LeetCode：栈和队列

这篇博客主要是记录一下我在刷LeetCodei时，做的一些关于栈和队列的题目。关于栈和队列的基础知识以及操作，这里不说，直接上题目。

例题1、 使用栈实现队列 LeetCode 232

分析：栈是后进先出，而队列是先进先出。我们可以使用两个栈来实现队列，如下图示。

使用两个栈来实现，一个用来push,一个用来pop()。当来了新元素时，压入s1中；对于弹出操作，当s2不为空的时候，在stack2中的栈顶元素是最先进入队列的元素，可以弹出。如果stack2为空时，我们把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压到stack1的底端，经过弹出和压入之后就处于stack2的顶端了，又可以直接弹出。
具体代码实现如下：

class MyQueue {
public:
    stack<int>s1;
    stack<int>s2;
public:
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
       if(s2.empty()){
        while(!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
        }
         int tmp=s2.top();
        s2.pop();
        return tmp;
    }
    
    /** Get the front element. */
    int peek() {
        if(s2.empty()){
        while(!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
        }
        
        int tmp=s2.top();
        return tmp;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        if(s1.empty()&&s2.empty())return true;
        else return false;
    }
};

例题2、 使用队列实现栈 LeetCode 225

分析：这道题和上面那道题类似，我们采用同样的方法，使用两个队列去实现栈。当有新元素要push时，用q2暂时存储之前的栈，q1存储新元素，然后再讲q2的元素再压回q1，这样q1中保存的就是倒序的数据，和栈的数据顺序是一样的；

class MyStack {
public:
    queue<int>q1;
    queue<int>q2;
public:
    /** Initialize your data structure here. */
    MyStack() {
    }
    /** Push element x onto stack. */
    void push(int x) {
         while(!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        } //先将q1清空，在装入新元素，然后将之前保存在q2中的数据在压回q1； 
        q1.push(x);
        while(!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
        }

    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
 int a = q1.front();
        q1.pop();
        return a;
    }
    
    /** Get the top element. */
    int top() {
   return q1.front();

    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
      return q1.empty();
    }
};