232. Implement Queue using Stacks

  • 35.6%

https://leetcode.com/problems/implement-queue-using-stacks/#/description

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 top, size, 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).

方法一:

使用两个栈,模拟队列,stack1存储新来的数据,当使用peek时,将stack1的数据都压入stack2,再求stack2的top就是peek数据,当需要pop时,只要先peek,然后再pop stack2就可以了,empty则最简单。

  1. 注意的地方,在pop()调用peek(),直接写 peek()就可以了。

  2. pop调用peek得到返回的值,然后需要stack2再pop一下,不要忘了。

疑问:如果都是空的,调用pop会发生什么情况,输出栈的error还是不作处理呢?栈直接pop,是error还是什么?

我的代码实现:

Oct 10th, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class MyQueue {
public:
stack<int> st1, st2;
/** Initialize your data structure here. */
MyQueue() {

}

/** Push element x to the back of queue. */
void push(int x) {
st1.push(x);
}

/** Removes the element from in front of queue and returns that element. */
int pop() {
int val = peek();
st2.pop();
return val;
}

/** Get the front element. */
int peek() {
if(st2.empty()){
while(st1.size()){
int val = st1.top();
st2.push(val);
st1.pop();
}
}
int val = st2.top();
return val;
}

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

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* bool param_4 = obj.empty();
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MyQueue {
stack<int> stack1;
stack<int> stack2;

public:
/** Initialize your data structure here. */
MyQueue() {

}

/** Push element x to the back of queue. */
void push(int x) {
stack1.push(x);
}

/** Removes the element from in front of queue and returns that element. */
int pop() {
peek();
int val = stack2.top();
stack2.pop();
return val;
}

/** Get the front element. */
int peek() {
if(stack2.empty()){
while(stack1.size()>0){
int val = stack1.top();
stack2.push(val);
stack1.pop();
}
}
return stack2.top();
}

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

https://discuss.leetcode.com/topic/17974/short-o-1-amortized-c-java-ruby

Short O(1) amortized, C++ / Java / Ruby

I have one input stack, onto which I push the incoming elements, and one output stack, from which I peek/pop. I move elements from input stack to output stack when needed, i.e., when I need to peek/pop but the output stack is empty. When that happens, I move all elements from input to output stack, thereby reversing the order so it’s the correct order for peek/pop.

The loop in peek does the moving from input to output stack. Each element only ever gets moved like that once, though, and only after we already spent time pushing it, so the overall amortized cost for each operation is O(1).

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class MyQueue {

Stack<Integer> input = new Stack();
Stack<Integer> output = new Stack();

public void push(int x) {
input.push(x);
}

public void pop() {
peek();
output.pop();
}

public int peek() {
if (output.empty())
while (!input.empty())
output.push(input.pop());
return output.peek();
}

public boolean empty() {
return input.empty() && output.empty();
}
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Queue {
stack<int> input, output;
public:

void push(int x) {
input.push(x);
}

void pop(void) {
peek();
output.pop();
}

int peek(void) {
if (output.empty())
while (input.size())
output.push(input.top()), input.pop();
return output.top();
}

bool empty(void) {
return input.empty() && output.empty();
}
};

https://discuss.leetcode.com/topic/19152/0-ms-c-solution-using-one-stack-w-explanation

0 ms C++ solution using one Stack w/ explanation.

You can implement queue using just one stack by either making push process costlier or pop costlier. Since we have two functions (top() and pop()) which require the top element of the stack, well make the push() function costlier - that is, for pushing a new element, we recursively pop the stack till it is empty and push it at the bottom of the stack, and take advantage of the recursive call to push back in the popped elements once the recursive call hits the base condition and returns. This implementation makes pop() and peek() functions easier. pop() is just going to pop off the top element in stack and peek() will return the top most element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Queue {
public:
stack<int> s;

// Push element x to the back of queue.
void push(int x) {
pushHelper(x);
}
void pushHelper(int x){
if(s.size()==0){
s.push(x);
return;
}
int data;
data = s.top();
s.pop();
pushHelper(x);
s.push(data);
return;

}

// Removes the element from in front of queue.
void pop(void) {
s.pop();
}

// Get the front element.
int peek(void) {
return s.top();
}

// Return whether the queue is empty.
bool empty(void) {
return (s.size()==0);
}
};

https://discuss.leetcode.com/topic/26163/share-my-python-solution-32ms

Share my python solution (32ms)

The idea is to simulate a queue using two stacks (same as previous posts). I use python list as the underlying data structure for stack and add a “move()” method to simplify code: it moves all elements of the “inStack” to the “outStack” when the “outStack” is empty. Here is the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Queue(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.inStack, self.outStack = [], []

def push(self, x):
"""
:type x: int
:rtype: nothing
"""
self.inStack.append(x)

def pop(self):
"""
:rtype: nothing
"""
self.move()
self.outStack.pop()

def peek(self):
"""
:rtype: int
"""
self.move()
return self.outStack[-1]

def empty(self):
"""
:rtype: bool
"""
return (not self.inStack) and (not self.outStack)

def move(self):
"""
:rtype nothing
"""
if not self.outStack:
while self.inStack:
self.outStack.append(self.inStack.pop())

https://discuss.leetcode.com/topic/17984/accepted-0ms-c-solution-with-two-std-stack-easy-understand

Accepted 0ms c++ solution with two std::stack, easy understand.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Queue {
public:
// Push element x to the back of queue.
void push(int x) {
while (!nums.empty()) {
helper.push(nums.top());
nums.pop();
}
nums.push(x);
while (!helper.empty()) {
nums.push(helper.top());
helper.pop();
}
}
// Removes the element from in front of queue.
void pop(void) {
nums.pop();
}
// Get the front element.
int peek(void) {
return nums.top();
}
// Return whether the queue is empty.
bool empty(void) {
return nums.empty();
}
private:
std::stack<int> helper, nums;
};
谢谢你,可爱的朋友。