Stacks, Queues, and Linked Structures · Linear ADTs

Stack

Stacks use last-in, first-out access. Students connect push, pop, and peek to call stacks, undo history, and expression processing.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

We connect stacks to recursion so students see the same idea in two forms.

Guided Lesson Notes

Understanding Stack

Stack focuses on restricted access order and how items enter, wait, move, or leave a structure. Stacks use last-in, first-out access. Students connect push, pop, and peek to call stacks, undo history, and expression processing.

The mental model is this: draw the structure as a line of items and mark the only legal places where an operation can touch it. That picture matters because it tells the student what information is available immediately and what must be searched, stored, or recomputed.

The core invariant is that after each operation, the front, back, top, head, tail, or current pointer must still describe the true structure. If a solution cannot state that rule, the code may still run on a sample input but fail on edge cases.

A strong implementation usually uses a small set of operations such as push, pop, peek, enqueue, dequeue, insert, remove, and traversal. The goal is not just to memorize an API; the goal is to know why each operation is allowed and what it costs.

In competitive programming, Stack tends to appear when the problem mentions undo, matching, next greater value, waiting order, recent history, or processing items in arrival order. Spotting that signal is often the difference between a nested-loop solution and an efficient one.

Visual Model

A small picture for Stack

front->A->B->C->back

Key Ideas

LIFO ordering
Push, pop, and peek
Stack underflow checks

Practice Prompts

Build a balanced-parentheses checker.
Use a stack to reverse a sequence without indexing.

Vocabulary

Terms students should be able to say clearly

Top or front

The item that will be removed or inspected next.

Push or enqueue

An insertion operation with a rule about where the item goes.

Pop or dequeue

A removal operation with a rule about which item leaves.

Underflow

Trying to remove an item from an empty structure.

Pointer

A reference that connects nodes or tracks a position.

Traversal

Walking through items in the only order the structure allows.

Worked Example

Worked example: tracing Stack

Use a tiny input and focus on lifo ordering. The goal is to see how the topic changes state before scaling it to a full problem.

1Write a small input where Stack is clearly useful.
2Label the part of the input related to LIFO ordering.
3Perform one operation and explain which invariant is still true afterward.
4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Push/enqueue at supported end	O(1)	Stacks and queues are designed around restricted end operations.
Search for a value	O(n)	Finding an arbitrary item usually requires traversal.
Reference update	O(1)	Linked structures can change local links quickly once the position is known.

Common Mistakes

What to watch while practicing

Coding before drawing the structure or state changes.
Forgetting the invariant that makes the algorithm correct.
Testing only the sample input and skipping boundary cases.
Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Stack interview problem: Days Until a Warmer Temperature

Interview medium

Problem

For each day, report how many days must pass until a warmer temperature appears. If no warmer day exists, report 0.

Input

The first line contains n. The second line contains n temperatures.

Output

Print n integers, one answer per day.

Sample Input

8
73 74 75 71 69 72 76 73

Sample Output

1 1 4 2 1 1 0 0

Why the sample works

Day 2 with temperature 75 waits four days until temperature 76 appears.

Approach

1Keep a stack of indices whose warmer day has not been found.
2When the current temperature is warmer than the stack top, resolve that earlier day.
3Push the current index after all smaller temperatures are resolved.
4Unresolved indices remain 0.

O(n) time and O(n) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] temp = new int[n];
    for (int i = 0; i < n; i++) temp[i] = sc.nextInt();

    int[] answer = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
      while (!stack.isEmpty() && temp[i] > temp[stack.peek()]) {
        int prev = stack.pop();
        answer[prev] = i - prev;
      }
      stack.push(i);
    }

    for (int i = 0; i < n; i++) {
      if (i > 0) System.out.print(" ");
      System.out.print(answer[i]);
    }
    System.out.println();
  }
}

Python Solution

n = int(input())
temp = list(map(int, input().split()))

answer = [0] * n
stack = []

for i, value in enumerate(temp):
    while stack and value > temp[stack[-1]]:
        prev = stack.pop()
        answer[prev] = i - prev
    stack.append(i)

print(*answer)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Stack: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Turn the topic into usable problem-solving skill

Students can use this page before a lesson, after a difficult homework assignment, or while preparing for AP Computer Science A extensions, Advanced Topics in CS, USACO growth, or a college data structures course.

Schedule Free Consultation Text Us Open Online Compiler