15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 6 of 12 in the free DSA Basics course · 6 lessons
Build a model of two ways to organize arriving data:
Extend these rules to circular queues, monotonic structures for array and window problems, and stacks for expression parsing. Compare array-backed and linked-node implementations to choose a representation based on the operations your program needs.
There are no required prior lessons.
You should be comfortable reading simple arrays, following variables such as indices and counters, and tracing one operation at a time. When an operation removes an item, write down both the returned value and the structure state afterward.
Use this stack operation sequence throughout the first lesson:
1Operations: push(4), push(7), pop(), push(2)Start with an empty stack:
1stack = []
2top = no elementApply each operation in order:
push(4) puts 4 on top.
1stack = [4]
2top = 4push(7) puts 7 above 4.
1stack = [4, 7]
2top = 7pop() removes and returns the top item, so it returns 7, not 4.
1returned = 7
2stack = [4]
3top = 4push(2) puts 2 on top.
1stack = [4, 2]
2top = 2Keep an explicit state and update it after every operation. A queue requires the same record of state, with different insertion and removal ends.
Stack Operations establishes the last-in-first-out model, the meaning of the top element, and behavior when a stack is empty.
Queue Operations introduces a queue’s first-in-first-out behavior. Track both a front and a rear.
Implementation Approaches compares array-backed and linked-node versions of stacks and queues, including the costs of their operations.
Circular Queue Mechanics uses queue front and rear positions. It improves an array queue by wrapping indices back to the beginning after freed positions become available.
Expression Parsing Basics applies stack push, pop, and peek operations to parentheses, operator precedence, postfix conversion, and postfix evaluation.
Monotonic Stack and Queue uses ordinary stack, queue, and deque operations to keep useful candidates in a chosen order.
A stack has one active end: the top. You insert, inspect, and remove at that end. One active end makes stack state changes easy to trace and defines the empty-structure case.
A queue has two roles. New values enter at the rear, while old values leave from the front. For example, if a queue is:
1front → [4, 7] ← rearthen enqueue(2) produces:
1front → [4, 7, 2] ← rearThe front stays at 4. A later dequeue returns 4, because queues remove the earliest inserted item.
A simple array queue can run out of room at the rear even after earlier values have been removed from the front. Circular Queue Mechanics addresses that representation problem: after the rear reaches the final array index, its next position is computed with modular arithmetic and may become index 0. An explicit size value distinguishes an empty queue from a full one.
A monotonic stack or deque keeps values or indices in increasing or decreasing order. When a new candidate makes an older one irrelevant, the older candidate is removed. These operations support finding a next-greater value or the maximum in each fixed-size window.
Expression parsing uses the same stack rule with operators or values as stored items. Parentheses determine when operators must be processed, and precedence determines whether an operator stays on the stack or is removed first. Check the top before popping, especially when a closing parenthesis appears.
The final lesson compares representations in memory. Arrays use indices and may have fixed capacity or resizing behavior. Linked nodes use pointers and can grow node by node. The stack or queue rule stays the same while implementation details and operation costs change.
Draw empty stacks and queues, then trace small operation lists. Label a stack’s top and a queue’s front and rear after every step.
For every removal, state the returned value before updating the displayed structure. Check that stack removal takes the newest item and queue removal takes the oldest item.
Practice empty cases deliberately. Decide what pop, peek, dequeue, or front should return or report when no item exists.
Trace a fixed-capacity circular queue through enough enqueue and dequeue operations for the rear to wrap from the last array position back to index 0. Track front, rear, and size.
Use a short array to maintain a monotonic stack for next-greater values, then use a monotonic deque for a small sliding-window maximum. Record why each removed candidate can no longer matter.
Parse a short arithmetic expression containing +, -, *, /, and parentheses. Keep separate records for output and the operator stack. Then evaluate a simple postfix expression using a value stack.
Implement the same basic stack and queue behavior with an array and with linked nodes. For each version, identify which pointer or index changes during insertion and removal, and derive the time and storage cost from those changes.