Pancakes & Bus Queues – Linear Data Structures.

As part of my ongoing learning and revision, today, I’m diving into the world of stacks and queues. These are two linear data structures that play a significant role in organizing and managing data in computer programs.

We’ll keep this short and sweet. An 80/20 if you will.

Let’s get started.

Stacks.

Imagine a stack of pancakes, with each pancake representing an item in your data structure. To add a pancake, you’d place it on top of the stack, and to remove one, you’d lift the top pancake.

Stacks work in the same way – they follow the Last-In-First-Out (LIFO) principle, where the most recent item added is the first to be removed.

Let’s break down the basic stack operations to uncover its secrets:

1. Push: Pile on a new pancake (add an item to the top of the stack).
2. Pop: Remove the top pancake (take off the top item).
3. Peek/Top: Sneak a peek at the top pancake (view the top item without removing it).

By understanding LIFO and basic stack operations, it allows you to explore some of the most appetizing applications of stacks, like evaluating arithmetic expressions, managing function calls, and navigating through graphs with depth-first search. (The latter I’m yet to experiment with).

Queues.

Now picture a line of people waiting for a bus. New people join at the end of the line, while those at the front board the bus and leave. Queues in computer science follow this same idea, operating under the First-In-First-Out (FIFO) principle, where the first item added is the first to be removed.

Time to dive into the core queue operations:

1. Enqueue: Join the line (add an item to the rear of the queue).
2. Dequeue: Board the bus (remove the front item from the queue).
3. Front: Check who’s first in line (view the front item without removing it).

With the FIFO principle and basic queue operations under our belt, it’s possible to tackle some cool queue applications, such as managing tasks in a first-come-first-served manner, exploring graphs with breadth-first search, and buffering data in communication systems.

Thanks for reading.

T3B