棧實現

Question

我是編程新手，在堆棧實現中遇到問題。 我的問題是實現中數組和堆棧之間的區別。在Java等編程語言中定義堆棧的確切語法是什麼？

大多數人使用數組來實現堆棧。如果數組和堆棧是兩種不同的數據結構，爲什麼我們使用數組來實現堆棧？我們如何在沒有數組的情況下實現堆棧？

如果有人可以提供一個例子，請幫助我。

Answer 1

Amit給出了定義堆棧的語法。作爲一個具體的例子，在Java中，您可以按如下方式定義整數堆棧： Stack<Integer> intStack = new Stack<Integer>();現在您可以使用堆棧的所有方法，如intStack.push()和intStack.pop()。有用的鏈接：http://en.wikibooks.org/wiki/Java_Programming/Collection_Classes

堆棧也是使用數組或鏈表實現的原因是，並非所有語言都具有內置的堆棧數據結構。例如C沒有它，你可以實現一個堆棧的唯一方法是間接的（使用數組，鏈表等）http://en.wikipedia.org/wiki/Stack_(abstract_data_type)#Array。在Java中，事情更容易，因爲您可以直接使用堆棧實現。

Answer 2

數組和堆棧是完全不同的東西。數組給你random access，而堆棧給你LIFO的行爲。

在Java

，陣列被定義爲T[]其中T是您的類型，而堆被聲明爲Stack<T>
實施例：

Stack<Object> stack = new Stack<Object>(); 
Object[] array = new Object[K]; //K is the array's size 

陣列可以被用來實現堆棧僅因爲它是非常基本的和簡單的，以任何架構來處理數組，但它不一定是這種情況。堆棧也可以由LinkedList或許多其他數據結構組成。

Answer 3

您可以使用數組或鏈表。使用數組可以更簡單。

如果您想要相同的代碼，我會查看JDK附帶的Stack的源代碼。

Answer 4

package com.uttara.stack; 

public class ArrayStack 
{ 
    int num; 
    public ArrayStack(int num) 
    { 
     this.num = num; 
    } 

    private Object[] element= new Object[10]; 

    int pos=0; 

    public void push(Object e) throws stackflowException 
    { 
     if(pos < element.length) 
     element[pos++] =e; 
     else 
      throw new stackflowException("something went wrong"); 
    } 

    public Object pop() throws stackflowException 
    { 

     return element[--pos]; 


    } 

    public Object peek() 
    { 
     return element[pos-1]; 

    } 
} 

公共類Stackimpli {

public static void main(String[] args) throws stackflowException { 

    ArrayStack s =new ArrayStack(10); 

    s.push("saffron"); 
    s.push("orange"); 
    s.push("8051"); 
    s.push("intel"); 
    s.push("android"); 
    s.push("linux"); 
    s.push("orange"); 
    s.push("blah"); 

    System.out.println(s.peek()); 
    for(int i=0; i<8; i++) 
    { 
System.out.println(s.pop()); 
    } 


} 

Answer 5

而不陣列疊層可以與節點中實現。如果你不熟悉什麼是節點，我建議你挖掘鏈表。它使用節點來存儲數據，節點是一種容器，它將數據和指針變量保存到下一個或前一個元素。

Answer 6

堆棧程序

package com.elegant.ds.stack; 

import java.util.Scanner; 

public class StackDemo { 

    @SuppressWarnings("resource") 
    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 
     System.out.println("Enter the size of stack"); 
     int size = scanner.nextInt(); 
     StackDemoTest stack = new StackDemoTest(size); 
     boolean yes = true; 
     do { 
      System.out.println("1. Push"); 
      System.out.println("2. Pop"); 
      System.out.println("3. Check Full"); 
      System.out.println("4. Check Empty"); 
      System.out.println("5. Delete Middle"); 
      System.out.println("6. Peek"); 
      System.out.println("7. Display"); 
      System.out.println("8. Exit"); 

      int choice = scanner.nextInt(); 
      switch (choice) { 
      case 1: 
       stack.push(scanner.nextInt()); 
       break; 

      case 2: 
       stack.pop(); 
       break; 

      case 3: 
       System.out.println(stack.isFull()); 
       break; 

      case 4: 
       System.out.println(stack.isEmpty()); 
       break; 

      case 5: 
       stack.deleteMiddle(); 
       break; 

      case 6: 
       stack.peek(); 
       break; 

      case 7: 
       stack.display(); 
       break; 
      case 8: 
       yes = false; 
       break; 

      default: 
       System.out.println("Invalid Choice!"); 
       break; 
      } 
     } while (yes); 
    } 
} 

class StackDemoTest { 

    int top = -1; 
    int size = 0; 
    int[] stackArray = null; 

    public StackDemoTest() { 

    } 

    public StackDemoTest(int size) { 
     stackArray = new int[size]; 
     top = -1; 
     this.size = size; 
    } 

    public void push(int item) { 
     if (isFull()) { 
      System.out.println("Stack is Full"); 
      return; 
     } 
     stackArray[++top] = item; 
     display(); 
    } 

    public void pop() { 
     if (isEmpty()) { 
      System.out.println("Stack is Empty"); 
      return; 
     } 
     System.out.println("poped item is " + stackArray[top]); 
     --top; 
     display(); 
    } 

    public void display() { 

     if (isEmpty()) { 
      System.out.println("Stack is Empty"); 
      return; 
     } 
     System.out.println("Items in stack is :-"); 
     for (int i = 0; i <= top; i++) { 
      System.out.print(stackArray[i] + " "); 
     } 
     System.out.println(); 
    } 

    public void deleteMiddle() { 
     if (isEmpty()) { 
      System.out.println("Stack is Empty "); 
      return; 
     } 
     System.out.println("Deleted Element is : " + stackArray[top/2]); 
     for (int i = top/2; i < top; i++) { 
      stackArray[i] = stackArray[i + 1]; 
     } 
     top--; 
     display(); 
    } 

    public void peek() { 
     if (isEmpty()) { 
      System.out.println("Stack is empty "); 
      return; 
     } 
     System.out.println("Peek item is : " + stackArray[top]); 
    } 

    public boolean isEmpty() { 
     return top <= -1; 
    } 

    public boolean isFull() { 
     return top + 1 >= size; 
    } 
} 

堆棧使用LinkedIst

package com.elegant.ds.stack; 

import java.util.NoSuchElementException; 
import java.util.Scanner; 


class Node { 
    private int data = 0; 
    private Node link = null; 

    public Node() { 

    } 

    public Node(int data, Node link) { 
     this.data = data; 
     this.link = link; 
    } 

    public int getData() { 
     return data; 
    } 

    public void setData(int data) { 
     this.data = data; 
    } 

    public Node getLink() { 
     return link; 
    } 

    public void setLink(Node link) { 
     this.link = link; 
    } 

    @Override 
    public String toString() { 
     return "Node [data=" + data + ", link=" + link + "]"; 
    } 

} 

class LinkedStack { 

    private Node top = null; 
    private int size = 0; 

    public LinkedStack() { 
     top = null; 
     size = 0; 
    } 

    public void push(int item) { 
     Node nptr = new Node(item, null); 
     if (isEmpty()) { 
      top = nptr; 
     } else { 
      nptr.setLink(top); 
      top = nptr; 
     } 
     size++; 
    } 

    public boolean isEmpty() { 
     return top == null; 
    } 

    public int pop() { 
     if (isEmpty()) 
      throw new NoSuchElementException("Underflow Exception"); 

     Node ptr = top; 
     top = ptr.getLink(); 
     size--; 
     return ptr.getData(); 

    } 

    public int peek() { 

     if (isEmpty()) 
      throw new NoSuchElementException("Underflow Exception"); 
     return top.getData(); 
    } 

    public int size() { 
     return size; 
    } 

    public int deleteMiddle() { 
     return 0; 
    } 
} 

public class LinkedStackTest { 

    @SuppressWarnings("resource") 
    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 
     LinkedStack linkedStack = new LinkedStack(); 
     boolean yes = true; 
     do { 
      System.out.println("1. Push"); 
      System.out.println("2. Pop"); 
      System.out.println("3. Peek"); 
      System.out.println("4. Check Empty"); 
      System.out.println("5. Size"); 
      System.out.println("6. Delete Middle Element"); 
      int choice = scanner.nextInt(); 
      switch (choice) { 
      case 1: 
       System.out.println("Enter the element :- "); 
       linkedStack.push(scanner.nextInt()); 
       break; 

      case 2: 
       try { 
        System.out.println("Popped Element = " + linkedStack.pop()); 
       } catch (Exception e) { 
        System.out.println(e.getMessage()); 
       } 
       break; 

      case 3: 
       try { 
        System.out.println("Peek Element = " + linkedStack.peek()); 
       } catch (Exception e) { 
        System.out.println(e.getMessage()); 
       } 
       break; 

      case 4: 
       System.out.println(linkedStack.isEmpty()); 
       break; 

      case 5: 
       System.out.println(linkedStack.size()); 
       break; 

      case 6: 
       try { 
        System.out.println(linkedStack.deleteMiddle()); 
       } catch (Exception e) { 
        System.out.println(e.getMessage()); 
       } 
       break; 

      default: 
       break; 
      } 
     } while (yes); 
    } 
}