队与栈的相互实现

队列是一种先进先出的数据结构，栈是一种先进后出的数据结构.
这两种数据结构底层其实都是数组或者链表实现的，只是 API 限定了它们的特性

1.用栈实现队列
方法是用两个栈，stack1用于入队，stack2用于出队。当创造一个队列时，也就是创造了两个栈；当一个新元素入队的时候，就是在stack1之中加入新元素，当要出队列的时候，若stack1为空则队列为空，因为队列是先入先出，也就是要去除stack1中的最后一个元素，那么就把stack1中的元素依次加入stack2中，那么stack1中栈底元素就成了stack2的栈顶了，那么stack2 直接pop() 就完成任务，完成之后再把stack2的元素重新加入stack1之中。
剑指09.

class CQueue {
    private Stack<Integer> s1,s2;

    public CQueue() {
        s1=new Stack<>();
        s2=new Stack<>();
    }
    
    public void appendTail(int value) {
        s1.push(value);

    }
    
    public int deleteHead() {
        if(s1.empty()){return -1;}
        while(!s1.empty()){
            s2.push(s1.pop());
        }
        int deleitem= s2.pop();
        while(!s2.empty()){
            s1.push(s2.pop());
        }
        return deleitem;
    }
}

栈结构实现一个队列，核心思想是利用两个栈互相配合。

2.用队列实现栈

class MyStack {
    private Queue<Integer> q1;
    int top_ele=0;

    /** Initialize your data structure here. */
    public MyStack() {
        q1=new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        q1.offer(x);
        top_ele=x;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int sz=q1.size();
        for(int i=0;i<sz-2;i++){
            q1.offer(q1.poll());
        }
        top_ele=q1.peek();
        q1.offer(q1.poll());
        return q1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return top_ele;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q1.isEmpty();
    }
}

这里的操作比较直接。