Implement the following operations of a queue using stacks.
- push(x) -- Push element x to the back of queue.
- pop() -- Removes the element from in front of queue.
- peek() -- Get the front element.
- empty() -- Return whether the queue is empty.
Notes:
- You must use only standard operations of a stack -- which means only
push
,
to toppeek/pop from top
,size
,
andis empty
operations are valid. - Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
- You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
- 题目解析:
- 用堆栈stack实现队列,仅仅能使用堆栈的操作,push(),pop()。empty().
- 方法:
- 用两个堆栈实现。代码例如以下:
class Queue {
public:
stack<int> st1;
stack<int> st2;
bool st1_use=1;
bool st2_use=0;
// Push element x to the back of queue.
void push(int x) {
if(st1_use==1)
st1.push(x);
else if(st2_use==1)
st2.push(x);
}
// Removes the element from in front of queue.
void pop(void) {
if(st1.empty()&&st2.empty())
exit(0);
if(st1_use==1&&st2_use==0)
{
while(st1.size()>1)
{
int temp=st1.top();
st2.push(temp);
st1.pop();
}
st1.pop();
while(st2.size()>0)
{
int temp=st2.top();
st1.push(temp);
st2.pop();
}
st1_use==1;
st2_use==0;
return;
}
if(st1_use==0&&st2_use==1)
{
while(st2.size()>1)
{
int temp=st2.top();
st1.push(temp);
st2.pop();
}
st2.pop();
while(st1.size()>0)
{
int temp=st1.top();
st2.push(temp);
st1.pop();
}
st1_use==0;
st2_use==1;
return;
}
}
// Get the front element.
int peek(void) {
if(st1_use==1&&st2_use==0)
{
int temp;
while(st1.size()>0)
{
temp=st1.top();
st2.push(temp);
st1.pop();
}
while(st2.size()>0)
{
int temp1=st2.top();
st1.push(temp1);
st2.pop();
}
st1_use==1;
st2_use==0;
return temp;
}
if(st1_use==0&&st2_use==1)
{
int temp;
while(st2.size()>0)
{
int temp=st2.top();
st1.push(temp);
st2.pop();
}
while(st1.size()>0)
{
int temp1=st1.top();
st2.push(temp1);
st1.pop();
}
st1_use==0;
st2_use==1;
return temp;
}
}
// Return whether the queue is empty.
bool empty(void) {
if(st1_use==1&&st1.empty())
return true;
if(st2_use==1&&st2.empty())
return true;
return false;
}
};
- 方法:
- 用两个堆栈实现。代码例如以下:
class Queue {
public:
stack<int> st1;
stack<int> st2;
bool st1_use=1;
bool st2_use=0;
// Push element x to the back of queue.
void push(int x) {
if(st1_use==1)
st1.push(x);
else if(st2_use==1)
st2.push(x);
} // Removes the element from in front of queue.
void pop(void) {
if(st1.empty()&&st2.empty())
exit(0);
if(st1_use==1&&st2_use==0)
{
while(st1.size()>1)
{
int temp=st1.top();
st2.push(temp);
st1.pop();
}
st1.pop();
while(st2.size()>0)
{
int temp=st2.top();
st1.push(temp);
st2.pop();
}
st1_use==1;
st2_use==0;
return;
}
if(st1_use==0&&st2_use==1)
{
while(st2.size()>1)
{
int temp=st2.top();
st1.push(temp);
st2.pop();
}
st2.pop();
while(st1.size()>0)
{
int temp=st1.top();
st2.push(temp);
st1.pop();
}
st1_use==0;
st2_use==1;
return;
}
} // Get the front element.
int peek(void) {
if(st1_use==1&&st2_use==0)
{
int temp;
while(st1.size()>0)
{
temp=st1.top();
st2.push(temp);
st1.pop();
} while(st2.size()>0)
{
int temp1=st2.top();
st1.push(temp1);
st2.pop();
}
st1_use==1;
st2_use==0;
return temp;
}
if(st1_use==0&&st2_use==1)
{
int temp;
while(st2.size()>0)
{
int temp=st2.top();
st1.push(temp);
st2.pop();
} while(st1.size()>0)
{
int temp1=st1.top();
st2.push(temp1);
st1.pop();
}
st1_use==0;
st2_use==1;
return temp;
}
} // Return whether the queue is empty.
bool empty(void) {
if(st1_use==1&&st1.empty())
return true;
if(st2_use==1&&st2.empty())
return true;
return false;
} };