# 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 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){
}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();
}``````

#### 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();
}
}``````

#### 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();
``````

#### 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.