Stacks & Queues ​

Relevant problems

• Sliding window maximum: Give the maximum of a sliding window in O(n) time (see https://www.youtube.com/watch?v=CZQGRp93K4k)
  • Use a deque to store elements in decreasing order (from left to right)
  • Remove items from left if the window grows larger than k
  • To append new values, first remove items from right if they are smaller than the value being added.

Stacks ​

• Stacks are LIFO (reverses order) b c d a -> b c d a b c d a <- b c d
• Stacks can be used to reverse the order of sequential data.
• Core operations: push and pop
• Implementing a peek operation, which retrieves the top of the stack but doesn't remove it, is often a good idea as well. Time complexity
• O(1) time complexity for push and pop when implemented as a linked list or array

[! SUCCESS] Working with stacks

• Become familiar with situations that are well-suited for LIFO functionality, e.g., parsing, reversing order
• Use a stack to convert a recursive solution to an iterative one by replicating the function call stack.
• Implement a custom stack class by wrapping the list type.
  • s.append(k) pushes onto stack
  • s.pop() removes top of stack
  • s[-1] peeks top of stack
  • len(s) == 0 returns whether stack is empty

Queues ​

• Queues are FIFO (retains the order) b c d a -> b c d a b c d a b c -> d
• Core operations: enqueue and dequeue
• Double-ended queues (deques) can enqueue or dequeue on either end

[! SUCCESS]

• Become familiar with situtations that are well-suited for FIFO functionality, e.g., preserving order
• Implement a custom queue class by wrapping the collections.deque() type
  • deque.append() = q.push_back() enqueue from the back
  • deque.popleft() = q.pop_front() dequeue from front
  • dequeue.appendleft() = q.push_front() enqueues from front
  • deque.pop() = q.pop_back() dequeue from back
  • q[0] and q[-1] peek at the front and back of the queue respectively

Rust ​

Use Vec for a stack, see Arrays - Rust. Use VecDeque for a queue.

Problems ​

8.1 ​

8.2 ​

8.6 Compute binary tree nodes in order of increasing depth ​

This pseudocode doesn't quite work because it's difficult to know when the breadth ends for a given depth. It could be solved by adding all the extra None's and then omitting them when they're added to the result, but this adds time complexity. Instead, the better approach is to use nested loops (oh no!) but yes in this case nested loops are okays ince each node is still traversed only once. Using nested loops and two queues, on each iteration of the outer loop, add to the result all of the values from the current depth then populate another queue with all of the items from the next depth. This is still breadth first search, but differs from my known implementation (one-pass) that adds each element to a flat array. Both methods are good to know.

In addition to your known 1-pass 1-queue approach where you populate a flat array with BFS, know the solution where you use a 2-queue nested-loop to populate the breadth-wise elements and add to the final result on each iteration.

The output difference is [1,2,3,4,5,6,7] vs. [[1],[2,3],[4,5,6,7]].

8.7 Implement a circular queue ​

I managed to correctly deduce that both a front and back index tracker had to be used to get this question correct. What I failed to get correct was a simple re-arrangement of the array given the front and back index. When the array had to be resized, the authors simply doubled the size and moved what was behind the front tracker to the front, and what remained from the back to just behind that, then added the same size as None directly after that. Simple enough, but remember that you can extend an array with += operation, though .extend IMO is more clear. Also you can re-arrange the array in place with syntax like a = (a[head:] + a[:head])

LC 20 Valid Parantheses ​

The key to this question is to notice that the stack is the correct data structure to use. This can be ascertained by recognizing that a structured comparison is required. By this, I mean that the position of an entry informs us of other valid positioning of other entries.

I knew that the hash map wasn't the ideal data structure because it removes the notion of positioning, that is, hash maps are best suited for unstructured comparisons whereby a corresponding entry may exist anywhere in the rest of the string.. With that said, there is probably a solution that uses a hash map, but this would be significantly more complicated since one would have to encode arithmetic regarding the indexes relative to the total length of the array.

LC 232 Implement Queue with Two Stacks ​

Solution: To implement the queue data structure using two stacks, it is key to recognize that you can reverse the elements in a stack by popping each element in stack1 and appending them in order to stack2. The best way to solve this problem is to keep this logic in the peek method. On each push operation, append to stack1, on each pop operation, first conduct a peek to ensure that there is an entry available to pop from stack2, then pop from stack2. In the peek method, check if there is anything in stack2, if not, move everything from stack1 into stack2, reversing the order, and return the value from stack2[-1].

Example, where the stacks are instead named inbound and outbound.

from collections import deque

class MyQueue:
    def __init__(self):
        self.inbound = deque()
        self.outbound = deque()

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

    def pop(self) -> int:
        self.peek()
        return self.outbound.pop()

    def peek(self) -> int:
        if len(self.outbound) == 0:
            while self.inbound:
                self.outbound.append(self.inbound.pop())

        return self.outbound[-1]
        
    def empty(self) -> bool:
        return True if len(self.inbound) + len(self.outbound) == 0 else False

from collections import deque

class MyQueue:
    def __init__(self):
        self.inbound = deque()
        self.outbound = deque()

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

    def pop(self) -> int:
        self.peek()
        return self.outbound.pop()

    def peek(self) -> int:
        if len(self.outbound) == 0:
            while self.inbound:
                self.outbound.append(self.inbound.pop())

        return self.outbound[-1]
        
    def empty(self) -> bool:
        return True if len(self.inbound) + len(self.outbound) == 0 else False

LC 844 Backspace String Compare ​

This question tests your ability to recognize that a stack can be used to remove elements in sequential order.

Solution 1: Using a stack, pop if the character is #, append otherwise. Take care to simply continue the loop if you encounter a # character but the stack is empty so as not to throw.

Solution 2: Using a zip() and a function defined for traversing each string backwards (using yield), iterate in reverse over both strings, comparing each entry as it's found and use a skip_counter to evaluate whether or not you need to skip the next entry (or multiple entries). Implemented correctly, this can take O(1) space.