Stack and Queue Basics

date2026-07-14document_iddoc_8f494f7c9e0522ea22b8df5937f1940cdescriptionスタックとキューを抽象データ型として定義し、操作契約、実装、計算量、DFSとBFSへの接続を説明する。prerequisites計算量の基本 / 配列の基本操作 / 抽象データ型と実装の区別type講義statusactive

algorithmdata-structuresundergraduatelecture

data/lecture/information/algorithm/data-structures/data-structures-portal.lecture.n.md

1Introduction

This lecture defines stacks and queues as abstract data types and explains their operation contracts, behavior on empty structures, representative implementations, and complexity. It then shows how their removal orders determine the traversal order of DFS and BFS.

2Stack contract

A stack is a last-in, first-out (LIFO) ADT: the most recently inserted element is removed first. Its basic operations are as follows.

push(x) inserts $x$ at the top.
pop() removes and returns the top element.
top() returns the top element without removing it.
isEmpty() reports whether the number of elements is zero.

The contract must specify the result of applying pop() or top() to an empty stack. In this lecture, either operation on an empty stack violates a precondition, and the caller must prevent it with isEmpty().

After push(a), push(b), and pop(), in that order, pop() returns $b$ and $a$ remains.

3Queue contract

A queue is a first-in, first-out (FIFO) ADT: the earliest inserted element is removed first. The insertion side is the rear, and the removal side is the front.

enqueue(x) inserts $x$ at the rear.
dequeue() removes and returns the front element.
front() returns the front element without removing it.
isEmpty() reports whether the number of elements is zero.

Applying dequeue() or front() to an empty queue also violates a precondition. After enqueue(a), enqueue(b), and dequeue(), in that order, dequeue() returns $a$ and $b$ remains.

4Implementations and complexity

A stack can use the end of a dynamic array as its top. With geometric capacity growth, push takes amortized $O (1)$ time, while pop, top, and isEmpty take worst-case $O (1)$ time. A fixed-capacity array requires the contract to specify behavior when the array is full.

A queue can use a circular array with front and rear indices or a linked list with references to both ends. In a fixed-capacity circular array, all operations take worst-case $O (1)$ time if enqueue requires that the array is not full. In a circular array whose capacity grows geometrically, enqueue takes amortized $O (1)$ time but $O (n)$ time in a resizing operation. In a linked list, all operations take worst-case $O (1)$ time under a computational model in which allocating one node takes $O (1)$ time. In contrast, an ordinary array implementation that shifts every element left after each dequeue takes $O (n)$ time. Thus, an $O (1)$ bound belongs to a chosen implementation, not to the ADT itself.

Both structures require $O (n)$ space to store $n$ elements.

5Connection to DFS and BFS

Depth-first search (DFS) manages discovered but unprocessed vertices with a stack. Prioritizing the most recently added candidate continues traversal in one direction before backtracking. In a recursive implementation, the function-call stack serves this purpose.

Breadth-first search (BFS) manages candidate vertices with a queue. Processing earlier discoveries first makes traversal levels from the start vertex nondecreasing. This FIFO order supports the shortest-distance property of BFS in an unweighted graph.

data/lecture/information/algorithm/search/dfs-and-bfs-basics.lecture.n.md

6Summary

A stack is a LIFO ADT, and a queue is a FIFO ADT.
The contract must specify behavior of removal and access operations on an empty structure.
Operation complexity depends on the concrete implementation.
DFS manages candidates with a stack, whereas BFS uses a queue.