栈与队列

理论知识

栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

那么问题来了，STL 中栈是用什么容器实现的？

从下图中可以看出，栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现

用栈实现队列(力扣232.)

• 新建一个栈
• push的时候，stackIn.push()即可
• pop的时候，判断if(stackOut.empty()){
• while(stackIn.empty()){
• stackOut.push(stackIn.top());
• stackIn.pop();}
• return result;}
• peek的时候，result=this->pop();
• stackOut.push(result);
• return result;

class MyQueue {
    //需要两个栈来模拟输入输出
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();//负责进栈
        stackOut = new Stack<>();//负责出栈
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        if(stackOut.isEmpty()){
            while(!stackIn.isEmpty()){
                int x = stackIn.pop();
                stackOut.push(x);
            }
        }
        return stackOut.pop();
    }
    
    public int peek() {
        int temp = this.pop();
        stackOut.push(temp);
        return temp;
    }
    
    public boolean empty() {
        return stackIn.isEmpty()&&stackOut.isEmpty();
    }
}

用队列实现栈(力扣225.)

• 用一个队列就能实现

• push时，直接放入

• pop时，先弹出再插入

• queue队列的api：add(),poll();

• Queue queue = new LinkedList();

class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList();
    }
    
    public void push(int x) {
        queue.add(x);
    }
    
    public int pop() {
        int size = queue.size() - 1;
        while(size-- > 0){
            int temp = queue.poll();
            queue.add(temp);
        }
        return queue.poll();
    }
    
    public int top() {
        int temp = this.pop();
        queue.add(temp);
        return temp;
    }
    
    public boolean empty() {
        return queue.size()<=0;
    }
}