Stack Implementation

C++ code for Stack Implementation using Arrays:  

/* C++ implementation of stack using array*/ #include <bits/stdc++.h> using namespace std; #define MAX 100 // Maximum size of Stack class Stack  { int top; public: int arr[MAX]; Stack() { top = -1; } bool push(int x); int pop(); int peek(); bool isEmpty(); }; bool Stack::push(int x) { if (top >= (MAX - 1))        { cout << "Stack overflow\n"; return false; } else        { arr[++top] = x; cout << x << " pushed into the stack\n"; return true; } } int Stack::pop() { if (top < 0)        { cout << "Stack underflow\n"; return 0; } else { int val = arr[top--]; return val; } } int Stack::peek() { if (top < 0)        { cout << "Stack is empty\n"; return 0; } else { int val = arr[top]; return val; } } bool Stack::isEmpty() { return (top < 0); } // main program to see the stack functions declared above in action int main() { class Stack s; s.push(10); s.push(20); s.push(30); cout << s.pop() << "Popped from the stack\n"; //printing all the elements present in the stack cout<<"Elements of the stack are as follows: \n"; while(!s.isEmpty()) { // print top element in stack cout<<s.peek()<<" "; // remove the top element from the stack s.pop(); } return 0; }

Output:

10 pushed into the stack 20 pushed into the stack 30 pushed into the stack 30 Popped from the stack Top element is : 20 Elements of the stack are as follows : 20 10

The time complexity of all the operations : 

• Push – O(1)  as we only increment top by 1 and insert the value.
• Pop – O(1) as we are only decrementing top by 1 and returning the value.
• Peek – O(1) as we just access the value at the index top
• isEmpty – O(1) as only we check the value of top
• Printing the stack – O(n) as we traverse whole stack elements to print them.

Now that we have discussed the array approach, we will learn another way using linked lists. 

You would be thinking – Why? What’s the need? 

Cons of Array Implementation:

We should know that array implementation is exemplary as far as we know how many elements are to be inserted into the stack in advance. So, this is why array implementation is not flexible, and it may become the bottleneck when you work in a system where space is limited. So, we should have some way to allocate and deallocate memory as per our needs. 

Stack Implementation Using Linked List

Again, let’s look at the visual representation of the stack implementation using a linked list to get an idea about it. 

So, we know that linked lists allocate memory dynamically according to requirements. 

The top element of that stack is pointed by a reference pointer called “top”. So, initially, when the list is empty, the value of the top is NULL. When we insert a new element, we first create a new node, allocate memory for it,  then initialize it with the given value, and make this node point to the current top of the stack and change top to point to this newly created node which basically means that we are inserting the new node to the starting of the linked list. 

Operations on Stack using Linked List

1. isEmpty –

• Check if the value of the top is NULL or not.
• If it is NULL, then the stack is empty.
• Else stack is not empty.

Time complexity – O(1) 

1. Push –

• Create a new node and allocate memory for it.
• Initialize it with the value to be inserted.
• Make the next field of the new node point to the current top of the stack and update the top to point to the new node.

Time complexity – O(1) 

1. Pop –

• Check if the Stack is empty.
• If empty, then Stack is in an underflow state.
• Else make a temporary node and make it point to the current top.
• Update top to top->next;
• Free the memory location pointed to by the temporary node.

Time complexity – O(1) 

1. Peek –

• Simply check if the stack is empty or not.
• If not, then return the value of the node pointed by the top.

Time complexity – O(1) 

C++ Code for Stack Implementation using Linked Lists

• C++

C++

#include <iostream>
using namespace std;

class StackNode {
public:
    int data;
    StackNode* next;
};

// Function to create a new stack node
StackNode* newNode(int data) {
    StackNode* stackNode = new StackNode();
    stackNode->data = data;
    stackNode->next = NULL;
    return stackNode;
}

// Function to check if the stack is empty
bool isEmpty(StackNode* root) {
    return root == NULL;
}

// Function to push an element onto the stack
void push(StackNode** root, int data) {
    StackNode* stackNode = newNode(data);
    stackNode->next = *root;
    *root = stackNode;
    cout << data << " pushed to the stack\n";
}

// Function to pop an element from the stack
int pop(StackNode** root) {
    if (isEmpty(*root)) {
        cout << "Stack Underflow\n";
        return INT_MIN;
    }
    StackNode* temp = *root;
    *root = (*root)->next;
    int popped = temp->data;
    delete temp;  // Use delete instead of free for C++ allocation
    return popped;
}

// Function to get the top element of the stack
int peek(StackNode* root) {
    if (isEmpty(root)) {
        cout << "Stack is empty\n";
        return INT_MIN;
    }
    return root->data;
}

// Main function to execute the stack operations
int main() {
    StackNode* root = NULL;

    push(&root, 10);
    push(&root, 20);
    push(&root, 30);

    cout << pop(&root) << " popped from stack\n";
    cout << "Top element of stack is " << peek(root) << endl;
    
    cout << "Elements present in stack: ";
    while (!isEmpty(root)) {
        cout << peek(root) << " ";
        pop(&root);
    }
    cout << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

10 pushed to stack 
20 pushed to stack
30 pushed to stack  
30 popped from stack 
Top element of stack is 20 
Elements present in stack : 20 10

Frequently Asked Questions

What is stack implementation?

Stack implementation involves using data structures, like arrays or linked lists, to create a stack where elements follow Last-In-First-Out (LIFO) order.

Why is stack implementation useful?

Stack implementation is useful for managing function calls, undo operations, and reversing data, thanks to its Last-In-First-Out (LIFO) nature.

What is stack and its operations?

A stack is a data structure where elements are added and removed in Last-In-First-Out (LIFO) order. Main operations include push, pop, and peek.

Conclusion

In this article, we talked about stacks and most importantly how to implement them with well-known data structures such as arrays and linked lists. Building up the foundation is very important as these questions are widely asked in the face to face interviews to test your in-depth understanding.

We also learned the implementation of various functions of the stack and their time complexities. You can also read more about stacks and other important data structures here.