Skip to main content

Stack Data Structure

Stack is simplest and very useful commonly used data structure. There is based on First In Last Out(FILO) or , In other word Last In First Out(LIFO). That means most recently added element is removing of first. There are main two operation of this data structure. Inserting element that is called push operation and removing element of Top of stack that is called pop operation.

stack Data Structure

Stack are restricted to insert and delete element in single end. So active state of stack is top section and inactive is bottom section. because push() and pop() operation are will be performed in top section of stack.

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

Stack Examples

Recursion is completely based on stack data structure. Because function calling execution are create new namespace of that function, and allocate memory of it's local variables. local variable are is parameter of function and declared variables of that function.

Application of stacks

There is lot of application of stack data structures.

Evaluation of Expression: Possible to evaluate the postfix, infix, perfix expression by using of stack

Recursion: function calling execution is managed by stack.

Complexity analysis

Operation Complexity
Insertion O(1)
Deletion O(1)
Searching O(n)
Space O(n)
Last updated on by Kalkicode




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