Stack
Stack
Page 1 of 48
Page 2 of 48
Topic cover:
• Array implementation
• LinkedList implementation
• Applications of stack
o evaluation
• Brackets grouping
In array implementation, the stack is formed by using the array. All the operations regarding the stack
are performed using arrays. Lets see how each operation can be implemented on the stack using array
data structure.
Adding an element into the top of the stack is referred to as push operation. Push operation involves
following two steps.
1. Increment the variable Top so that it can now refere to the next memory location.
2. Add element at the position of incremented top. This is referred to as adding new element at
the top of the stack.
Page 3 of 48
Stack is overflown when we try to insert an element into a completely filled stack therefore, our main
function must always avoid stack overflow condition.
Algorithm:
begin
top = top + 1
end
Time Complexity : o(1)
Page 4 of 48
The underflow condition occurs when we try to delete an element from an already empty stack.
Algorithm :
begin
if top = 0 then stack empty;
item := stack(top);
top = top - 1;
end;
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.
Algorithm :
Begin
if top = -1 then stack empty
item = stack[top]
return item
End
Page 5 of 48
Time complexity: o(n)
import java.util.Scanner;
class Stack
int top;
boolean isEmpty()
Stack()
top = -1;
Page 6 of 48
}
if(top == maxsize-1)
System.out.println("Overflow !!");
return false;
else
top++;
arr[top]=val;
System.out.println("Item pushed");
return true;
boolean pop ()
if (top == -1)
System.out.println("Underflow !!");
return false;
Page 7 of 48
else
top --;
System.out.println("Item popped");
return true;
void display ()
System.out.println(arr[i]);
class Main {
int choice=0;
//System.out.println("\n------------------------------------------------\n");
while(choice != 4)
Page 8 of 48
// System.out.println("\nChose one from the below options...\n");
System.out.println("\n1.Push\t2.Pop\t3.Show\t4.Exit");
choice = sc.nextInt();
switch(choice)
case 1:
s.push(sc);
break;
case 2:
s.pop();
break;
case 3:
s.display();
break; 8/
case 4:
System.out.println("Exiting....");
System.exit(0);
Page 9 of 48
break;
default:
};
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.
Page 10 of 48
The top most node in the stack always contains null in its address field. Lets discuss the way in which,
each operation is performed in linked list implementation of stack.
Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked list
implementation is different from that of an array implementation. In order to push an element onto
the stack, the following steps are involved.
Page 11 of 48
Code:
Page 12 of 48
Deleting a node from the stack (POP operation)
Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked
list implementation of stack is different from that in the array implementation. In order to pop an
element from the stack, we need to follow the following steps :
1. 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.
2. 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.
Time Complexity : o(n)
Code:
Page 13 of 48
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. For this purpose, we need to follow the following steps.
Code:
Java implementation:
Page 14 of 48
class StackUsingLinkedlist {
Node top;
// Constructor
StackUsingLinkedlist()
this.top = null;
// check if stack (heap) is full. Then inserting an element would lead to stack overflow
if (temp == null) {
System.out.print("\nHeap Overflow");
Page 15 of 48
return;
temp.data = x;
temp.link = top;
top = temp;
if (!isEmpty()) {
return top.data;
Page 16 of 48
}
else {
System.out.println("Stack is empty");
return -1;
if (top == null) {
System.out.print("\nStack Underflow");
return;
top = (top).link;
if (top == null) {
System.out.printf("\nStack Underflow");
Page 17 of 48
exit(1);
else {
System.out.printf("%d->", temp.data);
temp = temp.link;
// main class
class Main {
obj.push(11);
obj.push(22);
obj.push(33);
Page 18 of 48
obj.push(44);
obj.display();
obj.pop();
obj.pop();
obj.display();
Applications of Stack
1. Recursion
2. Expression evaluations and conversions
3. Parsing
4. Browsers
5. Editors
6. Tree Traversals
Page 19 of 48
Infix to Postfix conversion:
Infix expression:The expression of the form a op b. When an operator is in-between every pair of
operands.
Postfix expression:The expression of the form a b op. When an operator is followed for every pair of
operands.
Example:
• ^ (Exponential)
• /*
• +–
Note: brackets ( ) are used to override these rules.
Algorithm:
Page 20 of 48
6. Repeat steps 2-6 until infix expression is scanned.
7. Print the output
8. Pop and output from the stack until it is not empty.
Java Implementation:
import java.util.Stack;
class Main
Page 21 of 48
static int Prec(char ch)
switch (ch)
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
return -1;
// to postfix expression.
Page 22 of 48
// initializing empty stack
char c = exp.charAt(i);
if (Character.isLetterOrDigit(c))
result += c;
else if (c == '(')
stack.push(c);
// If the scanned character is an ')', pop and output from the stack
else if (c == ')')
result += stack.pop();
Page 23 of 48
else
stack.pop();
if(stack.peek() == '(')
result += stack.pop();
stack.push(c);
while (!stack.isEmpty()){
if(stack.peek() == '(')
result += stack.pop();
return result;
// Driver method
Page 24 of 48
public static void main(String[] args)
System.out.println(infixToPostfix(exp));
Brackets Grouping
Given an expression string exp , write a program to examine whether the pairs and the orders of
“{“,”}”,”(“,”)”,”[“,”]” are correct in exp.
Output: Balanced
Algorithm:
Page 25 of 48
Page 26 of 48
Code:
// balanced Parenthesis
class Main
int top=-1;
Page 27 of 48
void push(char x)
if (top == 99)
System.out.println("Stack full");
else
items[++top] = x;
char pop()
if (top == -1)
System.out.println("Underflow error");
return '\0';
else
top--;
return element;
Page 28 of 48
}
boolean isEmpty()
return true;
return true;
return true;
else
return false;
Parenthesis */
Page 29 of 48
{
for(int i=0;i<exp.length;i++)
st.push(exp[i]);
/* If exp[i] is an ending parenthesis then pop from stack and check if the popped
parenthesis is a matching pair*/
if (st.isEmpty())
return false;
/* Pop the top element from stack, if it is not a pair parenthesis of character then
there is a mismatch. This happens for expressions like {(}) */
return false;
Page 30 of 48
}
/* If there is something left in expression then there is a starting parenthesis without a closing
parenthesis */
if (st.isEmpty())
else
{ /*not balanced*/
return false;
/* UTILITY FUNCTIONS */
if (areParenthesisBalanced(exp))
System.out.println("Balanced ");
else
Page 31 of 48
QUEUE
Like Stack, Queue is a linear structure which follows a particular order in which the operations are
performed. The order is First In First Out (FIFO). A good example of queue is any queue of consumers
for a resource where the consumer that came first is served first.
The difference between stacks and queues is in removing. In a stack we remove the item the most
recently added; in a queue, we remove the item the least recently added.
Operations on Queue:
Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
Dequeue: Removes an item from the queue. The items are popped in the same order in which they are
pushed. If the queue is empty, then it is said to be an Underflow condition.
Page 32 of 48
Topics to be covered:
1. Array implementation
2. Constructing stack using queue
3. applications
We can easily represent queue by using linear arrays. There are two variables i.e. front and rear, that
are implemented in the case of every queue. Front and rear variables point to the position from where
insertions and deletions are performed in a queue. Initially, the value of front and queue is -1 which
represents an empty queue. Array representation of a queue containing 5 elements along with the
respective values of front and rear, is shown in the following figure.
Page 33 of 48
The above figure shows the queue of characters forming the English word "HELLO". Since, No deletion
is performed in the queue till now, therefore the value of front remains -1 . However, the value of rear
increases by one every time an insertion is performed in the queue. After inserting an element into the
queue shown in the above figure, the queue will look something like following. The value of rear will
become 5 while the value of front remains same.
After deleting an element, the value of front will increase from -1 to 0. however, the queue will look
something like following.
Check if the queue is already full by comparing rear to max - 1. if so, then return an overflow error.
If the item is to be inserted as the first element in the list, in that case set the value of front and rear to
0 and insert the element at the rear end.
Page 34 of 48
Otherwise keep increasing the value of rear and insert each element one by one having rear as the
index.
If, the value of front is -1 or value of front is greater than rear , write an underflow message and exit.
Otherwise, keep increasing the value of front and return the item stored at the front end of the queue
at each time.
Page 35 of 48
Code
class Queue
int capacity;
int array[];
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
Page 36 of 48
}
if (isFull(this))
return;
this.array[this.rear] = item;
this.size = this.size + 1;
int dequeue()
Page 37 of 48
if (isEmpty(this))
return Integer.MIN_VALUE;
this.size = this.size - 1;
return item;
int front()
if (isEmpty(this))
return Integer.MIN_VALUE;
return this.array[this.front];
int rear()
if (isEmpty(this))
return Integer.MIN_VALUE;
return this.array[this.rear];
Page 38 of 48
}
// Driver class
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
Page 39 of 48
Although, the technique of creating a queue is easy, but there are some drawbacks of using this
technique to implement a queue.
Memory wastage : The space of the array, which is used to store queue elements, can never be reused
to store the elements of that queue because the elements can only be inserted at front end and the
value of front might be so high so that, all the space before that, can never be filled.
The above figure shows how the memory space is wasted in the array representation of queue. In the
above figure, a queue of size 10 having 3 elements, is shown. The value of the front variable is 5,
therefore, we can not reinsert the values in the place of already deleted element before the position of
front. That much space of the array is wasted and can not be used in the future (for this queue).
On of the most common problem with array implementation is the size of the array which requires to
be declared in advance. Due to the fact that, the queue can be extended at runtime depending upon
the problem, the extension in the array size is a time taking process and almost impossible to be
performed at runtime since a lot of reallocations take place. Due to this reason, we can declare the
array large enough so that we can store queue elements as enough as possible but the main problem
with this declaration is that, most of the array slots (nearly half) can never be reused. It will again lead
to memory wastage.
The problem is opposite of this post. We are given a Queue data structure that supports standard
operations like enqueue() and dequeue(). We need to implement a Stack data structure using only
instances of Queue and queue operations allowed on the instances.
Page 40 of 48
A stack can be implemented using two queues. Let stack to be implemented be ‘s’ and queues used to
implement be ‘q1’ and ‘q2’. Stack ‘s’ can be implemented in two ways:
Algorithm:
Push
The new element is always added to the rear of queue q1 and it is kept as top stack element
Page 41 of 48
s
Java
q1.add(x);
top = x;
Pop:
We need to remove the element from the top of the stack. This is the last inserted element in q1.
Because queue is FIFO (first in - first out) data structure, the last inserted element could be removed
only after all elements, except it, have been removed. For this reason we need to maintain additional
queue q2, which will serve as a temporary storage to enqueue the removed elements from q1. The last
inserted element in q2 is kept as top. Then the algorithm removes the last element in q1. We swap q1
with q2 to avoid copying all elements from q2 to q1.
Page 42 of 48
Java:
top = q1.remove();
q2.add(top);
q1.remove();
q1 = q2;
Page 43 of 48
q2 = temp;
Java Implementation:
two queue */
import java.util.*;
class Main {
// elements
Stack()
curr_size = 0;
Page 44 of 48
curr_size++;
q2.add(x);
// elements in q1 to q2.
while (!q1.isEmpty()) {
q2.add(q1.peek());
q1.remove();
Queue<Integer> q = q1;
q1 = q2;
q2 = q;
if (q1.isEmpty())
return;
q1.remove();
Page 45 of 48
curr_size--;
if (q1.isEmpty())
return -1;
return q1.peek();
return curr_size;
// driver code
s.push(1);
s.push(2);
s.push(3);
Page 46 of 48
System.out.println(s.top());
s.pop();
System.out.println(s.top());
s.pop();
System.out.println(s.top());
Queue Application:
Queue is used when things don’t have to be processed immediately, but have to be processed in First
In First Out order like Breadth First Search. This property of Queue makes it also useful in following
kind of scenarios.
1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk
Scheduling.
2) When data is transferred asynchronously (data not necessarily received at same rate as sent)
between two processes. Examples include IO Buffers, pipes, file IO, etc.
Page 47 of 48
Page 48 of 48