# 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 thefirst element putinto the stack will always end up being thelast 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:

# 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 anabstract data structure. The definition of their structure is solely based on their behaviour 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 modifiying 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 decrement 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!)

### Dynamique 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.

Dynamique 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.