Stack in Data Structure

Assume you are standing in a line for a buffet dinner. When your turns come, you pick up a plate from the top. This plate was cleaned after the plate below it and is used earlier than the plate below it. You cannot use a plate without removing the plates above it. A stack works in the same way.

The last object to be entered in a stack is used at first. In this article, we will learn about stack operations, implementations, and some basic applications.

Stack in Data Structure

Stack is an abstract data type data structure that allows operations at one end only. Like in the above example you can add or remove plates from the top only. Similarly, in a stack, you can add or delete elements from one end only. This makes the stack a LIFO structure.

LIFO stands for Last In First Out. The last element entered in a stack will be the first one that can be accessed and removed. For the below elements, you will need to remove all the elements one by one above that element.

Basic Operations of Stack

Push(): adding an element in the stack.
Pop(): accessing or removing an element from the stack.
Peek(): return the topmost element of the stack without removing it.
IsFull(): check if stack is full.
IsEmpty(): check if stack is empty.
count(): counts the total number of elements in the stack.

Let us see each of these functions in details:

1. Peek() in Stack

Return the last entered element of the stack without removing it.

int peek() {
   return stack[top];
}

2. IsFull() in Stack

Check if the stack is full or not. Here MAXSIZE is the maximum size of the stack.

bool isFull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

3. IsEmpty() in Stack

Check if the stack is empty or not. If the stack is empty, the position of the top element is -1.

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

4. Push() in Stack

There is only one way of adding an element in a stack and that is to add on the top of the topmost element. We need to first check if the stack is full or not. We can only add an element if the stack has available space.

void push(int data) 
{
   if(!isFull()) 
    {
        top = top + 1;   
        stack[top] = data;
     } 
   else 
    {
      printf("stack is full");
     }
}

5. Pop() in Stack

Only the topmost element can be removed from the stack. First, check if the stack has any elements or it’s empty. You can only remove an element from a stack if it has any.

int pop(int data) 
{
   if(!isEmpty()) 
     {
        data = stack[top];
        top = top - 1;   
        return data;
     }
    else 
    {
      printf("Stack is empty");
    }
}

6. count() in Stack

This function counts the no of elements in a stack.

int count() 
{
   if(!isEmpty()) 
     {
        return 0;
    else 
    {
      return top+1;
    }
}

Stack implementation in array

Here, a stack is formed using an array. All the operations are performed using arrays only.

1. Push() in array

void push (int val, int n) 
{  
    if (top == n )   
    printf("stack full");   
    else   
    {  
    top = top +1;   
    stack[top] = val;   
    }   
}   

2. pop() in array

int pop ()  
{   
    if(top == -1)   
    {  
        printf("Underflow");  
        return 0;  
    }  
    else  
    {  
        return stack[top - - ];   
    }    
} 

3. peek() in array

int peek()  
{  
    if (top == -1)   
    {  
        printf("Underflow");  
        return 0;   
    }  
    else  
    {  
        return stack [top];  
    }  
}

Advantages of Stack in Array

1. Array implementation of the stack is very easy as compared to linked list implementation.
2. Requires less memory since no pointers are involved.

Disadvantages of Stack in Array

Arrays have a fixed memory size. They are not dynamic. They cannot grow or shrink on the requirement.

Stack implementation in a linked list

Here, a stack is formed using a linked list. All the operations are performed using linked lists only.

1. push() in a linked list

Since linked lists are dynamic, they have no maximum size. They can grow or shrink on the requirement. Therefore, we do not need to check if the stack is already full or not before pushing a new element. We can always add a new element in a stack since there is no limitation of memory.

void push ()  
{  
        if(head==NULL)  
        {         
            ptr -> next = NULL;  
            head=ptr;  
        }   
        else   
        {  
            ptr->next = head;  
            head=ptr;      
        }     
    }  

2. pop() in a linked list

Here we do need to check if a stack is empty or not. An empty stack has no data to be removed.

void pop()  
{  
   struct node *ptr;  
    if (head == NULL)  
    {  
        printf("stack empty");  
    }  
    else  
    {  
        ptr = head;  
        head = head->next;  
        free(ptr);     
    }  
}  

3. peek() in a linked list

int peek()  
{  
    if (head == NULL)  
    {  
        printf("stack empty");
        return 0;  
    }  
    else  
    {  
         return head -> data;  
    }  
}  

Stack implementation in Python

def create_stack():
    stack = []
    return stack

def isEmpty(stack):
    return len(stack) == 0

def push(stack, item):
    stack.append(item)
    print("pushed : " + item)

def pop(stack):
    if (isEmpty(stack)):
        return "UNDERFLOW"

    return stack.pop()


stack = create_stack()
push(stack, str("DATA"))
push(stack, str("FLAIR"))
push(stack, str("STACK"))
push(stack, str("DATA STRUCTURE"))

print("popped : " + pop(stack))
print("current stack " + str(stack))
print("popped : " + pop(stack))
print("current stack " + str(stack))

Stack implementation in C

#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>

#define MAX 10

int counter = 0;

struct stack {
  int items[MAX];
  int top;
};

typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

bool isfull(st *s) {
  if (s->top == MAX - 1)
    return true;
  else
    return false;
}

bool isempty(st *s) {
  if (s->top == -1)
    return true;
  else
    return false;
}

void push(st *s, int new) {
  if (isfull(s)) {
    printf("OVERFLOW");
  } else {
    s->top++;
    s->items[s->top] = new;
  }
  counter++;
}

void pop(st *s) {
  if (isempty(s)) {
    printf("UNDERFLOW");
  } else {
    printf("pop : %d", s->items[s->top]);
    s->top--;
  }
  counter--;
  printf("\n");
}

void DisplayStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < counter; i++) {
    printf("%d ", s->items[i]);
  }

Implementation of Stack in C++

#include <stdlib.h>
#include <iostream>
#include <stdbool.h>

using namespace std;

#define MAX 10
int size = 0;

struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

bool isfull(st *s) {
  if (s->top == MAX - 1)
    return true;
  else
    return false;
}

bool isempty(st *s) {
  if (s->top == -1)
    return true;
  else
    return false;
}

void push(st *s, int newitem) {
  if (isfull(s)) {
    printf("Overflow");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  size++;
}

void pop(st *s) {
  if (isempty(s)) {
    printf("Underflow");
  } else {
    printf("pop : %d", s->items[s->top]);
    s->top--;
  }
  size--;
  cout << endl;
}

void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < size; i++) {
    cout << s->items[i] << " ";
  }
  cout << endl;
}

int main() {
  
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);
  cout << "current stack";
  printStack(s);
  
  pop(s);
  cout << "current stack";
  printStack(s);
}

Stack implementation in Java

public class Stack {
  private String arr[];
  private int top;
  private int capacity;

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

  public void push(String x) {
    if (isFull()) {
      System.out.println("OverFlow");
      System.exit(1);
    }

    System.out.println("push " + x);
    arr[++top] = x;
  }

  public String pop() {
    if (isEmpty()) {
      System.out.println("Underflow");
      
      System.exit(1);
    }
    System.out.println("pop : "+arr[top]);
    return arr[top--];
  }

  public int size() {
    return top + 1;
  }

  public Boolean isEmpty() {
    return top == -1;
  }

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

  public void DisplayStack() {
    for (int i = 0; i <= top; i++) {
      System.out.println(arr[i]);
    }
  }

  public static void main(String []args) {
    Stack stack = new Stack(5);

    stack.push("DATA");
    stack.push("FLAIR");
    stack.push("STACK");
    stack.push("DATA STRUCTURE");
    System.out.println();
    stack.pop();
    System.out.println("current stack");

    stack.DisplayStack();
    System.out.println();
     stack.pop();
    System.out.println("current stack");

    stack.DisplayStack();
    

  }
}

Working of Stack

Stack works on LIFO Principle. Let us consider a stack of characters of Maximum size 7. 

Create an empty stack:  Top = -1

Push(‘D’):

Push(‘A’):

Push(‘T’):

Push(‘A’):

Pop():

Pop():

Push(‘F’):

Push(‘L’):

Push(‘A’):

Push(‘I’):

Push(‘R’):

Time complexity of Stack

In any of the above operations, we did not use any loops. All the operations were performed in constant time. Hence, the worst-case time complexity of  push(), pop(), peek(), isFull() and isEmpty() is O(1).

Applications of Stack

1. Expression conversion

Interconversion of postfix, prefix, and infix expression requires a stack. All symbols are stored in a stack and then each operation is performed.

2. Backtracking

In the Backtracking algorithm designing technique, we need to store the previous state to get back from the current state. For this purpose, a stack is used.

3. Algorithms

Stack is used in many algorithms like tree traversals, histogram problem, stock span problem, Tower of Hanoi.

4. Memory Management

Almost all modern computers use a stack for memory management. When a process is under execution all its variables are assigned to a  stack. The memory assigned to the program is already known to the compiler. When the execution is completed, all the variables in stack memory are released.

5. String Reversal

Stacks are useful in string reversal applications. Push all the characters of the string into a stack and then start popping them one by one.

6. Recursion

Recursion is backed by a stack. It is a function calling itself. Each time function calls itself, it uses a system stack to store its previous states.

Advantages of Stack

1. This implementation is dynamic in nature.

2. It can grow or shrink its size depending on the requirement. It has no maximum size.

Disadvantages of Stack

1. Little difficult to implement as it involves pointers.

2. Requires more memory space because of pointers.

Linked list implementation vs array implementation of Stack

Linked list implementation is a little bit tricky as compared to array implementation. But still linked implementation is more efficient and has a better performance. For smaller values, there might be no visible difference in both approaches, but as the input size increases, we can easily conclude that linked performances are far better than an array implementation.

Complexity

Conclusion

In this article, we learned how a stack works. Stack is based on the FIFO principle and many real-life examples are based on the same principle.

A stack can be implemented using an array and linked list. Though both approaches have their advantages and disadvantages, linked list implementation is more efficient. We also discussed stack implementation in some widely used programming languages.