Leetcode[225] Implement Stack using Queues
28 Nov 2015###Task1 Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty. Notes: You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue. You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack). Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.
###Python ####Two queue
class Stack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.queue1 = collections.deque()
self.queue2 = collections.deque()
def push(self, x):
"""
:type x: int
:rtype: nothing
"""
self.queue1.append(x)
def pop(self):
"""
:rtype: nothing
"""
while len(self.queue1) > 1:
self.queue2.append(self.queue1.popleft())
temp = self.queue1.popleft()
while len(self.queue2):
self.queue1.append(self.queue2.popleft())
return temp
def top(self):
"""
:rtype: int
"""
while len(self.queue1) > 1:
self.queue2.append(self.queue1.popleft())
temp = self.queue1.popleft()
self.queue2.append(temp)
while len(self.queue2):
self.queue1.append(self.queue2.popleft())
return temp
def empty(self):
"""
:rtype: bool
"""
return len(self.queue1) == 0
####One queue
class Stack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.queue = collections.deque()
def push(self, x):
"""
:type x: int
:rtype: nothing
"""
self.queue.append(x)
def pop(self):
"""
:rtype: nothing
"""
for i in range(len(self.queue) - 1):
self.queue.append(self.queue.popleft())
return self.queue.popleft()
def top(self):
"""
:rtype: int
"""
for i in range(len(self.queue)):
top = self.queue.popleft()
self.queue.append(top)
return top
def empty(self):
"""
:rtype: bool
"""
return len(self.queue) == 0
###Java
class MyStack {
Queue<Integer> left = new LinkedList<Integer>();
Queue<Integer> right = new LinkedList<Integer>();
// Push element x onto stack.
public void push(int x) {
left.offer(x);
}
// Removes the element on top of the stack.
public void pop() {
while (left.size() > 1) {
right.offer(left.poll());
}
left.poll();
//swap
Queue<Integer> temp = right;
right = left;
left = temp;
}
// Get the top element.
public int top() {
while (left.size() > 1) {
right.offer(left.poll());
}
int val = left.poll();
right.offer(val);
//swap
Queue<Integer> temp = right;
right = left;
left = temp;
return val;
}
// Return whether the stack is empty.
public boolean empty() {
return (left.isEmpty() && right.isEmpty());
}
}
###Points
- This can be implemented with only one queue!