Stack and Queue

The stack (LIFO) and the queue (FIFO): bracket sequences and processing order.

The two simplest data structures differ in their removal order: • A stack is LIFO (last in, first out): the last one in is the first one out. Like a pile of plates. • A queue is FIFO (first in, first out): the first one in is the first one out. Like a line at a shop. In C++ the stack is std::stack (push, top, pop), the queue is std::queue (push, front, pop). The canonical stack problem is the valid bracket sequence: every closing bracket must match the most recently opened one. "The most recently opened" is exactly the top of the stack.

Try it yourself — the code is editable

Input (sample — feel free to edit)

Checking brackets of three kinds. Enter: ([]{}())

Note the two checks people often forget: a closing bracket with an EMPTY stack (a stray closer) and a NON-EMPTY stack at the end (unclosed brackets). You have already seen a queue, even if you didn't notice: it underlies breadth-first search (BFS), which awaits you at level 4. For now — a minimal service-order example.

Try it yourself — the code is editable

A queue: first come, first served

Task: given a string of brackets, find the depth of the deepest nesting (hint: it is the maximum stack size over time; for a single bracket kind even a counter suffices). Mark the lesson as completed and move on to set and map.