Use a stack, queue and linked list to store data

10.4 Introduction to Abstract Data Types (ADT)

An Abstract Data Type (ADT) defines a data structure purely by the operations that can be performed on it and the mathematical properties of those operations. The implementation details (e.g., arrays, linked nodes) are hidden from the user.

Key ADTs Covered

• Stack
• Queue
• Linked List

1. Stack

A stack follows the Last‑In‑First‑Out (LIFO) principle. The primary operations are:

• push(x) – add element x to the top.
• pop() – remove and return the top element.
• peek() – view the top element without removing it.
• isEmpty() – test whether the stack contains no elements.

Typical use‑cases include expression evaluation, back‑tracking algorithms, and function call management.

2. Queue

A queue follows the First‑In‑First‑Out (FIFO) principle. Core operations are:

• enqueue(x) – add element x to the rear.
• dequeue() – remove and return the front element.
• front() – view the front element without removing it.
• isEmpty() – test whether the queue is empty.

Queues are used in scheduling, breadth‑first search, and buffering data streams.

3. Linked List

A linked list consists of nodes, each containing data and a reference (link) to the next node. Variants include:

• Singly linked list – each node points to the next node only.
• Doubly linked list – each node points to both next and previous nodes.
• Circular linked list – the last node links back to the first.

Common operations:

• insert(pos, x) – insert element x at position pos.
• delete(pos) – remove element at position pos.
• search(x) – locate the first occurrence of x.
• traverse() – visit each element in order.

Comparison of Stack, Queue and Linked List

Example: Storing Data Using Each ADT

Suppose we need to store the sequence of integers entered by a user and later retrieve them in reverse order.

1. Using a Stack

   • For each input n, execute stack.push(n).
   • When retrieval is required, repeatedly call stack.pop() until the stack is empty.
   • This automatically yields the numbers in reverse order.

2. Using a Queue

   • Enqueue each input: queue.enqueue(n).
   • To obtain the original order, dequeue repeatedly.
   • To obtain reverse order, first transfer all elements to a stack, then pop from the stack.

3. Using a Linked List

   • Insert each new element at the head: list.insert(0, n). This builds the list in reverse order directly.
   • Alternatively, insert at the tail to preserve input order, then traverse the list backwards (possible only with a doubly linked list).

Mathematical Representation

The abstract behaviour of a stack can be expressed as:

\$\text{push}(S, x) = S \cup \{(top+1, x)\}\$

\$\$\text{pop}(S) = \begin{cases}

(S', x) & \text{if } S = S' \cup \{(top, x)\} \\

\text{error} & \text{if } S = \emptyset

\end{cases}\$\$

Similarly, a queue’s enqueue operation can be described by:

\$\text{enqueue}(Q, x) = Q \cup \{(rear+1, x)\}\$

Summary

Understanding ADTs allows you to choose the most appropriate data structure for a given problem, focusing on the operations required rather than the underlying implementation. Stacks, queues, and linked lists each provide distinct access patterns and performance characteristics, making them fundamental tools in algorithm design.