JAVA

棧的特點：后進先出，所以一個線性鏈表實現的棧也只能在一端操作才能滿足這種特性；


/**
 * @Author: zzz
 * @CreateTime: 2017/3/27 14:51
 * @Description:
 */
public class MyStack<T> {

    private Node top;//永遠指向棧頂元素
 //元素個數
 private int size;


    /**
     * 內部類，定義節點
 */
 private class Node {
        public T data;

        public Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }

    }

    public void push(T data) {
        //next 指向當前元素top,如果是第一個元素next 指向null;
 Node node = new Node(data, top);
        //把當前元素指向top
 top = node;
        size++;
    }


    public T pop() {
        Node oldNode = top;
        top = top.next;
        oldNode.next = null;
        //釋放引用
 return oldNode.data;
    }

    //返回棧頂的元素，但不出棧
 public T peek() {
        return top.data;

    }

    // 判斷鏈棧是否為空棧
 public boolean empty() {
        return size == 0;
    }

    public String toString() {
        // 鏈棧為空鏈棧時
 if (empty())
            return "[]";
        else {
            StringBuilder sb = new StringBuilder("[");
            for (Node current = top; current != null; current = current.next) {
                sb.append(current.data.toString() + ", ");
            }
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();

        }
    }

    public static void main(String[] args) throws Exception {
        MyStack stack = new MyStack<String>();
        for (int i = 0; i <= 10; i++) {
            stack.push("111111-" + i);
        }
        System.out.println(stack);
        System.out.println("frist pop="+stack.pop());
        System.out.println("second pop="+stack.pop());
        System.out.println("thrid pop="+stack.pop());
        System.out.println("pop 之后的"+stack);
    }

/**
 * Created by zz.zhang on 2018/1/4.
 */
public class MyStack<T> {

    private int DEFAULT_SIZE = 8;//定義棧的初始默認長度
    private int capacity;//保存順序棧的長度
    private int size;//保存順序棧中元素的個數
    private Object[] elementData;//定義一個數組用于保存順序棧中的元素

    public MyStack() {
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }

    public MyStack(int initSize) {
        capacity = 1;
        while (capacity < initSize) {
            capacity <<= 1;//將capacity設置成大于initSize的最小2次方
        }
        elementData = new Object[capacity];
    }

    public void push(T element) throws Exception {
        elementData[size++] = element;
    }

    public T pop() throws Exception {
        if (empty()) {
            throw new IndexOutOfBoundsException("棧空，不能出棧");
        }
        T oldValue = (T) elementData[size - 1];
        elementData[--size] = null; // 設置成null 讓JVM垃圾回收
        return oldValue;
    }
public boolean empty() {
        return size == 0;
    }

    //返回當前順序棧中元素的個數
    public int length() {
        return size;
    }

    //獲取棧頂元素，不會將棧頂元素刪除
    public T peek() throws Exception {
        if (size == 0)
            throw new ArrayIndexOutOfBoundsException("棧為空");
        return (T) elementData[size - 1];
    }

    public void clear() {
        for (int i = 0; i < size; i++) {
            elementData[i] = null;
        }
        size = 0;
    }

    public static void main(String[] args)throws Exception{
        MyStack<String> stack=new MyStack<String>(30);
        for(int i=0 ;i<30;i++){
            stack.push(String.valueOf(i));
        }
        System.out.println(stack.pop());
        System.out.println(stack.peek());
    }
}