LeetCode Day 10 Stack and queue(1/3)

Today I studied and practice about stack and queue

Question 1

232. Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

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, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

This question does not examine the algorithm, it examines the idea of stacks and queues and the knowledge.

Only two stacks can be used, if you want to achieve queue FIFO, you need a stack as in, a stack is responsible for out, the elements of the stack-in need to be transferred to the out, pay attention to the order of the out to correspond to the in.

Note that in pop(), if stack-out is empty, you need to import the full stack-in into it, make sure it’s complete, otherwise there will be a problem of wrong order.

class MyQueue:
 
    def __init__(self):
        self.stackIn = []
        self.stackOut = []
 
    def push(self, x: int) -> None:
        self.stackIn.append(x)
 
    def pop(self) -> int:
        if self.empty():
            return None
        if self.stackOut:
            return self.stackOut.pop()
        else:
            for i in range(len(self.stackIn)):
                self.stackOut.append(self.stackIn.pop())
            return self.stackOut.pop()
 
    def peek(self) -> int:
        ans = self.pop()
        self.stackOut.append(ans)
        return ans
 
 
    def empty(self) -> bool:
        return not (self.stackIn or self.stackOut)
 

Question 2

225. Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Implementing a LIFO stack using two queues, is a little different from the previous question.

class MyStack:
 
    def __init__(self):
        self.queueIn = deque()
        self.queueOut = deque()
 
    def push(self, x: int) -> None:
        self.queueIn.append(x)
 
    def pop(self) -> int:
        if self.empty():
            return None
 
        for i in range(len(self.queueIn) - 1):
            self.queueOut.append(self.queueIn.popleft())
        
        self.queueIn, self.queueOut = self.queueOut, self.queueIn   
        return self.queueOut.popleft()
 
    def top(self) -> int:
        if self.empty():
            return None
        
        return self.queueIn[-1]
 
 
    def empty(self) -> bool:
        return len(self.queueIn) == 0