//基于數(shù)組實(shí)現(xiàn)的棧
public class MyStack<E> {
    private int size;//數(shù)組長(zhǎng)度
    //實(shí)際存儲(chǔ)數(shù)據(jù)的動(dòng)態(tài)數(shù)組
    private List<E> data = new ArrayList<>();
    
    //入棧,默認(rèn)尾插
    public void push(E val){
        data.add(val);
        size ++;
    }
    
    //彈出棧頂元素，返回棧頂?shù)闹?
    public E pop(){
        if(isEmpty()){
            //棧為空
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        //刪元素
       E val =  data.remove(size-1);
        size--;
        return val;
        //上面三句等同于return data.remove(size-1);
    }
    
    //返回棧頂元素，但不出棧
    public E peek(){
        if(isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek");
        }
        return data.get(size-1);
    }
    
    // 判斷當(dāng)前棧是否為空
    public boolean isEmpty() {
        return size == 0;
    }
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data.get(i));
            if (i != size - 1) {
                // 此時(shí)還沒到棧頂，還沒到數(shù)組末尾
                sb.append(", ");
            }
        }
        sb.append("] top");
        return sb.toString();
    }
}
 
//--------------------------
//測(cè)試類·
public class StackTest {
    public static void main(String[] args) {
        MyStack<Integer> myStack = new MyStack<>();
        myStack.push(1);
        myStack.push(3);
        myStack.push(5);
        System.out.println(myStack);
        System.out.println(myStack.pop());//刪除棧頂
        System.out.println(myStack.peek());//輸出棧頂，此時(shí)棧頂為3
        System.out.println(myStack.isEmpty());
    }
}

public interface Queue<E> {
    // 入隊(duì)
    void offer(E val);
    // 出隊(duì)
    E poll();
    // 返回隊(duì)首元素
    E peek();
    // 判斷隊(duì)列是否為空
    boolean isEmpty();
}
 
 //基于鏈表實(shí)現(xiàn)的基礎(chǔ)隊(duì)列
public class MyQueue<E> implements Queue<E> {
    // 鏈表的每個(gè)節(jié)點(diǎn)
    // ------------------------------
    //內(nèi)部類
    private class Node {
        E val;
        Node next;
        public Node(E val) {
            this.val = val;
        }
    }
    // ------------------------------
    // 當(dāng)前隊(duì)列中的元素個(gè)數(shù)
    private int size;
    // 隊(duì)首
    private Node head;
    // 隊(duì)尾
    private Node tail;
    @Override
    public void offer(E val) {
        Node node = new Node(val);
        if (head == null) {
            // 此時(shí)鏈表為空
            head = tail = node;
        }else {
            tail.next = node;
            tail = node;
        }
        size ++;
    }
 
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty!cannot poll!");
        }
        E val = head.val;
        Node node = head;
        head = head.next;
        // 將原來頭節(jié)點(diǎn)脫鉤
        node.next = null;
        size --;
        return val;
    }
 
    @Override
    public E peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }
 
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
 
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        // 鏈表的遍歷
        for (Node x = head;x != null;x = x.next) {
            sb.append(x.val);
            if (x.next != null) {
                // 還沒走到鏈表尾部
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
 
//測(cè)試類
public class QueueTest {
    public static void main(String[] args) {
        Queue<Integer> queue = new MyQueue<>();
        queue.offer(1);
        queue.offer(3);
        queue.offer(5);
        System.out.println(queue);
    }
}