剑指offer专题2：队列和栈

• 用两个栈模拟队列

  class CQueue {stack<int> stack1;stack<int> stack2;
  public:CQueue() {}void appendTail(int value) {stack1.push(value);}int deleteHead() {int val=-1;if(!stack2.empty()){val = stack2.top();stack2.pop();}else if(!stack1.empty()){while(!stack1.empty()){val = stack1.top();stack1.pop();stack2.push(val);}stack2.pop();}return val;}
  };
  

• 用队列实现栈

  • 两个队列实现栈

    //每次入队一个元素都需要将这个元素放在队头
    // 时间O(n),空间O(n)
    class MyStack {queue<int> Que1;queue<int> Que2;
    public:MyStack() {}void push(int x) {Que1.push(x);while(!Que2.empty()){Que1.push(Que2.front());Que2.pop();}swap(Que1,Que2);}int pop() {int val = Que2.front();Que2.pop();return val;}int top() {return Que2.front();}bool empty() {return Que2.empty();}
    };
    

  • 一个队列实现栈

    // 一个队列实现，每次都将元素置前面
    // 时间O(n)，空间O(1)
    class MyStack {queue<int> Que;
    public:MyStack() {}void push(int x) {int n = Que.size();Que.push(x);while(n--){Que.push(Que.front());Que.pop();}}int pop() {int val = Que.front();Que.pop();return val;}int top() {return Que.front();}bool empty() {return Que.empty();}
    };