스 택 의 실현 (배열 과 링크 구현)

 （    ），    （LIFO）      ，        。
    push             。
    pop              
    peak          

package com.dengdi.arraystack;

public interface StackADT{
    /**
     *           
     * @param element
     */
    public void push(T element);
    /**
     *          
     * @return
     */
    public T pop();
    /**
     *       
     * @return
     */
    public T peek();
}

             ：
    (1)            (             )；
    (2)          0 ；
    (3)                 ；
    (4)    top               。

package com.dengdi.arraystack;
/**
 *           
 * @author dengdi
 *
 * @param 
 */
public class ArrayStack implements StackADT{
    private int DEFAULT_LENGTH=100;
    private int point;
    private T[] stack;

    public ArrayStack() {
        point=0;
        stack=(T[]) new Object[DEFAULT_LENGTH];//          
    }

    @Override
    public void push(T element) {
        stack[point]=element;
        point++;
    }

    @Override
    public T pop() {
        point--;
        T result=stack[point];
        stack[point]=null;
        return result;
    }

    @Override
    public T peek() {

        return stack[point-1];
    }   
}

             ，                ，                 。                    。
      ：                    。      next       。
               ，                 。

package com.dengdi.arraystack;
//     
public class LinkedNode {
    private LinkedNode next;//      
    private T element;
    public LinkedNode() {
        this.next=null;
        this.element=null;
    }
    public LinkedNode(T element) {
        this.next=null;
        this.element = element;
    }
    public LinkedNode getNext() {
        return next;
    }
    public void setNext(LinkedNode next) {
        this.next = next;
    }
    public T getElement() {
        return element;
    }
    public void setElement(T element) {
        this.element = element;
    }

}

           ：
                       ：    、           。
                  ，             ，      next                。  ，                       。

package com.dengdi.arraystack;  
/**
 *       
 * @author dengdi
 *
 * @param 
 */

public class LinkedStack<T> implements StackADT<T>{
    private int count;
    private LinkedNode top;
    @Override
    public void push(T element) {
        LinkedNode temp=new LinkedNode(element);
        temp.setNext(top);
        top=temp;
        count++;
    }

    @Override
    public T pop() {
        T result=top.getElement();
        top=top.getNext();
        count--;
        return result;
    }

    @Override
    public T peek() {
        T result=top.getElement();
        return result;
    }

}