Stack in an important Data Structure. It is part of problems in Technical Interviews and useful in Functional Programming and Development. This Blog will introduce you to Stack and provide its implementation in C++ and basic operations you can perform to manipulate data through it.

Introduction to Stack

Stack as Abstract Data Type (ADT)

In this section let’s understand Stack as an ADT or Abstract Data Structure. This basically means we’ll only look at the features and operations and understand implementation in later sections. So we are only defining the data structure here as a mathematical or logical model.

A stack as a Data Structure is not very different from a Stack of things in the real world. Here are a few examples of Stack of real-world objects:

Applications of Stack in real-world

Stack at its core is a collection of any entity with a property that we must insert and remove elements from the same end. We call this end the Top of the Stack.

This property can also be also a constraint or limitation of using Stack. We can only access the Top of the Stack. Any item we want to insert or remove is done from the Top.

A Stack is a Last In First Out (LIFO) collection. The most recently added data item has to go out first.

Operations of Stack

Formally we can define a Stack as a List or collection with a restriction that insertion and deletion can only be done from one end which we call the Top of the stack.

There are two fundamentals available with a stack:

1. Push(code_damn): An insertion of a data element into the stack is called a push operation. In this case, it will insert code_damn into the stack.

2. Pop(): A deletion of the most recently added data element from the stack is called a Pop operation.

Push and Pop are the fundamental operations but there can be more.

• Top(): This operation simply returns the element at the Top of the Stack.

• isEmpty(): This operation is used to check if the stack is empty or not. It returns a boolean true if it is and false if it is not empty.

All the above operations take constant time. This means that the time complexity of each of these operations is O(1).

The logical view of Stack

Logically, we can represent a stack as a three-sided figure i.e. as a container. Let’s take an example and call our stack “codeDamnStack”. It represents a stack of integers and it is initially empty.

Here we are adding a few elements to our Stack using the push operation.

Push Operation in Stack

If we use top() operation now, it will return 5. Now that we have a Stack let’s remove the top element using the Pop operation.

Pop Operation in Stack

If we use the top() operation now, it will return 23.

Implementation of Stack

Implementation of Stack is quite similar to List but we just have to add one extra property and that is restricting the insertion and deletion of elements from one end.

There are two popular ways of implementing a List. we’ll see the Stack implementation using both of them:

1. Using Array

2. Using Linked List

Array Implementation of Stack

To understand array implementation, we are taking an example. We have an array of integers named learn_stack.

int learn_stack[10];
top = -1;

• To create a stack using Arrays, we create two functions push and pop to insert and remove an element respectively.

• The value of Top in an empty array is -1. Each time we insert an element, we increase the top by 1 and assign the element to the index Top.

push(int x){
  top = top + 1;
  learn_stack[top] = 1;
}

• To pop an element from a stack, we just need to decrease the top by one. We don’t need to reset the value of the index we are popping since that element is not part of the Stack.

pop(){
  top = top - 1;
}

We can only push an element in Stack only until when the array is not full. There can be a situation where the stack consumes the entire array. so the Top will be equal to the highest index in the array.

A further push will not be possible because it will result in an overflow. To avoid an overflow we can create a large enough array but for that, we have to be reasonably sure that the stack will not grow beyond a certain limit.

Push Function can check overflow and it can throw an error if it happens. This will not be good behaviour. Instead, we can use the concept of dynamic arrays.

This means that during the case of overflow, we can create a new larger array and copy the content of the stack from the older array into this new array and possibly delete the old array if we can. The cost or time complexity of copying an array will be O(n)

The size of the new array will be twice the size of the new array and the time complexity of the new push operation will be:

1. O(1) for best case

2. O(n) for the worst case

3. O(1) for average case

Here is the array implementation of Stack in C++

#include<bits/stdc++.h>
using namespace std;

#define MAXIMUM_INT 101
int exampleArray[MAXIMUM_INT];
int top = -1;

// push function to insert an element into stack
void pushElement(int x){
    if (top == MAXIMUM_INT - 1){
        cout<<"STACK OVERFLOW";
        return;
    }
    top++;
    exampleArray[top] = x; 
}

// pop function to remove element from stack
void popElement(){
    if (top == -1){
        cout<<" STACK IS STILL EMPTY";
        return;
    }
    top--;
}

// Top function to return the element at top of stack
int topElement(){
    return exampleArray[top];
}

bool isEmpty(){
    return (top == -1);
}

// Function to print all the element of Stack
void printStackElements(){
    cout<<"\nStack: ";
    for (int i=0; i<=top; i++){
        cout<<exampleArray[i]<<" ";
    }
}

// Main Function of Program
int main(){

    // Adding 2
    pushElement(2);

    // Adding 7
    printStackElements();
    pushElement(7);

    // Adding 13
    printStackElements();
    pushElement(13);
    printStackElements();

    // Adding 18
    pushElement(18);
    printStackElements();

    // Removing Top
    popElement();
    printStackElements();

    // Removing Top
    popElement();
    printStackElements();

    // Removing Top
    popElement();
    printStackElements();

    // Calling Top function 
    cout<<"\nTop Element is: "<<topElement();

    return 0;
}

Output:

Output

Linked List Implementation of Stack

A Linked List is a collection of entities called nodes. These nodes contain two fields. One to store data and the other to store the address of the next node.

The identity of the Linked List is the address of the first node, also known as the head node. A different variable stores the address of this first node. Usually, we name it head for convenience.

Unlike Arrays, Linked Lists are not of definite size and their elements are not stored in contiguous blocks of memory.

Before moving ahead we must know:

• the cost or time complexity of insertion and deletion in a Linked List is:

  • O(n) at end of the List

  • O(1) at beginning of the List

• The Top of the stack in this case is the head of the Linked List.

Here is the implementation of Stack using Linked List in C++:

// stack using singly Linked List
#include <bits/stdc++.h>
using namespace std;

// creating a linked list;
class Node {
public:
    int data;
    Node* link;

    // Constructor
    Node(int n)
    {
        this->data = n;
        this->link = NULL;
    }
};

class Stack {
    Node* top;

public:
    Stack() { top = NULL; }

    void pushElement(int data)
    {
        // Create new node temp
        Node* tempNode = new Node(data);

        // Check if the stack is overflow
        if (!tempNode) {
            cout << "\nStack Overflow";
            exit(1);
        }

        // Initialize data into temp data field
        tempNode->data = data;

        // Put top pointer reference into temp link
        tempNode->link = top;

        // Make temp as top of Stack
        top = tempNode;
    }

    // isEmpty function to check if function is empty
    bool isStackEmpty()
    {
        return (top == NULL);
    }

    // Top function to return top element in a stack
    int topElement()
    {
        // If stack is not empty , return the top element
        if (!isStackEmpty())
            return top->data;
        else
            exit(1);
    }

    // Pop Function to remove an element from Stack
    void popElement()
    {
        Node* tempNode;

        // Check for stack underflow
        if (top == NULL) {
            cout << "\nStack Underflow" << endl;
            exit(1);
        }
        else {

            // Assign top to temp
            tempNode = top;

            // Assign second node to top
            top = top->link;

            // This will automatically destroy
            // the link between first node and second node

            // Release memory of top node
            // i.e delete the node
            free(tempNode);
        }
    }

    // Function to print all the
    // elements of the stack
    void displayStackElements()
    {
        Node* tempNode;

        // Check for stack underflow
        if (top == NULL) {
            cout << "\nStack Underflow";
            exit(1);
        }
        else {
            cout<<"Stack: ";
            tempNode = top;
            while (tempNode != NULL) {

                // Print node data
                cout << tempNode->data;

                // Assign temp link to temp
                tempNode = tempNode->link;
                if (tempNode != NULL)
                    cout << "   ";
            }
        }
    }
};

// Driven Program
int main()
{
    // Creating a stack
    Stack exampleStack;

    // Push the elements to the stack
    exampleStack.pushElement(7);
    exampleStack.pushElement(23);
    exampleStack.pushElement(69);
    exampleStack.pushElement(98);

    // Printing stack elements
    exampleStack.displayStackElements();

    // Print top element of stack
    cout << "\nTop element is " << exampleStack.topElement() << endl;

    // Remove elements at the top of stack
    exampleStack.popElement();
    exampleStack.popElement();

    // Printing Stack Elements
    exampleStack.displayStackElements();

    // Print Top element of the stack
    cout << "\nTop element is " << exampleStack.topElement() << endl;

    return 0;
}

Output:

Output

Infix, Prefix and Postfix

Expressions

One of the most important and interesting applications of Stack data structure is in the evaluation of expressions.

• Expressions can have constants, variables and symbols that can be operators or parentheses.

• All these components must be arranged according to a set of rules.

• We should be able to parse and evaluate the expression according to these rules. Example of Expressions: 2 + 3, P – Q, (A * 2) etc

• The above examples have a common structure.

  • <operand> <operator> <operand>

  • operand by definition is the object on which the operation is performed.

  • The operator is the symbol that represents the operation to be performed.

  • Operand doesn’t have to be a constant or variable always. It can be an expression itself. For instance, in the expression (2 + 3) 4, is an operator and it has 2 operands i.e., the constant 4 and the expression (2+3).

Infix Notation

This way of writing the expression in which the operator is between the operands is Infix Notation. If there are multiple operators in an expression in this notation then they follow an operator precedence rule.

The order of Operation is as follows:

1. Parentheses: (), {}, []

2. Exponential: ^

   • It is applied right to left. For example, 2^3^2 will first evaluate to 2^9 and finally 512.

3. Multiplication and Division: *, /

   • It is applied from left to right.

4. Addition and Subtraction: +, –

   • It is applied from left to right.

while evaluating an expression in Infix form, we first need to compare the precedence of the operators and then check the associativity. The use of parentheses is very important since it explicitly tells us which operation we must perform first. It also improves the readability of the expression.

Prefix and Postfix Notation

Even though Infix Notation is the most common way of writing operations, it’s not easy to parse and evaluate an infix expression without ambiguity.

So mathematicians studied this problem and gave us two more ways of writing Infix expressions. They are parentheses-free and we can parse them without any ambiguity and don’t require any of the operator precedence or associativity rule.

Prefix Notation

Prefix Notation is also known as Polish Notation. In prefix notation, we place the operator before operands.

<operator> <operand> <operand>

Examples:

• 7 + 9 in Infix is +79 in Prefix.

• y – z in Infix is -yz in prefix.

• a + b c in Infix is +abc in Prefix.

Postfix Notation

Postfix notation is also known as reverse polish notation. In postfix notation, the operator is placed after the operands.

<operand> <operand> <operator>

Expressions in postfix notation are the easiest to parse and the least costly in terms of time and memory to evaluate, and that’s why this way actually invented.

Prefix notation can also take similar time and memory but the algorithm to parse and evaluate the postfix notation is really straightforward and intuitive. That’s why it is preferred for computation using machines.

Let’s take a comparative example of all three notations:

Infix vs Prefix vs Postfix

a + b c -> a + (b c) -> a + (b c ) -> a b c +

Evaluation of Prefix and Postfix expressions using stack

Postfix Evaluation

To understand how to convert an infix expression to postfix, let’s take an example: a b + c d – e

Infix to Postfix Conversion

The resultant Postfix expression is ab*cd*+e-

First, let’s see how we can evaluate the postfix expression manually: Again we’ll take the result of the above example to understand it.

In the expression ab*cd*+e-, let’s assign values to a, b, c, d and e:

a = 2, b = 3, c = 5, d = 4, e = 9

1. To evaluate the above expression, we need to scan the resultant postfix notation from left to right and find the first occurrence of the operator. In our example, it is *Multiplication is the first operator to appear.

2. For the first operator, the preceding two entities will always be operands. In postfix notation, the operands will always lie to the left of their operator.

   • You need to find the first occurrence of this pattern <operand> <operand> <operator> in the expression and now you can apply the operator on these two operands.

   • In our example, a and b are operands to apply the first occurrence of the * operator.

   • Repeat this sequential step of performing an operation on postfix notation until we get the final value.

Postfix Evaluation

Postfix Evaluation using Stack

Now that we know how things work manually, let’s understand how we can do the same using Stack.

Here is the pseudo-code for Postfix evaluation using stack:

// Function to evaluate Postfix Expression
evaluatePostfix(expression){

    // Stack to store characters in exxpression passed as string
    create a Stack s;

    // we will store only operands in the stack
    for (i = 0 to i = length(expression) - 1){
        if (expression[i] is operand){
            push(expression[i]);
        }

// When the operator occur, we will pop the
// last 2 added values, store them and perform
// the operation on them and push the new value
// to stack.
        else if(expression[i] is operator){
            op1 = pop(); // First Operand
            op2 = pop(); // Second Operand
            result = perform(expression[i], op1, op2);
            push(result);
        }
    }

    // At the end we will return top
    // as answer of expression
    return (Top of Stack)
}

Prefix Evaluation using Stack

Prefix evaluation works the same way as postfix. The only difference in the function is that we store the operands from right to left.

Here is the pseudo-code for prefix evaluation using stack:

// Function to evaluate Postfix Expression
evaluatePostfix(expression){

    // Stack to store characters in exxpression passed as string
    create a Stack s;

    // we will store only operands in the stack
    // and traverse from RIGHT TO LEFT
    for (i = length(expression) - 1 to i = 0){
        if (expression[i] is operand){
            push(expression[i]);
        }

// When the operator occur, we will pop the
// last 2 added values, store them and perform
// the operation on them and push the new value
// to stack.
        else if(expression[i] is operator){
            op1 = pop(); // First Operand
            op2 = pop(); // Second Operand
            result = perform(expression[i], op1, op2);
            push(result);
        }
    }

    // At the end we will return top
    // as answer of expression
    return (Top of Stack)
}Code language: C++ (cpp)

Infix to Postfix using Stack

We already know one way of converting infix expressions to postfix. The above example explains how to do it manually by applying operator precedence and, associativity rules.

Example: P + Q * R

1. P + ( Q * R )

2. P + ( QR* )

3. P Q R * +

Note: Here as you can see in the infix to postfix conversion, the position of operators and operands may change but the order in which the operand occurs from left to right does not change. The order of operators may change.

Here is the pseudo-code to convert infix to postfix using stack. We are assuming that there exists a class stack with all the basic operation functions like push, pop, empty and top.

// function to convert Infix to Postfix
infixToPostfix(expression){

// stack wil store only the operators
    Create a Stack s

// an empty string to parse operands
    Initialize result

    for (i = 0 to i = length(expression)-1){
        if (expression[i] is operand){
            result += expression[i]
        }

// If the character is operator then, we will check
// if it has higher precedence than operator at the top
// of stack. we will append it to result if it is true.
        else if (expression[i] is operator){
            while (!s.empty() && hasHigherPrecedence(s.top(),expression[i])){
                result += s.top()
                s.pop()
            }
            s.push(expression[i])
        }
    }

// there may be some unappended operators in the stack
// we will run a loop and add them all to result
    while (!s.empty){
        result += s.top()
        s.pop()
    }

// Return the result string containing the Postfix notation
    return result
}

Tree Traversal

Tree Traversal is basically iterating to each node of the tree so that we can perform the required operation on its’s data elements accordingly. One way to implement tree traversal is using a stack. A stack is a Last In First Out (LIFO) data structure that allows for the addition and removal of elements in a single end, called the top.

Tree Traversal can be done using 3 ways:

1. in-order

2. pre-order

3. post-order

In-order Tree Traversal

In-order tree traversal means that we first start by visiting the left node of the tree followed by the root node and right node respectively. The Algorithm is as follows:

1. Initialise an empty stack and push the root node to it.

2. Create a current node variable and set it to the root node.

3. While the current node is not null or the stack is not empty:

   1. If the current node has a left child, push the left child to the stack and set the current node to the left child.

   2. If the current node does not have a left child, pop the top element from the stack and visit it. Then, set the current node to its right child.

   3. If the current node has no left or right child, set it to null.

Pre-order Tree Traversal

Pre-order tree traversal means that we first start by visiting the root node of the tree followed by the left node and right node respectively. The Algorithm is as follows:

1. Create an empty stack and push the root node to it.

2. Create a current node variable and set it to the root node.

3. While the stack is not empty:

   1. Pop the top element from the stack and visit it.

   2. If the current node has the right child, push it to the stack.

   3. If the current node has a left child, push it to the stack.

Post-order Tree Traversal

Pre-order tree traversal means that we first start by visiting the left node of the tree followed by the right node and root node respectively. The Algorithm is as follows:

1. Create an empty stack and push the root node to it.

2. Create a current node variable and set it to the root node.

3. Create a last visited node variable and set it to null.

4. While the stack is not empty:

   1. Set the current node to the top element of the stack.

   2. If the current node has a left child and the last visited node is not the left child, push the left child to the stack and set the current node to the left child.

   3. If the current node does not have a left child or the last visited node is the left child, push the right child to the stack if it exists.

   4. If the current node does not have a left or right child, visit it and set the last visited node to the current node.

Sorting Algorithms

Sorting basically means organizing data using a certain property. In terms of simple arrays, we can sort their elements using storing them in stacks.

It is similar to how we stored characters in the stack during expression evaluation and conversion and popped them out by comparing the recently pushed data element.

A few of the Sorting Algorithms that can be implemented using the stack are:

1. Insertion Sort

2. Selection Sort

3. Merge Sort

Tower of Hanoi

The Tower of Hanoi is a Logical puzzle. It states that we are given three rods and multiple disks of different sizes which can be mounted around any of the given three rods.

Tower Of Hanoi Puzzle

All the disks are arranged in descending order from the base with the largest at the bottom and the smallest disk at the top. The puzzle is for us to shift these disks to other rods while following the rules given here:

• Only one disk can be moved at a time.

• Each move consists of taking the uppermost disk from one of the rods and placing it on top of another rod, or on an empty rod.

• No disk may be placed on top of a smaller disk.

Although there are multiple ways to solve this problem like recursion etc. But we can solve it using stack too.

Here is the Code to solve TOI using Stack. Here we are using the unbuilt Stack using C++ STL.

// Power Of Hanoi using Stack
#include <bits/stdc++.h>
#include <stack>

using namespace std;

// This function transfers one disk to another.
// it uses 3rd Disk as Temporary Host to keep them
void transferDisks(stack<int> &src, stack<int> &target, stack<int> &temp, int n)
{
    // If the rod has no disk then program ends
        if (n == 0)
        return;

    // Move n-1 disks from the source rod to the auxiliary rod
    // using the target rod as an auxiliary
    transferDisks(src, temp, target, n - 1);

    // Move the n-th disk from the source rod to the target rod
    target.push(src.top());
    src.pop();

    // Move the n-1 disks from the auxiliary rod to the target rod
    // using the source rod as an auxiliary
    moveDisks(temp, target, src, n - 1);
}

int main()
{
    // Create three stacks to represent the rods
    stack<int> src, target, temp;

    // Initialize the source rod with the disks
    // in ascending order of size, with the smallest
    // at the top
    for (int i = 5; i >= 1; i--)
        src.push(i);

    // Move the disks from the source rod to the target rod
    moveDisks(src, target, temp, 5);

    // Print the disks on the target rod
    while (!target.empty())
    {
        cout << target.top() << " ";
        target.pop();
    }

    return 0;
}

Conclusion

We can implement using both arrays and Linked List. It has many applications like conversion of infix to prefix and postfix notation and their evaluation. It is also functional in the execution of Function calls and recursion because recursion is also a chain of function calls.

We can do any undo operation in any text editor, we can implement this using a stack. A compiler verifies whether the parentheses are balanced in the code or not using the stack. Moving ahead, You must practice programming problems on Stack to understand how to implement it yourself accordingly.