Introduction
A Stack is a data structure that follows the LIFO (Last In First Out) principle. In other words : a data structure in which the element inserted at the last is the first element to come out.
Conversely, this also means that the first element put into the stack will always end up being the last one that goes out.
This limiting concept is extremely useful and makes it easy to manipulate structures representing those of our real world. For example, a stack may represent a stack of plates or books in which we can only remove / add each element to the top.
This structure is used all throughout programming. Here are some examples:
It can perfectly simulate a card game.
The Callstack refers to all function calls that happen during a program’s runtime. The call stack is indispensable to efficiently follow a program path. Note: a JS callstack generated by the use of H.urna Explorer.
Here is a Depth-First Search (or DFS) algorithm used to traverse a tree, which naturally describes itself recursively. Note : Recursive algorithms use the call stack to save their context. Understanding stacks will allow us to master recursive algorithms much more easily.
DFS, Depth-First Search, maze generation using a stack with H.urna Explorer.
History - undo - Ctrl+z : canceling a modification is carried out by keeping each of these changes in a stack.
Where Stack Overflow got its name. A “stack overflow” is what happens when we try to push an item on a full stack : it gets too big for the amount of memory allocated (cf. array implementation below).
Objectives
Operate a stack. Have a better understanding of recursion. Build our own stack structures. Put into practice arrays and linked lists. Understand the advantages / disadvantages of each implementation.
What is next?
If we have not seen the queues yet, this is the opportunity: they are implemented according to the FIFO principle (First-In-First-Out) inversely to the stacks.
We can now play with advanced algorithms such as the maze generation using a Deep Search (DFS). We may also continue with more advanced data structures such as: binary trees or hash tables.
Usage
We use C++ for code illustration, but no worries, other languages use the same logic and most often a similar syntax.
A stack is used for the following two main operations:
void push(const T& data); // Add new element on the top of the stack void pop(); // Remove element from the top of the stack
The following features are added to properly use a stack:
bool empty() const; // Check if stack is empty const T& top() const; // Seek the element on the top of the stack.
Example
stack< string > history; // Initialize stack
history.push("paste"); // ["paste"]
history.push("turn"); // ["paste", "turn"]
history.pop(); // ["paste"]
history.top(); // --> "paste"
history.push("color"); // ["paste", "color"]
history.push("clean"); // ["paste", "color", "clean"]
// Get drawing history from the last action
while (!history.empty()) {
auto current = history.top();
history.pop();
}
Build our owns
Cool, now that we know what a stack is, the question remains: how to build one? Good news! The answer is: pretty easy. Below we will look at implementations based upon arrays and linked lists in order to decide which best suits our case.
Note: the Stack is an abstract data structure. The definition of their structure is solely based on their behavior and not the underlying implementation. This is in contrast to more fundamental data structures, such as arrays and linked lists, which have strict requirements for how the storage of their data is implemented.
Linked List implementation
The basic linked list implementation is one of the easiest stack implementations we can do. Let's take back the skeleton of our structure seen in the 'linked list' course.
template < typename T >
class Stack
{
public:
Stack() : head(nullptr) {} // Construct as an empty stack
~Stack() { ... } // Destructor (same as linked list)
private:
// Node structure declaration
struct Node
{
// Constructor
Node(const T& data) : data(data), next(nullptr) {}
T data; // Value
Node* next; // Pointer to the next node
};
Node* head; // Pointer on the first element (also the top of the stack)
}
When we want to add something to the stack (Push), we just need to add it to the beginning of the list (the top of our stack). But wait... that's exactly what PushFront does, doesn't it?
void Push(const T& data)
{
Node* newNode = new Node(data); // Allocate memory
newNode->next = head; // Set the next node to be the head
head = newNode; // Set head to the new node
}
For the Pop operation, nothing is easier: just delete the first item in the list.
void Pop()
{
if (!head) // Empty stack error
return;
auto tmp = head; // Get the current top
head = head->next; // Set the head to point to the next node
delete tmp; // Delete the node
}
The Empty and Top functions are also trivial.
bool Empty() const { return (head) ? false : true; }
const T& Top() const
{
if (!head); // Throw Exception
return *head;
}
The above implementation gives you the ideas involved, and any optimization may be accomplished by modifying the linked list code.
Array implementation
Using a table implementation for a stack is a simple approach and only involves keeping the count.
template < typename T >
class Stack
{
public:
// Allocate/Deallocate stack memory
Stack(const int size) : count(0), max_size(size) { stack = new T[max_size]; }
~Stack() { delete[] stack; }
private:
int count; // Keep track of current stack size (and therefore the top index)
const int max_size; // Keep track of the max size to check if full
T* stack; // Pointer on the array
Stack(); // Forbid default constructor
}
To add something to the stack (Push), we just have to put it at the count index and increment the count.
void Push(const T new_data) {
if (count == max_size) // Stack overflow exception
stack[count] = new_data; // Set data
++count; // Update count
}
For the Pop function, nothing is easier: we just decrements the index.
void Pop()
{
if (count == 0) // Empty stack error
return;
--count; // Change top index
}
The Empty and Top functions are also still trivial.
bool Empty() const { return count == 0; }
const T& Top() const { return stack[count]; }
Stack Overflow !
That's what happens if we try to add an item to a full stack.
A stack overflow occurs if the call stack pointer exceeds the stack bound. The call stack may consist of a limited amount of address space, often determined at the start of the program.
In the case of the call stack this will happen if we have an infinite loop / recursion. (a fairly common bug!)
Dynamic Array (Vector) implementation
If we were using a dynamic implementation then when our top index reaches the capacity index, we simply double the size of the stack. This implies a loss of performance because it requires memory allocation as well as a copy of all the elements.
In short
Linked List Insert and delete operations in O(1). Can grow dynamically. Memory allocation/deallocation required for Insert and Delete operations. Slightly more memory usage due to additional storage of pointers.
Array Insert and delete operations in O(1). Can not grow dynamically: it requires a maximum size at initialization. An oversized table causes amount of wasted memory. Possible stack overflow problem.
Dynamic Array (Vector) Insert and delete operations in O(1) (except on resize). Can grow dynamically. Resize operation in O(n). An oversized table causes amount of wasted memory.