Algorithms C++ Edition (2015)

Part 1: Identifying the Data Types

Chapter 1a: Abstract Data Types: The Stack

The Stack

A stack is literally what it is - a stack of objects.

And as an abstract Data Type, the stack would hold a list of data objects for later processing.

The data objects in a stack would be inserted and retrieved in a Last-In-First-Out process.

A Stack will usually have two main functions defined along with it: push (aka insert) and pop (aka remove/retrieve).

How the Stack Works

Think of a stack as a pile of plates “stacked” on top of one another. And each plate had a letter in it. The top plate would be the easiest to retrieve.

So retrieving a data object from a Stack would be the last object that was entered.

For example, let’s have a ‘stack’ of dishes as an array:

// stackOfPlates are a collection of strings

// Each string resembles a Plate

string stackOfPlates[5] = {“A”, “B”, “C”, “D”}

If you wanted to insert a new plate in this stack, it would be placed at the end of the list.

Now, for example, let’s take a look at this stack:

string stackOfPlates[5] = {“A”, “B”, “C”, “D”}

Then, let’s enter a plate called “E”. To enter items into a stack, you need a function to insert it into the stack. This function is usually called push().

stackOfPlates.push(“E”)

Afterwards, here’s what the stack would look like:

string stackOfPlates[5] = {“A”, “B”, “C”, “D”, “E”}

If we wanted to retrieve a plate from this stack, the LAST item in the collection would be removed from the stack. Then that item would be given. You need a function to remove and retrieve an item from the stack. This function is called pop().

// This would print E

print(stackOfPlates.pop())

// This would print D

print(stackOfPlates.pop())

// This would print C

print(stackOfPlates.pop())

Then, here’s what the stack would look like afterwards:

string stackOfPlates[5] = {“A”, “B”}

When to Use the Stack

Carefully look at how a list of data objects should be processed. Once you notice it uses a Last-In-First-Out process for any data objects that enter or leave, use a stack.

Also, complex algorithms and functions use stacks. If a computer processes a procedure as a stack, it will “stack” all the functions that are called. Then it will proceed to complete each function called, starting with the most recent (you’ll learn more about all this in-depth later).

For future reference, picture yourself in a tech interview. If you ever are asked how a certain function’s procedure works, you’ll be very fortunate to know how a stack works and how that function will proceed from start to finish.

However, recall that stacks normally use lists - either arrays or linked lists. So which one do you choose? Recall these lines from the Master’s Handbook Series:

Linked Lists = any size, faster add & remove

Arrays = fixed size, faster access/process

So depending on which data structure you use, the next chapters show you how you implement a stack.