Implement Queue using Stacks(用栈实现队列)

时间:2022-11-05 16:32:07

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 top
    peek/pop from topsize,
    and is 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;
    } };