Stacks, Queues, and Linked Structures · Linear ADTs

Queue

Queues use first-in, first-out access and model waiting lines, scheduling, buffering, and breadth-first traversal.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

Students learn queues as both a data structure and a modeling tool.

Guided Lesson Notes

Understanding Queue

Queue focuses on restricted access order and how items enter, wait, move, or leave a structure. Queues use first-in, first-out access and model waiting lines, scheduling, buffering, and breadth-first traversal.

Model: draw the structure as a line of items and mark the only legal places where an operation can touch it.

Invariant: after each operation, the front, back, top, head, tail, or current pointer must still describe the true structure.

Implementation: a small set of operations such as push, pop, peek, enqueue, dequeue, insert, remove, and traversal.

Use Queue when the problem mentions undo, matching, next greater value, waiting order, recent history, or processing items in arrival order.

Visual Model

A small picture for Queue

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

Key Ideas

FIFO ordering
Enqueue and dequeue
Front and rear state

Practice Prompts

Simulate a service line with arrivals and departures.
Trace queue state after a sequence of operations.

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 Queue

Trace a small input, focusing on fifo ordering.

1Write a small input where Queue is clearly useful.
2Label the part of the input related to FIFO 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

Queue interview problem: Shortest Path in a Binary Grid

Interview medium

Problem

Given a grid where 0 means open and 1 means blocked, find the fewest cells in a path from the top-left cell to the bottom-right cell using four-direction movement.

Input

The first line contains n and m. The next n lines contain m values, each 0 or 1.

Output

Print the shortest path length in cells, or -1 if no path exists.

Sample Input

Sample Output

Why the sample works

One shortest path visits six cells from the upper-left corner to the lower-right corner.

Approach

1A shortest unweighted path is a breadth-first search problem.
2Push the start cell with distance 1.
3Visit each open neighbor once and store its distance.
4The first time the target is popped, its distance is optimal.

O(nm) time and O(nm) 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 m = sc.nextInt();
    int[][] grid = new int[n][m];
    for (int r = 0; r < n; r++) {
      for (int c = 0; c < m; c++) {
        grid[r][c] = sc.nextInt();
      }
    }

    if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) {
      System.out.println(-1);
      return;
    }

    int[][] dist = new int[n][m];
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    Queue<int[]> q = new ArrayDeque<>();

    dist[0][0] = 1;
    q.add(new int[] {0, 0});

    while (!q.isEmpty()) {
      int[] cur = q.remove();
      int r = cur[0];
      int c = cur[1];

      if (r == n - 1 && c == m - 1) {
        System.out.println(dist[r][c]);
        return;
      }

      for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
        if (grid[nr][nc] == 1 || dist[nr][nc] != 0) continue;
        dist[nr][nc] = dist[r][c] + 1;
        q.add(new int[] {nr, nc});
      }
    }

    System.out.println(-1);
  }
}

Python Solution

from collections import deque

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

if grid[0][0] == 1 or grid[n - 1][m - 1] == 1:
    print(-1)
else:
    dist = [[0] * m for _ in range(n)]
    dist[0][0] = 1

    answer = -1
    q = deque([(0, 0)])
    while q:
        r, c = q.popleft()
        if r == n - 1 and c == m - 1:
            answer = dist[r][c]
            break
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 0 and dist[nr][nc] == 0:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))

    print(answer)

Practice Challenge

Make the idea your own

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

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free Session Text Us Open Online Compiler