Skip to main content

Stack Data Structure

A stack is a linear data structure that operates on the principle of Last-In-First-Out (LIFO). In simple terms, the last element added to the stack will be the first element to be removed. Stacks are commonly used in computer science and programming, where they are used to store and retrieve data in a specific order.

A stack can be thought of as a collection of elements, where each element is added to the top of the stack and removed from the top of the stack. The element at the top of the stack is called the top element, and the element at the bottom of the stack is called the base element.

Stacks are commonly used in algorithms and programming because they provide a simple and efficient way to manage data. For example, stacks can be used to keep track of function calls in a program, or to evaluate expressions in reverse Polish notation.

Stack Data Structure

Stack Operations:

A stack supports two basic operations, push and pop.

Push: adds a new element to the top of the stack.

Pop: removes the top element from the stack.

A stack also has a third operation, peek, which returns the top element of the stack without removing it.

Stack Implementation:

A stack can be implemented using an array or a linked list. In an array-based implementation, the stack is represented as an array, where the top element of the stack is stored at the end of the array. In a linked list implementation, the stack is represented as a linked list, where each element in the list contains a pointer to the next element in the list.

Stack Applications:

Stacks are used in a variety of applications, including:

  1. Function Call Stack: In programming, a function call stack is used to store information about the function calls that are made during program execution. Each time a function is called, information about the function call is added to the stack. When the function returns, the information is removed from the stack.

  2. Expression Evaluation: Stacks are used to evaluate expressions in reverse Polish notation, where the operands are placed before the operator. This is done by pushing the operands onto the stack and then popping them off and applying the operator.

  3. Backtracking: Stacks are used in backtracking algorithms to keep track of the state of the search. Each time a new state is explored, it is pushed onto the stack. When a dead end is reached, the state is popped off the stack and the search continues from the previous state.

  4. Undo/Redo: Stacks are used in applications that support undo and redo operations. Each time an action is performed, the state of the application is pushed onto the stack. When the user chooses to undo an action, the state is popped off the stack and applied to the application.

Complexity analysis

Operation Complexity
Insertion O(1)
Deletion O(1)
Searching O(n)
Space O(n)

In conclusion, stacks are a fundamental data structure used in computer science and programming. They are simple to understand and implement, and provide a powerful way to manage data. With their efficient push, pop, and peek operations, stacks can be used in a wide variety of applications, from function call stacks to expression evaluation to undo and redo operations.

Stack Implementation

In this section implemented of stack using array and linked list data structure. Implemented of stack by using of array there are limitation of size. View program to implement stack using array.

//implement stack using array
#include<stdio.h>

//function prototype
void push(int);
void display();
void pop();
int isEmpty();
int isFull();

//set size of stack
#define SIZE 10
int element[SIZE],top=-1;

//insert Stack element
void push(int value){
	if(isFull()){
		printf("Stack Is Full\n");
	}else{
		element[++top]=value;
		printf("\nPush Stack element %d", value);
		display();
	}
}
//pop Stack element
void pop(){
	if(isEmpty()){
		printf("Empty Stack\n");
	}else{
		printf("\nPop Stack element %d", element[top]);
		top--;
		display();
	}
}
//display element of Stack
void display(){
	if(isEmpty()){
		printf("\nEmpty Stack\n");

	}else{
		printf("\n Stack Element :");
		int index=0;
	 	for(index;index<=top;index++){
	 		printf("  %d",element[index]);
	 	}
	}
}
int isFull(){
	if(top+1==SIZE){
		return 1;
	}else{
		return 0;
	}
}
int isEmpty(){
	if(top==-1){
		return 1;
	}else{
		return 0;
	}
}
int main(){
	//insert elements
	push(5);
	push(4);
	push(3);
	push(2);
	push(1);

 //delete elements
	pop();
	pop();
	pop();
	pop();
	pop();
}

Output

Push Stack element 5
 Stack Element :  5
Push Stack element 4
 Stack Element :  5  4
Push Stack element 3
 Stack Element :  5  4  3
Push Stack element 2
 Stack Element :  5  4  3  2
Push Stack element 1
 Stack Element :  5  4  3  2  1
Pop Stack element 1
 Stack Element :  5  4  3  2
Pop Stack element 2
 Stack Element :  5  4  3
Pop Stack element 3
 Stack Element :  5  4
Pop Stack element 4
 Stack Element :  5
Pop Stack element 5
Empty Stack
//C++ Stack implemation By using Array
#include<iostream>
using namespace std;

//Create a Stack class
class Stack{
	public:
		int top,
				limit,
				*element;
	public:
		//member function of class
		Stack(int);
		void push(int);
		void pop();
		void display();
		int isEmpty();
		int isFull();

};
//constructor of class
Stack::Stack(int size){
	 top=-1;
	 limit=size;
	 //create stack of given size 
	 element=new int[size];
}
//push a stack element
void Stack::push(int value){

	if(isFull()){
		cout<<"Stack overflow\n";
	}else{
		element[++top]=value;
		cout<<"\nPush stack element"<<value;
		display();
	}
}
//display element of Node
void Stack:: display(){
	if(isEmpty()){
		cout<<"\nEmpty Stack";
	}else{
		cout<<"\n Stack Element :";
		int index=0;
		for(index;index<=top;index++){
			cout<<" "<<element[index];
		}
	}
}
//Remove top of stack element
void Stack :: pop(){
	if(isEmpty()){
		cout<<"\nEmpty Stack"<<endl;
	}else{
		
		cout<<"\nPop Stack Element "<<element[top] ;
	  top--;
		display(); //display all stack element
	}
}
int Stack ::isEmpty(){
	if(top==-1){
		return 1;
	}else{
		return 0;
	}
}
int Stack ::isFull(){
	if(top+1==limit){
		return 1;
	}else{
		return 0;
	}
}
int main(){

	//create object
	Stack obj(5);//set stack size
	//push element of stack
	obj.push(50);
	obj.push(40);
	obj.push(30);
	obj.push(20);
	obj.push(10);
	//pop operation
	obj.pop();
	obj.pop();
	obj.pop();
	obj.pop();
	obj.pop();
}

Output

Push stack element50
 Stack Element : 50
Push stack element40
 Stack Element : 50 40
Push stack element30
 Stack Element : 50 40 30
Push stack element20
 Stack Element : 50 40 30 20
Push stack element10
 Stack Element : 50 40 30 20 10
Pop Stack Element 10
 Stack Element : 50 40 30 20
Pop Stack Element 20
 Stack Element : 50 40 30
Pop Stack Element 30
 Stack Element : 50 40
Pop Stack Element 40
 Stack Element : 50
Pop Stack Element 50
Empty Stack
//java implement stack using array
public class Stack{
	static int top;
	//set size of stack
	static  int limit;
	static int element[];
	//Class constructors
	Stack(int size){
		top=-1;
		limit=size;
		element=new int[size];
	}
	//insert stack element
	static void push(int value){
		if(top+1==limit){
			System.out.println("\nStack is Full not push element "+value);
		}else{
			element[++top]=value;
			System.out.println("\nPush element of Stack "+value);
			display();			
		}
	}
	static void pop(){
		if(top==-1){
			System.out.println("Empty Stack ");
		}else{
		
			System.out.println("\nPop element of Stack "+element[top]);
			top--;
			display();
		}

	}
	//display all stack elements
	static void display(){
		if(top!=-1){
			int index=0;
			for(index=0;index<=top;index++){
				System.out.print("  "+element[index]);
			}
		}else{
				System.out.println("Empty Stack"); 
		}
	}

	public static void main(String[] args) {
		
		Stack obj=new Stack(5);
		obj.push(0);
		obj.push(1);
		obj.push(2);
		obj.push(3);
		obj.push(4);
		obj.push(5);
		obj.pop();
		obj.pop();
		obj.pop();
	}
}
Output
Push element of Stack 0
  0
Push element of Stack 1
  0  1
Push element of Stack 2
  0  1  2
Push element of Stack 3
  0  1  2  3
Push element of Stack 4
  0  1  2  3  4
Stack is Full not push element 5

Pop element of Stack 4
  0  1  2  3
Pop element of Stack 3
  0  1  2
Pop element of Stack 2
  0  1

#create class Stack    
class Stack:
 def __init__(self,size):
  #Assign default value
  self.top=-1
  self.limit=size
  self.element=[]

 #push new node to Stack  
 def push(self,data):
  if self.top+1 >self.limit:
    print("Stack is Full")
  else:
    self.top+=1
    self.element.append(data)
    print("Push Elements",self.element[self.top]) 
    print("Stack Elements",self.element) 


 def pop(self):
  if self.top==-1:
    print("Empty Stack");
  else:
    print("Pop Elements",self.element[self.top]) 
    self.top-=1
    self.element.pop()
    print("Stack Elements",self.element) 
#Create Object of class Stack
Stack=Stack(4)

#Stack push operation
Stack.push(1)
Stack.push(2)
Stack.push(3)
Stack.push(4)
Stack.push(5)

#Pop operation
Stack.pop();
Stack.pop();
Stack.pop();

Output

('Push Elements', 1)
('Stack Elements', [1])
('Push Elements', 2)
('Stack Elements', [1, 2])
('Push Elements', 3)
('Stack Elements', [1, 2, 3])
('Push Elements', 4)
('Stack Elements', [1, 2, 3, 4])
('Push Elements', 5)
('Stack Elements', [1, 2, 3, 4, 5])
('Pop Elements', 5)
('Stack Elements', [1, 2, 3, 4])
('Pop Elements', 4)
('Stack Elements', [1, 2, 3])
('Pop Elements', 3)
('Stack Elements', [1, 2])
//c# program to implement stack using array
using System;

//Create a Stack class
public class Stack{
	private int top;
	private int[]element;
	private int limit;
	//constructor of class Stack
	public Stack(int size){
		//set initial stack top is null
		top=-1; 
		limit=size;
		element=new int[size];
	}
	//display all stack elements
	public void display(){
		if(top!=-1){
			for(int index=0;index<=top;index++){
				Console.Write("  "+element[index]);
			}
		}else{
			Console.WriteLine("Empty Stack");
		}
	}
	//insert stack element
	public void push(int value){
		if(top+1<limit){

			element[++top]=value;
			Console.WriteLine("\nPush data {0}",value);
			display();
		}else{
			Console.WriteLine("\nStack is Full");
		}

	}
	//delete stack elements
	public void pop(){
		if(top!=-1){
			Console.WriteLine("\nPop data {0}",element[top]);
			top--;
			display();
		}else{
			Console.WriteLine("Empty Stack");
		}
	}

}
class Program{
	static void Main(string[] args){
		Stack obj=new Stack(5);
		//insert stack elements
		obj.push(1);
		obj.push(2);
		obj.push(3);
		obj.push(4);
		obj.push(5);
		//Delete stack elements
		obj.pop();
		obj.pop();
		obj.pop();
	}
}

Output

Push data 1
  1
Push data 2
  1  2
Push data 3
  1  2  3
Push data 4
  1  2  3  4
Push data 5
  1  2  3  4  5
Pop data 5
  1  2  3  4
Pop data 4
  1  2  3
Pop data 3
  1  2

Linked list is solve the limitation of size in stack data structure. and that are suitable to create and allocated stack node as well.

//implement stack using linked list
#include<stdio.h>
#include <stdlib.h> //for malloc function
//create structure
struct Node{
	int data;
	struct Node*next;
};
//function prototype
void push(struct Node**,int);
void display(struct Node*);
void pop(struct Node**);

//insert Stack element
void push(struct Node**top,int value){
		//Create dynamic node
		struct Node*node=(struct Node*)malloc(sizeof(struct Node));
		if(node==NULL){
			printf("Memory overflow\n");
		}else{
			node->data=value;
			node->next=*top;
			*top=node;
			printf("\n Push Stack element %d",value);
			display(*top);
		}
}
//pop Stack element
void pop(struct Node**top){
		if(*top==NULL){
			printf("Empty Stack\n");
		}else{
			struct Node*temp=*top;
			*top=temp->next;
			printf("\n Pop Stack element %d",temp->data);
			free(temp);
			temp=NULL;
			display(*top);
		}
}
//display element of Stack
void display(struct Node*temp){
  if(temp!=NULL){
  	printf("\nStack Elements is : ");
  }
	while(temp!=NULL){
		printf("%d  ",temp->data);
		temp=temp->next;
	}
}
int main(){
	struct Node*top=NULL;
	push(&top,5);
	push(&top,4);
	push(&top,3);
	push(&top,2);
	push(&top,1);

	pop(&top);
	pop(&top);
	pop(&top);
	pop(&top);
}

Output

 Push Stack element 5
Stack Elements is : 5
 Push Stack element 4
Stack Elements is : 4  5
 Push Stack element 3
Stack Elements is : 3  4  5
 Push Stack element 2
Stack Elements is : 2  3  4  5
 Push Stack element 1
Stack Elements is : 1  2  3  4  5
 Pop Stack element 1
Stack Elements is : 2  3  4  5
 Pop Stack element 2
Stack Elements is : 3  4  5
 Pop Stack element 3
Stack Elements is : 4  5
 Pop Stack element 4
Stack Elements is : 5
//Stack implemation By using Linked list
#include<iostream>
using namespace std;
//create structure
struct Node{
	int data;
	struct Node*next;
};
//Create a Stack class
class Stack{
	public:
		struct Node*top;
	public:
		//member function of class
		Stack();
		
		void push(int);
		void pop();
		void display();
};
//constructor of class
Stack::Stack(){
	 top=NULL;
}
//push a stack element
void Stack::push(int value){
	//Create dynamic node
	struct Node*node=new Node;
	if(node==NULL){
		cout<<"Memory overflow\n";
	}else{
		//push node at beginning of linked list
		node->data=value;
		node->next=top;
		top=node;
		printf("\n Push stack element %d\n",value );
		printf(" After push Linked List :");
		display();
	}
}
//display element of Node
void Stack:: display(){
	struct Node*temp=top;
	if(temp==NULL){
		cout<<" Empty Stack"<<endl;
	}
	//display stack element value
	while(temp!=NULL){
		cout<<" "<<temp->data;
		temp=temp->next;
	}
}
//Remove top of stack element
void Stack :: pop(){
	if(top==NULL){
		cout<<"Empty Linked List";
	}else{
		struct Node*temp=top;
		printf("\n%d Pop Stack Element\n",temp->data );
		top=temp->next;
		free(temp);//remove top element
		temp=NULL;
		printf(" After pop Linked List :");
		display(); //display all stack element
	}
}
int main(){

	//create object
	Stack obj;
	//push element of stack
	obj.push(50);
	obj.push(40);
	obj.push(30);
	obj.push(20);
	obj.push(10);
	//pop operation
	obj.pop();
	obj.pop();
	obj.pop();
	obj.pop();
	obj.pop();
}
C++ stack implement by linked list

Output

 Push stack element 50
 After push Linked List : 50
 Push stack element 40
 After push Linked List : 40 50
 Push stack element 30
 After push Linked List : 30 40 50
 Push stack element 20
 After push Linked List : 20 30 40 50
 Push stack element 10
 After push Linked List : 10 20 30 40 50
10 Pop Stack Element
 After pop Linked List : 20 30 40 50
20 Pop Stack Element
 After pop Linked List : 30 40 50
30 Pop Stack Element
 After pop Linked List : 40 50
40 Pop Stack Element
 After pop Linked List : 50
50 Pop Stack Element
 After pop Linked List : Empty Stack
//java implement MyStack using linked list
public class MyStack{
	static Node top;
	static class Node{
		int data;
		Node next;
	}
	//Class constructors
	MyStack(){
		top=null;
	}
	static void push(int value){
		Node node=new Node(); 
		node.next=top;
		node.data=value;
		top=node;
		System.out.println("\nPush element of MyStack "+value);
		display();
	}
	static void pop(){
		if(top==null){
			System.out.println("Empty MyStack ");
		}else{
			Node temp=top;
			top=temp.next;
			System.out.println("\nPop element of MyStack "+temp.data);
			temp=null;
			display();
		}

	}
	//display all MyStack elements
	static void display(){
		if(top!=null){
			System.out.print("MyStack Elements :");
			Node temp=top;
			while(temp!=null){
				System.out.print(temp.data+" "); 
				temp=temp.next;
			}
		}else{
			if(top==null)
				System.out.println("Empty List"); 
		}
	}

	public static void main(String[] args) {
		
		top=null;//set top to null
		MyStack obj=new MyStack();
		obj.push(0);
		obj.push(1);
		obj.push(2);
		obj.push(3);
		obj.push(4);
		obj.pop();
		obj.pop();
		obj.pop();
	}
}
stack implement by linked list

Output

Push element of Stack 0
Stack Elements :0
Push element of Stack 1
Stack Elements :1 0
Push element of Stack 2
Stack Elements :2 1 0
Push element of Stack 3
Stack Elements :3 2 1 0
Push element of Stack 4
Stack Elements :4 3 2 1 0
Pop element of Stack 4
Stack Elements :3 2 1 0
Pop element of Stack 3
Stack Elements :2 1 0
Pop element of Stack 2
Stack Elements :1 0
#create class Node 
class Node:
 def __init__(self,data):
  self.data=data
  self.next=None

#create class Stack    
class Stack:
 def __init__(self):
  #Assign default value
  self.top=None

 #insert new node to Stack  
 def insert(self,data):
  node=Node(data)
  node.next=self.top
  self.top=node 
  print("Push Stack Element {0} ".format(data))

 #display all Stack list node 
 def display(self):
  temp=self.top
  while(temp!=None):
   print(temp.data),
   temp=temp.next
 

 def pop(self):
  if self.top==None:
    print("Empty Stack");
  else:
    temp=self.top
    self.top=temp.next
    print("\nPop Stack Element {0} ".format(temp.data))
    temp=None
    self.display()
#Create Object of class Stack
Stack=Stack()

#Stack list insertion
Stack.insert(1)
Stack.insert(2)
Stack.insert(3)
Stack.insert(4)
Stack.insert(5)

Stack.pop();
Stack.pop();
Stack.pop();
python stack implement by linked list

Output

Push Stack Element 1
Push Stack Element 2
Push Stack Element 3
Push Stack Element 4
Push Stack Element 5

Pop Stack Element 5
4 3 2 1
Pop Stack Element 4
3 2 1
Pop Stack Element 3
2 1
//c# program to implement stack using linked list
using System;
//Create a Node class
public class Node{
	public Node next;
	public Object data;
}
//Create a Stack class
public class Stack{
	private Node top;
	//constructor of class Stack
	public Stack(){
		//set initial stack top is null
		this.top=null; 
	}
	//display all stack elements
	public void display(){
		if(top!=null){
			Console.WriteLine("\nStack Elements");
			Node temp=top;
			while(temp!=null){
				Console.Write(temp.data+" ");
				temp=temp.next;
			}
		}else{
			Console.WriteLine("Empty Stack");
		}
	}
	//insert stack element
	public void push(Object value){
		Node node=new Node();
		node.data=value;
		node.next=top;
		top=node;
		Console.WriteLine("\nPush data {0}",value);
		display();
	}
	//delete stack elements
	public void pop(){
		if(top!=null){
			Node temp=top;
			top=temp.next;
			Console.WriteLine("\nPop data {0}",temp.data);
			temp=null;
			display();
		}else{
			Console.WriteLine("Empty Stack");
		}
	}

}
class Program{
	static void Main(string[] args){
		Stack obj=new Stack();
		//insert stack elements
		obj.push(1);
		obj.push(2);
		obj.push(3);
		obj.push(4);
		obj.push(5);
		//Delete stack elements
		obj.pop();
		obj.pop();
		obj.pop();
	}
}

Output

Push data 1

Stack Elements
1
Push data 2

Stack Elements
2 1
Push data 3

Stack Elements
3 2 1
Push data 4

Stack Elements
4 3 2 1
Push data 5

Stack Elements
5 4 3 2 1
Pop data 5

Stack Elements
4 3 2 1
Pop data 4

Stack Elements
3 2 1
Pop data 3

Stack Elements
2 1




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment