Stack and Queue

1. Stack - Last In, First Out (LIFO), with only one end for operations.

   • Implemented using arrays or linked lists.

2. Queue - First In, First Out (FIFO), with two ends for operations: one for adding and one for removing elements.

   • Implemented using arrays or linked lists.

Stack Operations

Queue Operations

Common data structure operations and Big O notation.

1. Validate Parentheses String

Given a string s containing only '(', ')', '{', '}', '[', and ']', determine if the string is valid.

A valid string must meet the following conditions:

• Left brackets must be closed by the same type of right brackets.
• Left brackets must be closed in the correct order.
• Each right bracket must have a corresponding left bracket of the same type.

https://leetcode.cn/problems/check-if-a-parentheses-string-can-be-valid/

Use a stack to push left brackets and pop when encountering right brackets. Check if the stack is empty at the end.

def is_valid(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char not in mapping:
            stack.append(char)
        elif not stack or mapping[char] != stack.pop():
            return False
    return not stack

2. Implement a Stack Using Two Queues

Implement a LIFO stack using two queues, supporting push, pop, top, and empty operatoins.

class MyQueue:

    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def push(self, x):
        self.input_stack.append(x)

    def pop(self):
        if self.empty():
            return None
        if self.output_stack:
            return self.output_stack.pop()
        else:
            length = len(self.input_stack)
            self.output_stack = [self.input_stack.pop() for _ in range(length)]
            return self.output_stack.pop()

    def peek(self):
        if self.empty():
            return None
        if self.output_stack:
            return self.output_stack[-1]
        else:
            length = len(self.input_stack)
            self.output_stack = [self.input_stack.pop() for _ in range(length)]
            return self.output_stack[-1]

    def empty(self):
        return not (self.input_stack or self.output_stack)

3. Implement a Queue Using Two Stacks

Implement a FIFO queue using two stacks, supporting push, pop, peek, and empty operations.

class MyQueue:

    def __init__(self):
        self.list = []

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

    def pop(self) -> int:
        x = self.list[0]
        self.list = self.list[1:]
        return x

    def peek(self) -> int:
        return self.list[0]

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

if __name__ == "__main__":
    obj = MyQueue()
    obj.push(1)
    obj.push(2)
    print(obj.peek())
    print(obj.pop())
    print(obj.empty())

Priority Queue (Understand Implementation Mechanism)

PriorityQueue - Elements are added normally but removed based on priority.

Two implementation methods:

• 1. Heap (Binary, Binomial, Fibonacci)
• 2. Binary Search Tree

Min Heap and Max Heap

1. Kth Largest Element in a Data Stream

Design a class that finds the kth largest element in a stream of integers.

import heapq

class Solution:
    @staticmethod
    def find_kth_largest(nums, k):
        heap = []
        heapq.heapify(heap)
        for n in nums:
            if len(heap) < k:
                heapq.heappush(heap, n)
            elif n > heap[0]:
                heapq.heapreplace(heap, n)
        return heap[0]

2. Sliding Window Maximum

Given an array nums and a window size k, find the maximum value in each sliding window as it moves from left to right.

class Solution:
    @staticmethod
    def max_sliding_window(nums, k: int):
        if not nums or not k:
            return []
        if len(nums) == 1:
            return [nums[0]]
        queue = []
        res = []
        for i in range(len(nums)):
            if queue and queue[0] == i - k:
                queue.pop(0)
            while queue and nums[queue[-1]] < nums[i]:
                queue.pop()
            queue.append(i)
            if i >= k - 1:
                res.append(nums[queue[0]])
        return res