Stack Implementation

Introduction

Have you always wanted to learn about stacks? Do you also want to know how to implement it in code or a way to visualize it? Then, you are at the right place. This article aims to provide you with in-depth knowledge about stack implementation in one of the easiest and systematic ways. 

Before discussing more implementation, let’s brush up on our knowledge about stacks. 

So, What are stacks? No, I don’t want you to think of it as a coding question; just imagine how a stack looks in the practical world. 

See this image:

So, we have five disks stacked together, as shown above.  The numbers represent the order in which we place them one by one on top of each other. So, this is what a stack looks like.

Stack is a linear data structure that allows the most recently added elements to be removed first and this feature is more popularly known as LIFO ( last in, first out). So, both the insertion and deletion of elements happen only from one end, i.e. from the top of the stack.

The main functions of the stack include – 

1. Pop – to remove the top element from the stack
2. Push – to insert an element into the stack 
3. Peek or top – to find the top element of the stack
4. isEmpty – to check if the stack is empty or not 

Now that you are confident about the foundation, let’s think about how to mimic this stack in our code, i.e. how to implement it. Maybe you should wonder – 

• What data structures should be used? 
• How to implement the primary functions of the stack?  

Stack Implementation Using Array

Arrays are also linear data structures that we are now going to use for stack implementation. You may think that so far, we imagine arrays as a horizontal block consisting of data elements, whereas stacks are vertical. How come we can use arrays for implementing a stack? 

Let’s see this representation which helps you to visualize the array as a stack: –

So, you see that the start index of the array becomes the bottom of the stack and the ending index acts as stack top. 

First, we need to declare an array with a fixed size of “MAX”. Then define a variable “top” and initialize it with “-1”. 

Functions for Stack Implementation using Arrays:

1. Push Operation  –  To add an element to the stack, two things we need to do

• Increment the top variable to now point to the next free slot in the array and check it does not exceed the maximum limit.
• Put the new value in that position.

PseudoCode –  

if(top == MAX-1)                        // MAX =  size of the array 
print ( “Stack overflow ”)
else
      top = top+1
      array[top]  =  val

2. Pop Operation  –  It is used for removing elements from the stack. 

Steps – 

• Check if the value of top is -1, which means our stack is empty i.e.underflow condition. 
• Else we will store the current data at the index “top” in a variable and then decrement top by one so that now it points to the new top of the stack.

PseudoCode – 

if(top==-1)
print( "stack underflow")
else
value = array[top]
top=top-1

3. Peek – To get the topmost element of the stack. 

• Quite simply, just check if the top is equal to -1 or not. If not, get the value at the index top and return it; otherwise, the stack is empty.

PseudoCode – 

if(top!=-1)
return array[top]
else
print("Stack underflow")

4. isEmpty – It is used to check if the stack is empty or not. 

• Just check if the top equals -1, then the stack is empty; otherwise, it is not.

PseudoCode – 

if(top==-1)
return true
else
return false

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) 

2. 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) 

3. 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) 

4. 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++ code for implementation of stack using linked lists
#include <bits/stdc++.h>
using namespace std;

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

StackNode* newNode(int data)
{
StackNode* stackNode = new StackNode();
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}

int isEmpty(StackNode* root)
{
return !root;
}

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

int pop(StackNode** root)
{
if (isEmpty(*root))
return INT_MIN;
StackNode* temp = *root;
*root = (*root)->next;
int popped = temp->data;
free(temp);

return popped;
}

int peek(StackNode* root)
{
if (isEmpty(root))
return INT_MIN;
return root->data;
}

// main code to execute the functions declared above.
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 : ";
//printing the elements present in stack :
while(!isEmpty(root))
{
// print the top element of stack
cout<<peek(root)<<" ";
// removing the top element from stack
pop(&root);
}

return 0;
}

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

Key Takeaways

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.

Apart from this, you can use CodeStudio to practice a wide range of DSA questions typically asked in interviews at big product-based companies. It will assist you in mastering efficient coding techniques and provide you with interview experiences from scholars in large product-based companies.