Introduction to Stack Data Structure (Operations and Implementation)

What is stack data structure?

A stack is considered to be a linear data structure because it is based on the principle of Last In First Out (LIFO). In a stack, elements are added and removed from the same end, called the top of the stack. The last element added to the stack is the first one to be removed, creating a linear order of elements.

The name "stack" comes from the idea of a pile of objects, like a stack of plates in a cafeteria. In a cafeteria, plates are added to the top of the stack as they are cleaned and placed back on the shelf. When a plate is needed, it is taken from the top of the stack. The first plate that was placed on the stack will be the last one to be used.

• If we want to access an item that is deeper in the stack, we may need to remove the items that are on top of it first. For example, if we have a stack of books and we want to get to a book that is near the bottom of the stack, we will need to remove the books on top of it first.
• When all of the items are removed from a stack, they will be accessed in reverse chronological order. This means that the first item we remove will be the one that was most recently added to the stack, and the last item we remove will be the one that has been in the stack the longest.

Key operations on stack data structure

Stack supports two primary operations: push and pop. When we add an element to the top of the stack, it is called a push operation. When we remove an element from the top of the stack, it is called a pop operation.

• void push(x): Add element x to the top of the stack. Adding an element onto a full stack will cause a stack overflow error.
• int pop(): Remove the top element from the stack. Popping an element from an empty stack will cause a stack underflow error.

In addition to push and pop, several other operations are supported by stack data structures:

• int peek(): Access the top element from the stack. This operation allows us to look at the top element without modifying the stack.
• int size(): Return the total number of elements in the stack.
• boolean isEmpty(): Return true if the stack is empty.
• boolean isFull(): Return true if the stack is full.

Array implementation of stack structure

It is possible to implement a stack data structure using an array. To do this, we can define a class called StackArray that provides access to a set of methods that implement stack operations. Users can call these methods from outside the class using an object of the StackArray class. This is an example of encapsulation and abstraction, as we are hiding the implementation details of the stack from the outside world and only providing access to the operations that can be performed on it.

We declare three private attributes inside the StackArray class:

• stack: a pointer to an array that stores elements in the stack
• top: a variable that keeps track of the top element in the stack
• capacity: a variable that represents the maximum number of elements the stack can hold

The StackArray class has several public member methods:

StackArray(int size): this is the constructor for the StackArray class. It takes an integer size as an argument, which represents the capacity of the stack. The constructor initializes the stack array, sets the capacity to size, and sets the top to -1 to indicate that the stack is empty.

StackArray(int size) 
{
    Stack = new int[size];
    capacity = size;
    top = -1;
}

void push(int x): this method adds an element x onto the top of the stack. If the stack is full, it prints an error message and returns. Otherwise, it increments top by 1 and places the element at the top of the stack.

void push(int x) 
{
    if (isFull() == true) 
    {
        cout << "Stack is full! Cannot add " << x << " to stack." << endl;
        return;
    }

    top = top + 1;
    Stack[top] = x;
}

int pop(): this method removes the top element from the stack and returns it. If the stack is empty, it prints an error message and returns INT_MIN.

int pop() 
{
    if (isEmpty() == true) 
    {
        cout << "Stack is empty! Cannot pop from stack." << endl;
        return INT_MIN;
    }

    int temp = Stack[top];
    top = top - 1;
    return temp;
}

int peek(): this method returns the top element of the stack without removing it. If the stack is empty, it prints an error message and returns INT_MIN.

int peek() 
{
    if (isEmpty() == true) 
    {
        cout << "Stack is empty!" << endl;
        return INT_MIN;
    }

    return Stack[top];
}

int size(): this method returns the number of elements in the stack.

bool isEmpty(): this method returns true if the stack is empty, and false otherwise.

bool isFull(): this method returns true if the stack is full, and false otherwise.

int size() 
{
    return top + 1;
}

bool isEmpty() 
{
    if(top == -1)
        return true;
    else 
        return false
}

bool isFull() 
{
    if(top == capacity - 1)
        return true 
    else 
        return false
}

Stack using array implementation code C++

class StackArray 
{
 private:
    int *Stack;
    int top;
    int capacity;

 public:
    StackArray(int size) 
    {
        Stack = new int[size];
        capacity = size;
        top = -1;
    }

    void push(int x) 
    {
        if (isFull()) 
        {
            cout << "Stack is full! Cannot add " << x << " to stack." << endl;
            return;
        }

        top = top + 1;
        Stack[top] = x;
    }

    int pop() 
    {
        if (isEmpty()) 
        {
            cout << "Stack is empty! Cannot pop from stack." << endl;
            return INT_MIN;
        }

        int temp = Stack[top];
        top = top - 1;
        return temp;
    }

    int peek() 
    {
        if (isEmpty()) 
        {
            cout << "Stack is empty!" << endl;
            return INT_MIN;
        }

        return Stack[top];
    }

    int size() 
    {
        return top + 1;
    }

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

    bool isFull() 
    {
        return top == capacity - 1;
    }
};

One advantage of using an array to implement a stack is that it is relatively simple to set up. Additionally, because it does not require the use of pointers, it can be more memory-efficient. However, there are also some downsides to this approach. For example, the stack is not dynamic, so it cannot change its size at runtime to meet changing needs. This means that the total size of the stack must be defined beforehand.

Dynamic array implementation of stack

The array implementation of a stack has a fixed size, which can be a critical limitation. To address this issue, we can use a dynamic array instead. When the stack is full, we can increase its capacity by resizing the array to double its original size.

This is a StackDynamicArray class that implements a stack data structure using an array with dynamic resizing. In this class, we have added resizeStack() method and modified void push(int x) method.

void resizeStack(): this is a private method that increases the capacity of the stack array by a factor of 2. It creates a new array called temp with 2 * capacity elements, copies the elements from stack to temp, and then deletes the stack array. Finally, it sets the stack array to temp and updates the capacity variable.

void resizeStack() 
{
    int *temp = new int[2 * capacity];
    for (int i = 0; i < capacity; i = i + 1)
        temp[i] = stack[i];
    delete [] stack;
    stack = temp;
    capacity = 2 * capacity;
}

void push(int x): this method add an element x onto the stack. If the stack is full, it calls the resizeStack() function to increase the capacity of the stack. Then, it increments top by 1 and places the element at the top of the stack.

void push(int x) 
{
    if (isFull() == true)
        resizeStack();
    top = top + 1;
    stack[top] = x;
}

Stack using dynamic array implementation code C++

class StackDynamicArray 
{
 private:
    int *stack;
    int top;
    int capacity;
    void resizeStack() 
    {
        int *temp = new int[2 * capacity];
        for (int i = 0; i < capacity; i = i + 1)
            temp[i] = stack[i];
        delete [] stack;
        stack = temp;
        capacity = 2 * capacity;
    }

 public:
    StackDynamicArray(int size) 
    {
        stack = new int[size];
        capacity = size;
        top = -1;
    }

    void push(int x) 
    {
        if (isFull())
            resizeStack();
        top = top + 1;
        stack[top] = x;
    }

    int pop() 
    {
        if (isEmpty()) 
        {
            cout << "Stack Underflow!" << endl;
            return INT_MIN;
        }
        int temp = stack[top];
        top = top - 1;
        return temp;
    }

    int peek() 
    {
        if (isEmpty())
        {
            cout << "Stack is empty!" << endl;
            return INT_MIN;
        }    
        return stack[top];
    }

    int size() 
    {
        return top + 1;
    }

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

    bool isFull() 
    {
        return top == capacity - 1;
    }
};

Note: In programming, dynamic-sized arrays are data structures that can hold a varying number of items. For example, in C++ we have vectors, in Python we have lists, and in Java we have ArrayLists. These data structures have the ability to automatically adjust their size as items are added or removed.

Linked list implementation of stack

A singly-linked list is a linear data structure where each element, called a node, stores a value and a pointer to the next element in the list. We can use a singly-linked list to implement a stack data structure by representing the head of the linked list as the top of the stack. This allows us to easily add and remove elements from the head of the list to perform push and pop operations on the stack.

We define a LinkedListStack class, which has the following private member attributes.

• stackTop: a pointer to the top element of the stack (the head of the linked list).
• stackSize: a variable to store the number of elements in the stack.

We define following public member methods in LinkedListStack class:

void push(int data): We adds a new element to the top of the stack. For this, we creates a new Node object with the given data, sets the next pointer of the new node to the current top element of the stack, and then updates the stackTop pointer to the new node. We also increments the stackSize counter.

void push(int data) 
{
    Node* new_node = new Node(data);
    new_node->next = stackTop;
    stackTop = new_node;
    stackSize = stackSize + 1;
}

int pop(): We removes the top element from the stack. For this, we checks if the stack is empty, and if it is, we prints an error message. If the stack is not empty, we stores a pointer to the top element in a temporary variable, updates the stackTop pointer to the next element in the list, stores the value of the top element in a temp variable, deletes the top element, and decrements the stackSize counter. Finally, we returns the value of the top element stored in temp variable.

int pop() 
{
    if (stackSize == 0) 
    {
        cout << "Stack is empty" << endl;
        return INT_MIN;
    }
    
    Node* temp = stackTop;
    stackTop = stackTop->next;
    int data = temp->data;
    delete temp;
    stackSize = stackSize - 1;
    return data;
}

int getSize(): We returns the value stored in stackSize variable.

bool isEmpty(): If stackSize is equal to 0, we returns true otherwise we return false otherwise.

int peek(): We checks if the stack is empty, and if it is, we prints an error message. If the stack is not empty, we returns the value stored in stackTop.

int getSize() 
{
    return stackSize;
}

bool isEmpty() 
{
    return stackSize == 0;
}

int peek() 
{
    if (stackSize == 0) 
    {
            cout << "Stack is empty" << endl;
            return INT_MIN;
    } 
    return stackTop->data;
}

Stack using linked list implementation code C++

// Node class for a singly-linked list
class Node 
{
 public:
    int data;
    Node* next;
    Node(int data) : data(data), next(NULL) {}
};

// Stack class
class LinkedListStack 
{
 private:
    Node* stackTop;
    int stackSize;

 public:
    Stack() : stackTop(NULL), size(0) {}
    
    // Push an element to the top of the stack
    void push(int data) 
    {
        Node* new_node = new Node(data);
        new_node->next = stackTop;
        stackTop = new_node;
        stackSize = stackSize + 1;
    }

    // Pop the top element from the stack
    int pop() 
    {
        if (stackSize == 0) 
        {
            cout << "Error: stack is empty" << endl;
            return INT_MIN;
        }
        
        Node* temp = stackTop;
        stackTop = stackTop->next;
        int data = temp->data;
        delete temp;
        stackSize = stackSize - 1;
        return data;
    }

    // Return the size of the stack
    int getSize() 
    {
        return stackSize;
    }

    // Check if the stack is empty
    bool isEmpty() 
    {
        return stackSize == 0;
    }

    // Return the top element of the stack
    int peek() 
    {
        if (stackSize == 0) 
        {
            cout << "Error: stack is empty" << endl;
            return INT_MIN;
        } 
        return stackTop->data;
    }
};

One advantage of using a linked list to implement a stack is that it can dynamically adjust its size at runtime to meet changing needs. However, this approach does have a drawback: it requires the use of pointers, which can consume additional memory.

Applications of stack in data structures and algorithms

• Back and forward buttons in a web browser
• UNDO/REDO functionality in text editors and image editing software
• Call logs management in mobile phones
• Memory management in computer programming
• Delimiter checking
• Implementing recursion in programming
• Expression conversion and evaluation
• Matching HTML tags in web development
• We can solve a lot of coding problems using stack!

Explore this blog to learn more: Application of stack data structure

Coding problems to practice using stack

• Next greater element: Find the next greater element for each element in the array.
• Sort stack: Given a stack, sort the elements in the stack in ascending order. You may not use any additional data structures or make any copies of the elements.
• Implement stack using queue: Design a stack that is implemented using one or more queues.
• Implement queue using stack: Design a queue that is implemented using one or more stacks.
• Min stack: Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time
• Largest rectangle in histogram: Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of the largest rectangle in the histogram.
• Reverse stack elements: Given a stack, reverse the order of the elements in the stack.
• Implement two stack using single array: Design a data structure that allows for two stacks to be used with a single array, with both stacks having O(1) time complexity for push and pop operations.

Enjoy learning, enjoy algorithms!