232-用栈实现队列

题目描述

使用栈实现队列的下列操作：

• push(x) -- 将一个元素放入队列的尾部。
• pop() -- 从队列首部移除元素。
• peek() -- 返回队列首部的元素。
• empty() -- 返回队列是否为空。

思路

创建两个栈 s1， s2

1. 入队

   将元素放入 s1 中

2. 出队

   • 若 s2 为空，将 s1 的元素 放入 s2 中， 此时 s2 的栈顶就是队首元素，s2 栈顶出栈。
   • 若 s2 不为空，直接将 s2 栈顶元素出栈即可。

3. 获取队首元素

   • 若 s2 不为空，s2 的栈顶元素就是队首元素。
   • 若 s2 为空，s1 不为空，将 s1 中的元素放入 s2 中，然后 s2 的栈顶元素就是队首元素。

代码

class MyQueue {
public:
    /** Initialize your data structure here. */
	stack<int> s1, s2;
	int temp;
	int res;
    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())
			{
				temp = s1.top();
				s2.push(temp);
				s1.pop();
			}
			res = s2.top();
			s2.pop();
			return res;
		}
		else
		{
			res = s2.top();
			s2.pop();
			return res;
		}
    }

    /** Get the front element. */
    int peek() {
        if(!s2.empty())
		{
			res = s2.top();
			return res;
		}
		else if(!s1.empty())
		{
			while(!s1.empty())
			{
				temp = s1.top();
				s2.push(temp);
				s1.pop();
			}
			res = s2.top();
			return res;
		}
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty() && s2.empty();
    }
};