題目描述
使用棧實(shí)現(xiàn)隊(duì)列的下列操作：
- push(x) -- 將一個(gè)元素放入隊(duì)列的尾部。
- pop() -- 從隊(duì)列首部移除元素。
- peek() -- 返回隊(duì)列首部的元素。
- empty() -- 返回隊(duì)列是否為空。
思路
創(chuàng)建兩個(gè)棧 s1鹉胖， s2
-
入隊(duì)
將元素放入 s1 中
-
出隊(duì)
- 若 s2 為空，將 s1 的元素 放入 s2 中够傍， 此時(shí) s2 的棧頂就是隊(duì)首元素甫菠，s2 棧頂出棧。
- 若 s2 不為空冕屯，直接將 s2 棧頂元素出棧即可寂诱。
-
獲取隊(duì)首元素
- 若 s2 不為空，s2 的棧頂元素就是隊(duì)首元素安聘。
- 若 s2 為空痰洒，s1 不為空瓢棒，將 s1 中的元素放入 s2 中，然后 s2 的棧頂元素就是隊(duì)首元素丘喻。
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();
}
};
