Stack & Queue Summary

Summary of Stack & Queue.

LeetCode 232 Implement Queue using Stacks

class MyQueue:

    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        self.stack_in.append(x)

    def pop(self) -> int:
        if self.empty(): 
            return None

        if self.stack_out:
            return self.stack_out.pop()
        else:
            # for i in range(len(self.stack_in)):
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()

    def peek(self) -> int:
        if not self.stack_out:
              return self.stack_in[0]
        else:
              return self.stack_out[-1]

    def empty(self) -> bool:
        return not (self.stack_in or self.stack_out)

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

LeetCode 225 Implement Stack using Queues

two queues

class MyStack:

    def __init__(self):
        self.queue_in = deque()
        self.queue_out = deque()

    def push(self, x: int) -> None:
        self.queue_in.append(x)

    def pop(self) -> int:
        if self.empty():
            return None
        for i in range(len(self.queue_in)-1):
            self.queue_out.append(self.queue_in.popleft())
        self.queue_out, self.queue_in = self.queue_in, self.queue_out
        return self.queue_out.popleft()

    def top(self) -> int:
        if self.empty():
            return None
        return self.queue_in[-1]

    def empty(self) -> bool:
        return len(self.queue_in) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

one queue

class MyStack:

    def __init__(self):
        self.que = deque()

    def push(self, x: int) -> None:
        self.que.append(x)

    def pop(self) -> int:
        if self.empty():
            return None
        for i in range(len(self.que)-1):
            self.que.append(self.que.popleft())
        return self.que.popleft()

    def top(self) -> int:
        if self.empty():
            return None
        return self.que[-1]

    def empty(self) -> bool:
        return len(self.que) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

LeetCode 20 Valid Parentheses

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for it in s:
            if it == '(':
                stack.append(')')
            elif it == '[':
                stack.append(']')
            elif it == '{':
                stack.append('}')
            elif not stack or stack[-1] != it:
                return False 
            else:
                stack.pop()
        return True if not stack else False

LeetCode 1047 Remove All Adjacent Duplicates in String

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for it in s:
            if stack and it == stack[-1]:
                stack.pop()
            else:
                stack.append(it)
        return ''.join(stack)

LeetCode 150 Evaluate Reverse Polish Notation

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for tok in tokens:
            if tok not in ['+','-','*','/']:
                stack.append(tok)
            else:
                first, second = stack.pop(), stack.pop()
                stack.append(int(eval(f'{second} {tok} {first}')))
        return int(stack.pop())

LeetCode 239 Sliding Window Maximum

A customized Monotonic Queue

class MyQueue():
    def __init__(self):
        self.queue = []
    
    def pop(self, value):
        # move window and remove the first element
        if self.queue and self.queue[0] == value:
            self.queue.pop(0)

    def push(self, value):
        # keep descending order
        while self.queue and self.queue[-1] < value:
            self.queue.pop()
        self.queue.append(value)

    def front(self):
        # return the max
        return self.queue[0]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = MyQueue()
        res = []
        for i in range(k):
            que.push(nums[i])
        res.append(que.front())
        for i in range(k, len(nums)):
            que.pop(nums[i-k]) # popleft if it's the max
            que.push(nums[i])
            res.append(que.front()) # current max
        return res

max-heap

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
                 # elements in heap are in increasing order by default in python
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)
        res = [-q[0][0]]
        for i in range(k, len(nums)):
            heapq.heappush(q,(-nums[i], i))
            while q[0][1] <= i-k:
                heapq.heappop(q)
            res.append(-q[0][0])
        return res

LeetCode 347 Top K Frequent Elements

min-heap

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = {}
        for i in nums:
            if i not in cnt:
                cnt[i] = 1
            else:
                cnt[i] += 1
        
        que = []
        for num, freq in cnt.items():
            heapq.heappush(que, (freq, num))
            if len(que) > k: # keep the size = k
                heapq.heappop(que)
        res = []
        for i in range(k-1, -1, -1):
            res.append(que[i][1])
        return res