(Reprinted from Blog article)
One of the important data structures is Stack and Queue, but we will address the issue of implementing them.
However, as shown in This commentary article, stacks and queues can be represented by arrays, which is a special data structure. Is not. The important difference is the following usage.
Extracts the last pushed element in the stack data structure Extract the first pushed element in the queue data structure
Implement Stack class and Queue class with the above functions.
Implement Stack using Queues
[https://leetcode.com/problems/implement-stack-using-queues/]
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.
Example:
MyStack stack = new MyStack();
stack.push(1); stack.push(2); stack.top(); // returns 2 stack.pop(); // returns 2 stack.empty(); // returns false
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).
First of all, from the implementation of stack. As you can see in the problem title, you are required to implement stack using queue.
Using a queue also limits the possible operations. Push is limited to the back and pop is limited to the front, as only push to back, peek / pop from front, size, and is empty operations are valid.
If you do it, the test will pass even if you ignore the intent of the problem and use stack. But, of course, there is no point in creating a stack using stack. In python, list shows the behavior corresponding to stack.
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = []
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.stack.append(x)
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.stack.pop()
def top(self) -> int:
"""
Get the top element.
"""
return self.stack[-1]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return len(self.stack) == 0
This problem requires you to implement stack using queue, but the point is pop. Again, stack retrieves the last pushed element, while queue retrieves the first pushed element.
In python you can retrieve the first pushed element with queue.popleft (). The following solution is to use popleft to sort the queue so that the element that was pushed later comes first when you execute push.
class MyStack:
def __init__(self):
self.queue = collections.deque()
def push(self, x: int) -> None:
q = self.queue
q.append(x)
for _ in range(len(q)-1):
q.append(q.popleft())
def pop(self) -> int:
return self.queue.popleft()
def top(self) -> int:
return self.queue[0]
def empty(self) -> bool:
return len(self.queue) == 0
The time complexity is $ O (n) $ for push and $ O (1) $ for pop.
By the way, it cannot be used under the request of this problem, but as described in the following article, there is also a pop method incollections.deque (), and the time complexity is $ O (1) $ from the back. It is possible to retrieve and delete elements.
[https://note.nkmk.me/python-collections-deque/:embed:cite]
Implement Queue using Stacks
[https://leetcode.com/problems/implement-queue-using-stacks/]
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.
Example:
MyQueue queue = new MyQueue();
queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false
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).
Next is the implementation of Queue. Now you are asked to implement a queue using stack.
This also limits the possible operations. only push to top, peek / pop from top, size, and is empty operations are valid. This means that only list.append (x), list [-1], and list.pop () are allowed for push, peek, and pop.
The following solution is to prepare two stacks, store them in the inStack when pushing, and prepare an outStack which stores the elements of the inStack in the reverse order for peek and pop, and perform processing.
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.inStack, self.outStack = [], []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.inStack.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
self.peek()
return self.outStack.pop()
def peek(self) -> int:
"""
Get the front element.
"""
if(self.outStack == []):
while(self.inStack != []):
self.outStack.append(self.inStack.pop())
return self.outStack[-1]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return len(self.inStack) == 0 and len(self.outStack) == 0
Recommended Posts