Implement Queue using Stacks【232】

Datetime:2016-08-23 01:22:48          Topic: LeetCode           Share

232. Implement Queue using Stacks

My Submissions

Total Accepted:  28236 Total Submissions:  83455 Difficulty:  Easy

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 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).

Subscribe to see which companies asked this question

Hide Tags
Stack   Design

Show Similar Problems

//思路首先:队列是先进先出,栈是先进后出,两次先进后出即是先进先出
//考虑用两个栈实现队列的效果:
//压入时:先将s2的元素全部压入s1,保证s2空,再将要压入的元素压入栈s1,再按照顺序全部压入栈2,这样s2就有序了
//删除时:将s2的栈顶弹出
//获取队首:获取s2栈顶元素
//是否为空?判断s2是否为空即可
class Queue {
public:
    // Push element x to the back of queue.//压到队列尾部
    void push(int x) {//此函数将花费大量时间
        while(!s2.empty())
        {
            int val=s2.top();
            s2.pop();
            s1.push(val);
        }
        s1.push(x);
        while(!s1.empty())
        {
            int val=s1.top();
            s1.pop();
            s2.push(val);
        }
    }

    // Removes the element from in front of queue.//从队列前面删除元素
    void pop(void) {
        s2.pop();
    }

    // Get the front element.//获取队首元素
    int peek(void) {
        return s2.top();
    }

    // Return whether the queue is empty.//队列是否为空
    bool empty(void) {
        return s2.empty();
    }
private:
    stack<int> s1;//辅助栈
    stack<int> s2;//执行栈,将模拟队列效果
};





About List