STACK
Basic concepts of Stack data structure is discussed below:
Stack :
Stack is an ordered list in which, insertion and deletion can be performed only at one end that is called top.
Stack is a recursive data structure having pointer to its top element.
Stacks are called as Last-In-First-Out (LIFO) lists i.e. the element which is inserted first in the stack, will be deleted last from the stack.
Applications of Stack :
Recursion, Expression evaluations and conversions, Parsing, Browsers, Editors, Tree Traversals
Stack Operations
Push : Adding an element onto the stack
Pop : Removing an element from the stack
The stack is called empty if it doesn't contain any element inside it. At this stage, the value of variable top is -1.
Value of top will get increased by 1 every time when we add any element to the stack. In the following stack, After adding first element, top = 2.
Array Implementation of Stack
Adding an element into the top of the stack is referred as (Push operation)
Increment the variable Top so that it can now refere to the next memory location.
Add element at the position of incremented top. This is referred to as adding new element at the top of the stack.
Deletion of an element from a stack (Pop operation)
Deletion of an element from the top of the stack is called pop operation. The value of the variable top will be incremented by 1 whenever an item is deleted from the stack.
The top most element of the stack is stored in an another variable and then the top is decremented by 1. the operation returns the deleted value that was stored in another variable as the result.
Visiting each element of the stack (Peek operation)
Peek operation involves returning the element which is present at the top of the stack without deleting it.
Underflow condition can occur if we try to return the top element in an already empty stack.
Array Implementation of Stack:
import java.util.Scanner;
class Stack
{
int top;
int maxsize = 10;
int[] arr = new int[maxsize];
boolean isEmpty()
{
return (top < 0);
}
Stack()
{
top = -1;
}
boolean push (Scanner sc)
{
if(top == maxsize-1)
{
System.out.println("Overflow !!");
return false;
}
else
{
System.out.println("Enter Value");
int val = sc.nextInt();
top++;
arr[top]=val;
System.out.println("Item pushed");
return true;
}
}
boolean pop ()
{
if (top == -1)
{
System.out.println("Underflow !!");
return false;
}
else
{
top --;
System.out.println("Item popped");
return true;
}
}
void display ()
{
System.out.println("Printing stack elements .....");
for(int i = top; i>=0;i--)
{
System.out.println(arr[i]);
}
}
}
public class Main
{
public static void main(String[] args)
{
int choice=0;
Scanner sc = new Scanner(System.in);
Stack s = new Stack();
while(choice != 4)
{
System.out.println("\n1.Push\n2.Pop\n3.Show\n4.Exit");
System.out.println("\n Enter your choice \n");
choice = sc.nextInt();
switch(choice)
{
case 1:
{
s.push(sc);
break;
}
case 2:
{
s.pop();
break;
}
case 3:
{
s.display();
break;
}
case 4:
{
System.out.println("Exiting....");
System.exit(0);
break;
}
default:
{
System.out.println("Please Enter valid choice ");
}
};
}
}
}
Just a basic array implementation program using stack with all functions
Linked List Implementation of Stack
Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory.
Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.
Adding a node to the stack (Push operation)
Create a node first and allocate memory to it.
If the list is empty then the item is to be pushed as the start node of the list. This includes assigning value to the data part of the node and assign null to the address part of the node.
If there are some nodes in the list already, then we have to add the new element in the beginning of the list (to not violate the property of the stack).
Deleting a node from the stack (POP operation)
Deleting a node from the top of stack is referred to as pop operation.
Check for the underflow condition: The underflow condition occurs when we try to pop from an already empty stack. The stack will be empty if the head pointer of the list points to null.
Adjust the head pointer accordingly: In stack, the elements are popped only from one end, therefore, the value stored in the head pointer must be deleted and the node must be freed. The next node of the head node now becomes the head node.
Display the nodes (Traversing):
Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form of stack.
Copy the head pointer into a temporary pointer.
Move the temporary pointer through all the nodes of the list and print the value field attached to every node.
Linked List Implementation of stack:
class Node
{
int data;
Node next;
};
class Stack
{
private Node top;
public Stack() {
this.top = null;
}
public void push(int x)
{
Node node = new Node();
if (node == null)
{
System.out.print("\nHeap Overflow");
return;
}
System.out.println("Inserting " + x);
node.data = x;
node.next = top;
top = node;
}
public boolean isEmpty()
{
return top == null;
}
public int peek()
{
if (!isEmpty()) {
return top.data;
}
else {
System.out.println("Stack is empty");
return -1;
}
}
public void pop()
{
if (top == null)
{
System.out.print("\nStack Underflow");
return;
}
System.out.println("Removing " + peek());
top = (top).next;
}
}
public class MyClass
{
public static void main(String[] args)
{
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("Top element is " + stack.peek());
stack.pop();
stack.pop();
stack.pop();
if (stack.isEmpty())
System.out.print("Stack is empty");
else
System.out.print("Stack is not empty");
}
}
output:
Inserting 1
Inserting 2
Inserting 3
Top element is 3
Removing 3
Removing 2
Removing 1
Stack is empty
Problems Based on stack Implementation
Expression containing Redundancy brackets or not
import java.util.*;
public class Main
{
static boolean checkRedundancy(String s)
{
Stack<Character> st = new Stack<>();
char[] str = s.toCharArray();
for (char ch : str)
{
if (ch == ')')
{
char top = st.peek();
st.pop();
boolean flag = true;
while (top != '(')
{
if (top == '+' || top == '-'|| top == '*' || top == '/')
{
flag = false;
}
top = st.peek();
st.pop();
}
if (flag == true)
{
return true;
}
}
else
{
st.push(ch);
}
}
return false;
}
static void findRedundant(String str)
{
boolean ans = checkRedundancy(str);
if (ans == true)
{
System.out.println("YES");
}
else
{
System.out.println("NO");
}
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String str = sc.next();
findRedundant(str);
}
}
input 1:
((a+b))
output 1:
YES
explanation:
redundant brackets means equal number of open and close brackets (or) nothing should be inside the brackets
input 2:
(a+(b)/c)
output 2:
YES
input 3:
(a+b*(c-d))
output 3:
NO
input 4:
()
output 4:
YES
Stock Span Problem:
import java.util.*;
public class Main
{
static void calculateSpan(int price[], int n, int S[])
{
Stack<Integer> st = new Stack<>();
st.push(0);
S[0] = 1;
for (int i = 1; i < n; i++)
{
while (!st.empty() && price[st.peek()] <= price[i])
{
st.pop();
}
S[i] = (st.empty()) ? (i + 1) : (i - st.peek());
st.push(i);
}
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the total number of stocks in the market :");
int N=sc.nextInt();
int price[] = new int[N];
for(int index=0;index<N;index++)
{
price[index]=sc.nextInt();
}
int S[] = new int[N];
calculateSpan(price, N, S);
System.out.print("The Stock Span is : "+Arrays.toString(S));
}
}
input 1:
Enter the total number of stocks in the market :
6
10 4 5 90 120 80
output 1:
The Stock Span is : [1, 1, 2, 4, 5, 1]
Check Parenthesis Matching Using stack:
import java.util.*;
public class Main
{
static class Stack
{
int top=-1;
char[] check=new char[100];
boolean isEmpty()
{
if(top==-1)
return true;
else
return false;
}
void push(char element)
{
if(top!=check.length-1)
{
check[++top]=element;
}
}
char pop()
{
char element='\0';
if(top!=-1)
{
element=check[top--];
}
return element;
}
}
static boolean isMatchingPair(char c1,char c2)
{
if(c1=='{'&&c2=='}')
return true;
else if(c1=='('&&c2==')')
return true;
else if(c1=='['&&c2==']')
return true;
else
return false;
}
static boolean ParanthesisMatch(char[] arr)
{
Stack st=new Stack();
for(int index=0;index<arr.length;index++)
{
if(arr[index]=='{'||arr[index]=='('||arr[index]=='[')
{
st.push(arr[index]);
}
if(arr[index]=='}'||arr[index]==')'||arr[index]==']')
{
if(st.isEmpty())
return false;
else if(!isMatchingPair(st.pop(),arr[index]))
{
return false;
}
}
}
if(st.isEmpty())
return true;
else
return false;
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String str=sc.next();
char[] arr=str.toCharArray();
if(ParanthesisMatch(arr))
{
System.out.print("yes");
}
else
{
System.out.print("no");
}
}
}
input 1:
[][]()[{}]()[]
output 1:
yes
input 2:
[][]([)[{}}()[]
output 2:
no
Reverse Numbers Using Stack:
import java.util.Scanner;
import java.util.Stack;
import java.util.List;
import java.util.ArrayList;
public class Main
{
static class Stack
{
List<Integer> al=new ArrayList<>();
int top=-1;
boolean isEmpty()
{
return (top == -1) ? true : false;
}
int pop()
{
return al.get(top--);
}
void push(int val)
{
top++;
al.add(val);
}
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
Stack st=new Stack();
int n=sc.nextInt();
int num=0;
for(int index=0;index<n;index++)
{
num=sc.nextInt();
st.push(num);
}
while(!st.isEmpty())
{
System.out.print(st.pop()+" ");
}
}
}
input 1:
5
10 20 30 40 50
output 1:
50 40 30 20 10
input 2:
10
19 1 9 89 50 21 72 41 28 58
output 2:
58 28 41 72 21 50 89 9 1 19
Reverse Digits using Stack:
import java.util.Scanner;
import java.util.Stack;
import java.util.List;
import java.util.ArrayList;
public class Main
{
static class Stack
{
List<Integer> al=new ArrayList<>();
int top=-1;
boolean isEmpty()
{
return (top == -1) ? true : false;
}
int pop()
{
return al.get(top--);
}
int peek()
{
return al.get(top);
}
void push(int val)
{
top++;
al.add(val);
}
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
Stack st=new Stack();
int num=sc.nextInt();
while(num!=0)
{
st.push(num%10);
num/=10;
}
int index=1,ans=0;
while(!st.isEmpty())
{
ans=ans+(st.peek()*index);
st.pop();
index*=10;
}
System.out.print(ans);
}
}
input 1:
1234
ouptut 1:
4321
input 2:
621573478
output 2:
874375126
Undo Keystroke using Stack:
import java.util.*;
public class Main
{
static int top=-1;
static List<Character> al=new ArrayList<>();
static class Stack
{
boolean isEmpty()
{
if(top==-1)
return true;
else
return false;
}
void push(char ch)
{
al.add(ch);
top++;
}
char pop()
{
char c=al.get(top);
al.remove(top);
top--;
return c;
}
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Stack st=new Stack();
String str=sc.nextLine();
int l=str.length();
for(int i=0;i<l;i++)
{
char ch=str.charAt(i);
if(ch=='*')
{
if(!st.isEmpty())
st.pop();
}
else
{
st.push(ch);
}
}
StringBuilder sb=new StringBuilder();
while(!st.isEmpty())
{
sb.append(st.pop());
}
System.out.print(sb.reverse().toString());
}
}
input 1:
tt***u
output 1:
u
input 2:
lucky * draty**w
output :
lucky draw
Story Book Stack:
import java.util.*;
public class Main
{
static class stack
{
int top=-1;
List<String> al=new ArrayList<>();
boolean isEmpty()
{
if(top==-1)
return true;
else
return false;
}
void push(String str)
{
top++;
al.add(str);
}
String pop()
{
String s=al.get(top);
al.remove(top);
top--;
return s;
}
String peek()
{
String s=al.get(top);
return s;
}
}
public static void main(String args[])
{
Stack st=new Stack();
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{
int n=sc.nextInt();
if(n==1)
{
String str=sc.nextLine();
st.push(str);
}
else if(n==2)
{
if(!st.isEmpty())
System.out.println(st.peek());
}
else if(n==-1)
{
if(!st.isEmpty())
st.pop();
}
else if(n==0)
{
System.exit(0);
}
}
}
}
input 1:
1 hello
1 hi
1 book
2
-1
2
-1
2
1 feels for the words
2
-1
-1
1 welcome to code jamm
1 learn your lessons
2
-1
2
0
output 1:
book
hi
hello
feels for the words
learn your lessons
welcome to code jamm
Find Next Greater Element using Stack:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Stack<Integer> st=new Stack<Integer>();
int n=sc.nextInt();
int[] arr=new int[n];
for(int index=0;index<n;index++)
{
arr[index]=sc.nextInt();
}
int[] ans=new int[n];
for(int index=n-1;index>=0;index--)
{
while(!st.isEmpty()&&st.peek()<=arr[index])
{
st.pop();
}
if(st.isEmpty())
{
st.push(arr[index]);
ans[index]=arr[index];
}
else
{
ans[index]=st.peek();
}
}
for(int index=0;index<n;index++)
{
System.out.print(ans[index]+" ");
}
}
}
input 1:
5
10 20 30 40 40
output 1:
20 30 40 40 40
input 2:
8
12 46 18 36 19 36 68
output 2:
46 68 36 68 36 68 76 76
Find next Smaller Element using Stack:
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Stack<Integer> st=new Stack<Integer>();
int n=sc.nextInt();
int[] arr=new int[n];
for(int index=0;index<n;index++)
{
arr[index]=sc.nextInt();
}
int[] ans=new int[n];
for(int index=n-1;index>=0;index--)
{
while(!st.isEmpty()&&st.peek()>=arr[index])
{
st.pop();
}
if(st.isEmpty())
{
st.push(arr[index]);
ans[index]=arr[index];
}
else
{
ans[index]=st.peek();
}
}
for(int index=0;index<n;index++)
{
System.out.print(ans[index]+" ");
}
}
}
/*
input 1:
5
10 20 30 40 40
output 1:
10 20 30 40 50
input 2:
8
12 46 18 36 19 36 68
output 2:
12 18 18 19 19 36 68
Remove adjacent equal elements using stack:
import java.util.*;
public class Main
{
static List<Integer> al=new ArrayList<>();
static int top=-1;
static class Stack
{
boolean isEmpty()
{
if(top==-1)
return true;
else
return false;
}
void push(int x)
{
++top;
al.add(x);
}
int pop()
{
int num=0;
if(!isEmpty())
{
num=al.get(top);
al.remove(top);
top--;
}
return num;
}
int peek()
{
int num=0;
if(!isEmpty())
{
num=al.get(top);
}
return num;
}
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
Stack st=new Stack();
int n=sc.nextInt();
for(int index=1;index<=n;index++)
{
int num=sc.nextInt();
if(st.isEmpty())
{
st.push(num);
}
else if(st.peek()==num)
{
st.pop();
}
else
{
st.push(num);
}
}
if(al.size()==0)
System.out.print("-1");
else
{
for(Integer num:al)
System.out.print(num+" ");
}
}
}
input 1:
9
10 50 30 40 40 30 50 20 90
output 1:
10 20 90
input 1:
6
30 45 80 80 45 30
output 2:
-1
Prefix evaluation using stack:
import java.util.*;
public class Main
{
static int evaluate(int num1,int num2,char c)
{
int ans=0;
if(c=='+')
ans=num1+num2;
else if(c=='-')
ans=num2-num1;
else if(c=='*')
ans=num1*num2;
else if(c=='/')
ans=num2/num1;
return ans;
}
static int prefixEvaluation(String str)
{
StringBuilder sb=new StringBuilder(str);
sb.reverse();
Stack<Integer> st=new Stack<>();
for(int index=0;index<sb.length();index++)
{
char c=sb.charAt(index);
if(c==' ')
{
continue;
}
if(c=='*'||c=='/'||c=='^'||c=='+'||c=='-')
{
int s1=st.pop();
int s2=st.pop();
int temp=evaluate(s2,s1,c);
st.push(temp);
}
else
{
StringBuilder temp=new StringBuilder();
while(Character.isDigit(c))
{
temp.append(c);
index++;
c=sb.charAt(index);
}
index--;
int num=Integer.parseInt(temp.reverse().toString());
st.push(num);
}
}
return st.pop();
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
System.out.print(prefixEvaluation(str));
}
}
input 1:
+ -2 3 / 60 * 5 6
output 1:
1
input 2:
+ -5 4 * 21 / 7 3
output 2:
43
Sorting stack using another stack:
import java.util.*;
public class Main
{
static Stack<Integer> sortStack(Stack<Integer> st,int n)
{
Stack<Integer> tempStack=new Stack<>();
while(!st.isEmpty())
{
int val=st.pop();
while(!tempStack.isEmpty()&&tempStack.peek()<val)
{
st.push(tempStack.pop());
}
tempStack.push(val);
}
return tempStack;
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
Stack<Integer> st=new Stack<>();
int n=sc.nextInt();
for(int index=0;index<n;index++)
{
st.push(sc.nextInt());
}
Stack<Integer> newStack=sortStack(st,n);
while(!newStack.isEmpty())
{
System.out.print(newStack.pop()+" ");
}
}
}
input 1:
8
1 67 29 432 357 357 451 32
output 1:
1 29 32 67 357 357 432 451
input 2:
5
1 4 5 2 3
output 2:
1 2 3 4 5
Descending sort of stack using recursion:
import java.util.*;
public class Main
{
static void sortInsert(Stack<Integer> st,int val)
{
if(st.isEmpty() || val>st.peek())
{
st.push(val);
return;
}
int temp=st.pop();
sortInsert(st,val);
st.push(temp);
}
static void sortStack(Stack<Integer> st,int n)
{
if(!st.isEmpty())
{
int val=st.pop();
sortStack(st,n);
sortInsert(st,val);
}
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
Stack<Integer> st=new Stack<>();
int n=sc.nextInt();
for(int index=0;index<n;index++)
{
st.push(sc.nextInt());
}
sortStack(st,n);
while(!st.isEmpty())
{
System.out.print(st.pop()+" ");
}
}
}
input 1:
8
1 67 29 432 357 357 451 32
output 1:
451 432 357 357 67 32 29 1
input 2:
5
1 4 5 2 3
output 2:
5 4 3 2 1
Ascending sort of stack using recursion:
import java.util.*;
public class Main
{
static void sortInsert(Stack<Integer> st,int val)
{
if(st.isEmpty() || val>st.peek())
{
st.push(val);
return;
}
int temp=st.pop();
sortInsert(st,val);
st.push(temp);
}
static void sortStack(Stack<Integer> st,int n)
{
if(!st.isEmpty())
{
int val=st.pop();
sortStack(st,n);
sortInsert(st,val);
}
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
Stack<Integer> st=new Stack<>();
int n=sc.nextInt();
for(int index=0;index<n;index++)
{
st.push(sc.nextInt());
}
sortStack(st,n);
ListIterator<Integer> itr = st.listIterator();
while(itr.hasPrevious())
{
itr.previous();
}
while(itr.hasNext())
{
System.out.print(itr.next()+" ");
}
}
}
input 1:
8
1 67 29 432 357 357 451 32
output 1:
1 29 32 67 357 357 432 451
input 2:
5
1 4 5 2 3
output 2:
1 2 3 4 5
Stack implementation using LinkedList:
import java.util.Scanner;
class Node
{
int data;
Node next=null;
}
class Stack
{
static Node top=null;
public static boolean isEmpty()
{
if(top==null)
return true;
else
return false;
}
public static void push(int element)
{
Node newNode=new Node();
if(newNode==null)
{
System.out.print("Stack is Full");
return;
}
else
{
newNode.data=element;
newNode.next=top;
top=newNode;
}
}
public static int peek()
{
if(isEmpty())
{
System.out.print("Stack is empty");
return -1;
}
else
return top.data;
}
public static void pop()
{
if(isEmpty())
{
System.out.print("Stack is empty");
return;
}
else
{
System.out.print(peek()+" ");
top=top.next;
}
}
}
public class Main
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the number of Elements: ");
int N=sc.nextInt();
System.out.println("Enter the Elements: ");
Stack stack=new Stack();
for(int index=1;index<=N;index++)
{
stack.push(sc.nextInt());
}
System.out.println("Top Element: "+stack.peek());
System.out.println("Inserted Elements in the stack are: ");
while(!stack.isEmpty())
{
stack.pop();
}
}
}
input 1:
5
1 2 3 4 5
output 1:
Enter the number of Elements:
Enter the Elements:
Top Element: 5
Inserted Elements in the stack are:
5 4 3 2 1
Check if a queue can be sorted into another queue using another stack :
import java.util.*;
public class Main
{
static boolean checkSortedQueue(Queue<Integer> queue,int n)
{
Stack<Integer> stack=new Stack<Integer>();
int count=1,temp=0;
while(!queue.isEmpty())
{
temp=queue.poll();
if(temp==count)
count++;
else
{
if(stack.isEmpty())
stack.push(temp);
else if(!stack.isEmpty()&&stack.peek()<temp)
return false;
else
stack.push(temp);
}
while(!stack.isEmpty()&&stack.peek()==count)
{
stack.pop();
count++;
}
}
if(count-1==n&&stack.isEmpty())
return true;
return false;
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
Queue<Integer> queue=new LinkedList<>();
int n=sc.nextInt();
for(int index=0;index<n;index++)
{
queue.add(sc.nextInt());
}
if(checkSortedQueue(queue,n))
System.out.print("yes");
else
System.out.print("no");
}
}
input 1:
6
5 1 2 6 3 4
output 1:
no
input 2:
5
5 1 2 3 4
output 2:
yes