Stacks and Queues

[YuezhenQin]

Stacks and Queues

While a stack followed a LIFO pattern, a queue follows FIFO (first in first out). In a stack, elements are added and removed from the same side. In a queue, elements are added and removed from opposite sides.

[YuezhenQin]

Stack: Matching

A stack is an ordered collection of elements where elements are only added and removed from the same end.

The characteristic that makes something a "stack" is that you can only add and remove elements from the same end. It doesn't matter how you implement it, a "stack" is just an abstract interface.

Typically, inserting into a stack is called pushing and removing from a stack is called popping. Stacks will usually also come with operations like peek, which means looking at the element at the top of the stack.

[YuezhenQin]

Queues: BFS

Queues are trickier to implement than stacks if you want to maintain good performance. Like a stack, you could just use a dynamic array, but operations on the front of the array (adding or removal) are O(n), where n is the size of the array.

One way to implement an efficient queue is by using a doubly linked list. Recall that with a doubly linked list, if you have the pointer to a node, you can add or delete at that location in O(1). A doubly linked list that maintains pointers to the head and tail (both ends, usually with sentinel nodes) can implement an efficient queue.

There is also a data structure called a deque, short for double-ended queue, and pronounced "deck". In a deque, you can add or delete elements from both ends. A normal queue designates adding to one end and deleting to another end.

[YuezhenQin]

Stacks and Queues: Preserve Monotonic

Monotonic stacks and queues are useful in problems that, for each element, involves finding the "next" element based on some criteria，for example, the next larger/smaller element.

Here's some pseudocode for maintaining a monotonic increasing stack over an input array:

Stack<E> stack = new Stack<>();
for (int num: nums) {
    while (!stack.isEmpty() && stack.peek() >= num) { 
        stack.pop();
    }
    stack.push(num);
}

Monotonic increasing: [min, max] Monotonic decreasing: [max, min]