Data Structure and Algorithms - Stack

A stack is an Abstract Data Type (ADT), that is popularly used in most programming languages. It is named stack because it has the similar operations as the real-world stacks, for example – a pack of cards or a pile of plates, etc.

The stack follows the LIFO (Last in - First out) structure where the last element inserted would be the first element deleted.

Stack Representation

A Stack ADT allows all data operations at one end only. At any given time, we can only access the top element of a stack.

The following diagram depicts a stack and its operations −

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which makes it a fixed size stack implementation.

Basic Operations on Stacks

Stack operations usually are performed for initiapzation, usage and, de-initiapzation of the stack ADT.

The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(), isEmpty(). These are all built-in operations to carry out data manipulation and to check the status of the stack.

Stack uses pointers that always point to the topmost element within the stack, hence called as the top pointer.

Insertion: push()

push() is an operation that inserts elements into the stack. The following is an algorithm that describes the push() operation in a simpler way.

Algorithm

1 − Checks if the stack is full.
2 − If the stack is full, produces an error and exit.
3 − If the stack is not full, increments top to point next empty space.
4 − Adds data element to the stack location, where top is pointing.
5 − Returns success.

Example

Following are the implementations of this operation in various programming languages −

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full*/
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.
");
   }
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: 
");
   
   // print stack data
   for(i = 0; i < 8; i++) {
      printf("%d ", stack[i]);
   }
   return 0;
}

Stack Elements: 
44 10 62 123 15 0 0 0 

#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full*/
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.
");
   }
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: 
");

   // print stack data
   for(i = 0; i < 8; i++) {
      printf("%d ", stack[i]);
   }
   return 0;
}

Stack Elements: 
44 10 62 123 15 0 0 0 

import java.io.*;
import java.util.*; // util imports the stack class
pubpc class StackExample {
   pubpc static void main (String[] args) {
      Stack<Integer> stk = new Stack<Integer>();
      
      // inserting elements into the stack
      stk.push(52);
      stk.push(19);
      stk.push(33);
      stk.push(14);
      stk.push(6);
      System.out.print("The stack is: " + stk);
   }
}

The stack is: [52, 19, 33, 14, 6]

class Stack:
   def __init__(self):
      self.stack = []
   def __str__(self):
      return str(self.stack)
   def push(self, data):
      if data not in self.stack:
         self.stack.append(data)
         return True
      else:
         return False
stk = Stack()
stk.push(1)
stk.push(2)
stk.push(3)
stk.push(4)
stk.push(5)
print("Stack Elements:")
print(stk)

Stack Elements:
[1, 2, 3, 4, 5]

Note − In Java we have used to built-in method push() to perform this operation.

Deletion: pop()

pop() is a data manipulation operation which removes elements from the stack. The following pseudo code describes the pop() operation in a simpler way.

Algorithm

1 − Checks if the stack is empty.
2 − If the stack is empty, produces an error and exit.
3 − If the stack is not empty, accesses the data element at which top is pointing.
4 − Decreases the value of top by 1.
5 − Returns success.

Example

Following are the implementations of this operation in various programming languages −

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is empty */
int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}

/* Check if the stack is full*/
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to delete from the stack */
int pop(){
   int data;
   if(!isempty()) {
      data = stack[top];
      top = top - 1;
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.
");
   }
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.
");
   }
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: 
");

   // print stack data
   for(i = 0; i < 8; i++) {
      printf("%d ", stack[i]);
   }
   /*printf("Element at top of the stack: %d
" ,peek());*/
   printf("
Elements popped: 
");

   // print stack data
   while(!isempty()) {
      int data = pop();
      printf("%d ",data);
   }
   return 0;
}

Stack Elements: 
44 10 62 123 15 0 0 0 
Elements popped: 
15 123 62 10 44 

#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is empty */
int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}

/* Check if the stack is full*/
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to delete from the stack */
int pop(){
   int data;
   if(!isempty()) {
      data = stack[top];
      top = top - 1;
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.
");
   }
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.
");
   }
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: 
");

   // print stack data
   for(i = 0; i < 8; i++) {
      printf("%d ", stack[i]);
   }
   
   /*printf("Element at top of the stack: %d
" ,peek());*/
   printf("
Elements popped: 
");

   // print stack data
   while(!isempty()) {
      int data = pop();
      printf("%d ",data);
   }
   return 0;
}

Stack Elements: 
44 10 62 123 15 0 0 0 
Elements popped: 
15 123 62 10 44 

import java.io.*;
import java.util.*; 

// util imports the stack class
pubpc class StackExample {
   pubpc static void main (String[] args) {
      Stack<Integer> stk = new Stack<Integer>();
      
      // Inserting elements into the stack
      stk.push(52);
      stk.push(19);
      stk.push(33);
      stk.push(14);
      stk.push(6);
      System.out.print("The stack is: " + stk);
      
      // Deletion from the stack
      System.out.print("
The popped element is: ");
      Integer n = (Integer) stk.pop();
      System.out.print(n);
   }
}

The stack is: [52, 19, 33, 14, 6]
The popped element is: 6

class Stack:
   def __init__(self):
      self.stack = []
   def __str__(self):
      return str(self.stack)
   def push(self, data):
      if data not in self.stack:
         self.stack.append(data)
         return True
      else:
         return False
   def remove(self):
      if len(self.stack) <= 0:
         return ("No element in the Stack")
      else:
         return self.stack.pop()
stk = Stack()
stk.push(1)
stk.push(2)
stk.push(3)
stk.push(4)
stk.push(5)
print("Stack Elements:")
print(stk)
print("----Deletion operation in stack----")
p = stk.remove()
print("The popped element is: " + str(p))
print("Updated Stack:")
print(stk)

Stack Elements:
[1, 2, 3, 4, 5]
----Deletion operation in stack----
The popped element is: 5
Updated Stack:
[1, 2, 3, 4]

Note − In Java we are using the built-in method pop().

peek()

The peek() is an operation retrieves the topmost element within the stack, without deleting it. This operation is used to check the status of the stack with the help of the top pointer.

Algorithm

1. START
2. return the element at the top of the stack
3. END

Example

Following are the implementations of this operation in various programming languages −

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full */
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to return the topmost element in the stack */
int peek(){
   return stack[top];
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.
");
   }
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: 
");

   // print stack data
   for(i = 0; i < 8; i++) {
      printf("%d ", stack[i]);
   }
   printf("
Element at top of the stack: %d
" ,peek());
   return 0;
}

Stack Elements: 
44 10 62 123 15 0 0 0 
Element at top of the stack: 15

#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full */
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Function to return the topmost element in the stack */
int peek(){
   return stack[top];
}

/* Function to insert into the stack */
int push(int data){
   if(!isfull()) {
      top = top + 1;
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.
");
   }
}

/* Main function */
int main(){
   int i;
   push(44);
   push(10);
   push(62);
   push(123);
   push(15);
   printf("Stack Elements: 
");

   // print stack data
   for(i = 0; i < 8; i++) {
      printf("%d ", stack[i]);
   }
   printf("
Element at top of the stack: %d
" ,peek());
   return 0;
}

Stack Elements: 
44 10 62 123 15 0 0 0 
Element at top of the stack: 15

import java.io.*;
import java.util.*; 

// util imports the stack class
pubpc class StackExample {
   pubpc static void main (String[] args) {
      Stack<Integer> stk = new Stack<Integer>();
      
      // inserting elements into the stack
      stk.push(52);
      stk.push(19);
      stk.push(33);
      stk.push(14);
      stk.push(6);
      System.out.print("The stack is: " + stk);
      Integer pos = (Integer) stk.peek();
      System.out.print("
The element found is " + pos);
   }
}

The stack is: [52, 19, 33, 14, 6]
The element found is 6

class Stack:
   def __init__(self):
      self.stack = []
   def __str__(self):
      return str(self.stack)
   def push(self, data):
      if data not in self.stack:
         self.stack.append(data)
         return True
      else:
         return False
   # Use peek to look at the top of the stack
   def peek(self):
      return self.stack[-1]
stk = Stack()
stk.push(1)
stk.push(2)
stk.push(3)
stk.push(4)
stk.push(5)
print("Stack Elements:")
print(stk)
print("topmost element: ",stk.peek())

Stack Elements:
[1, 2, 3, 4, 5]
topmost element: 5

isFull()

isFull() operation checks whether the stack is full. This operation is used to check the status of the stack with the help of top pointer.

Algorithm

1. START
2. If the size of the stack is equal to the top position of the stack, the stack is full. Return 1.
3. Otherwise, return 0.
4. END

Example

Following are the implementations of this operation in various programming languages −

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full */
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Main function */
int main(){
   printf("Stack full: %s
" , isfull()?"true":"false");
   return 0;
}

Stack full: false

#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full */
int isfull(){
   if(top == MAXSIZE)
      return 1;
   else
      return 0;
}

/* Main function */
int main(){
   printf("Stack full: %s
" , isfull()?"true":"false");
   return 0;
}

Stack full: false

import java.io.*;
pubpc class StackExample {
   private int arr[];
   private int top;
   private int capacity;
   StackExample(int size) {
      arr = new int[size];
      capacity = size;
      top = -1;
   }
   pubpc boolean isEmpty() {
      return top == -1;
   }
   pubpc boolean isFull() {
      return top == capacity - 1;
   }
   pubpc void push(int key) {
      if (isFull()) {
         System.out.println("Stack is Full
");
         return;
      }
      arr[++top] = key;
   }
   pubpc static void main (String[] args) {
      StackExample stk = new StackExample(5);
      stk.push(1); // inserting 1 in the stack
      stk.push(2);
      stk.push(3);
      stk.push(4);
      stk.push(5);
      System.out.println("Stack Full? " + stk.isFull());
   }
}

Stack Full? true

isEmpty()

The isEmpty() operation verifies whether the stack is empty. This operation is used to check the status of the stack with the help of top pointer.

Algorithm

1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END

Example

Following are the implementations of this operation in various programming languages −

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is empty */
int isempty() {
   if(top == -1)
      return 1;
   else
      return 0;
}

/* Main function */
int main() {
   printf("Stack empty: %s
" , isempty()?"true":"false");
   return 0;
}

Stack empty: true

#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is empty */
int isempty(){
   if(top == -1)
      return 1;
   else
      return 0;
}

/* Main function */
int main(){
   printf("Stack empty: %s
" , isempty()?"true":"false");
   return 0;
}

Stack empty: true

import java.io.*;
import java.util.*; // util imports the stack class
pubpc class StackExample {
   pubpc static void main (String[] args) {
      Stack<Integer> stk = new Stack<Integer>();
      
      // Inserting elements into the stack
      stk.push(52);
      stk.push(19);
      stk.push(33);
      stk.push(14);
      stk.push(6);
      System.out.println("Stack empty? "+ stk.isEmpty());
   }
}

Stack empty? false

Implementation of Stack

For a complete stack program in C programming language, please cpck here.

For a complete stack program in C++ programming language, please cpck here.

For a complete stack program in JAVA programming language, please cpck here.

For a complete stack program in Python programming language, please cpck here.