スタックの実装

Question

私はプログラミングでは新しく、スタックの実装に問題があります。 私の質問は、実装での配列とスタックの違いは何ですか？ Javaのようなプログラミング言語でスタックを定義するための正確な構文は何ですか？

ほとんどの人はスタックの実装にアレイを使用します。配列とスタックが2つの異なるデータ構造である場合、なぜスタックを実装するために配列を使用するのですか？配列なしでスタックを実装する方法は？

例を提供できる人は、私を助けてください。

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で

スタックは、実施例
Stack<T>として宣言されている間、配列は、Tはあなたのタイプである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); 
    } 
}