Module 2

Stack

Stack is a linear list in which insertion and deletions are allowed only at one end, called top.

This data structure is also called LIFO structure (Last In First Out).

Insertion of an element into the stack is called PUSH operation.

Deletion of an element from the stack is referred as POP operation.

Basic features of Stack

1. Stack is an ordered list of similar data type.

2. Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).

3. push() function is used to insert new elements into the Stack and pop() function is used to

remove an element from the stack. Both insertion and removal are allowed at only one

end of Stack called Top.

4. Stack is said to be in Overflow state when it is completely full and is said to be

in Underflow state if it is completely empty.

Algorithm for PUSH operation

1. Check if the stack is full or not.

2. If the stack is full, then print error of overflow and exit the program.

3. If the stack is not full, then increment the top and add the element.
Algorithm for POP operation

1. Check if the stack is empty or not.

2. If the stack is empty, then print error of underflow and exit the program.

3. If the stack is not empty, then print the element at the top and decrement the top.

Applications of stack:

 Balancing of symbols

 Infix to Postfix/Prefix conversion

 Redo-undo features at many places like editors, photoshop.

 Forward and backward feature in web browsers

 Used in many algorithms likeTower of Hanoi, tree traversals etc

 Backtracking algorithm designing technique .

 String reversal is also a another application of stack.

Conditions of Stack
 Stack pointer Condition

-1 Stack Empty

0 One element in the stack

N-1 Stack Full

Implementations of Stack

Array implementation of stack

#include <stdio.h>

int stack[100],i,j,choice=0,n,top=-1;

void push();

void pop();

void show();

void main ()

printf("Enter the number of elements in the stack ");

scanf("%d",&n);

printf("*********Stack operations using array*********");

printf("\n \n");

while(choice != 4)

printf("Chose one from the below options...\n");

printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");

printf("\n Enter your choice \n");

scanf("%d",&choice);

switch(choice)

case 1:

push();

break;

case 2:

pop();

break;

case 3:

show();

break;

case 4:

printf("Exiting ... ");

break;

default:

printf("Please Enter valid choice ");

}
 };

void push ()

int val;

if (top == n )

printf("\n Overflow");

else

printf("Enter the value?");

scanf("%d",&val);

top = top +1;

stack[top] = val;

void pop ()

if(top == -1)

printf("Underflow");

else

top = top -1;

void show()

for (i=top;i>=0;i--)

{
 printf("%d\n",stack[i]);

if(top == -1)

printf("Stack is empty");

Stack Implementation using linked list

Instead of using array, we can also use linked list to implement stack. Linked list allocates the
memory dynamically.
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

Adding a node to the stack (Push operation)

1. Create a node first and allocate memory to it.

2. 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.
 3. 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). For this
purpose, assign the address of the starting element to the address field of the
new node and make the new node, the starting node of the list.

Deleting a node from the stack (POP operation)

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.

Program:

#include <stdio.h>

#include <stdlib.h>

void push();

void pop();

void display();

struct node

int val;

struct node *next;

}*top,*newnode;

void main ()

int choice=0;
printf("\n*********Stack operations using linked list*********\n");

printf("\n \n");

while(choice != 4)

printf("\n\nChose one from the below options...\n");

printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");

printf("\n Enter your choice \n");

scanf("%d",&choice);

switch(choice)

case 1:

push();

break;

case 2:

pop();

break;

case 3:

display();

break;

}
 case 4:

printf("Exiting ... ");

break;

default:

printf("Please Enter valid choice ");

void push ()

int val;

newnode = (struct node*)malloc(sizeof(struct node));

printf("Enter the value");

scanf("%d",&val);

if(top==NULL)

newnode->val = val;

newnode-> next = NULL;

top=newnode;

}
 else

newnode->val = val;

newnode->next = top;

top=newnode;

printf("Item pushed");

void pop()

int item;

struct node *temp;

if (top == NULL)

printf("Underflow");

else

temp= top;

top = top->next;

free(temp);
 printf("Item popped");

void display()

int i;

struct node *temp;

temp=top;

if(top == NULL)

printf("Stack is empty\n");

else

printf("Printing Stack elements \n");

while(temp!=NULL)

printf("%d\n",temp->val);

temp = temp->next;

}
Notation

The way to write arithmetic expression is known as a notation. An arithmetic expression can be written in three
different but equivalent notations, i.e., without changing the essence or output of an expression. These notations
are –
 Infix Notation
 Prefix (Polish) Notation
 Postfix (Reverse-Polish) Notation
These notations are named as how they use operator in expression.
Infix Notation
We write expression in infix notation, e.g. a - b + c, where operators are used in-between operands. It is easy
for us humans to read, write, and speak in infix notation but the same does not go well with computing devices.
An algorithm to process infix notation could be difficult and costly in terms of time and space consumption.
Prefix Notation
In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For
example, +ab. This is equivalent to its infix notation a + b. Prefix notation is also known as Polish Notation.
Postfix Notation
This notation style is known as Reversed Polish Notation. In this notation style, the operator is postfixed to the
operands i.e., the operator is written after the operands. For example, ab+.This is equivalent to its infix
notation a + b.

To evaluate any arithmetic expression, we need to take care of operator precedence and associativity also.

Precedence
When an operand is in between two different operators, which operator will take the operand first, is decided
by the precedence of an operator over others. For example –
A + B * C → A + (B * C)
As the multiplication operator has a higher precedence over the addition operator so B * C expression will be
evaluated first. The result of the multiplication of B * C is added to the A.
Precedence order

Operators Symbols

Parenthesis { }, ( ), [ ]

Exponential notation ^

Multiplication and Division *, /

Addition and Subtraction +, -

Associativity
Associativity describes the rule where operators with the same precedence appear in an expression. For
example, in expression a + b − c, both + and – have the same precedence, then which part of the expression
will be evaluated first, is determined by associativity of those operators. Here, both + and − are left
associative, so the expression will be evaluated as (a + b)− c.

Associativity order
Operators Associativity

^ Right to Left

*, / Left to Right

+, - Left to Right

Conversion of infix to postfix Expression

Here, we will use the stack data structure for the conversion of infix expression to postfix expression.
Whenever an operator will encounter, we push operator into the stack. If we encounter an operand, then we
append the operand to the expression.

Rules for the conversion from infix to postfix expression

1. Print the operand as they arrive.

2. If the stack is empty or contains a left parenthesis on top, push the incoming operator on to the stack.
3. If the incoming symbol is '(', push it on to the stack.
4. If the incoming symbol is ')', pop the stack and print the operators until the left parenthesis is found.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
6. If the incoming symbol has lower precedence than the top of the stack, pop and print the top of the
stack. Then test the incoming operator against the new top of the stack.
7. If the incoming operator has the same precedence with the top of the stack then use the associativity
rules. If the associativity is from left to right then pop and print the top of the stack then push the
incoming operator. If the associativity is from right to left then push the incoming operator.
8. At the end of the expression, pop and print all the operators of the stack.

Example1
Convert the infix expression A+B*C to its postfix form.
Step input action stack Output
1 A+B*C Write to target empty A
2 +B*C push + A
3 B*C Write to target + AB
4 *C Push +* AB
 5 C Write to target +* ABC
6 Pop * + ABC*
7 Pop + empty ABC*+

Example 2
Convert the infix expression A*(B-C) to its postfix form.

Step input action stack Output

1 A*(B-C) Write to target empty A
2 *(B-C) push * A
3 (B-C) Push *( A
4 B-C) Write to target *( AB
5 -C) push - *(- AB
6 C) Write to target *(- ABC
7 ) Pop - * ABC-
8 Pop * ABC-*

Queue
Queue is a linear list in which elements can be inserted only at one end called rear and deleted only at the other
end called front. It is of the type FIFO (First In First Out). which means that element inserted first will be
removed first.
Insertion operation is called enqueue
Deletion operation is called dequeue

Algorithm for ENQUEUE operation

1. Check if the queue is full or not.(rear=maxsize-1)
2. If the queue is full, then print overflow error and exit the program.
3. If the queue is not full, then increment the rear and add the element.
Algorithm for DEQUEUE operation
1. Check if the queue is empty or not.(rear=-1)
2. If the queue is empty, then print queue is empty and exit the program.
3. If the queue is not empty, then delete the element at the front and increment the front

Operations performed on queue

The fundamental operations that can be performed on queue are listed as follows -

o Enqueue: The Enqueue operation is used to insert the element at the rear end of the queue. It returns
void.
o Dequeue: It performs the deletion from the front-end of the queue. It also returns the element which
has been removed from the front-end. It returns an integer value.
o Peek: This is the third operation that returns the element, which is pointed by the front pointer in the
queue but does not delete it.
o Queue overflow (isfull): It shows the overflow condition when the queue is completely full.
o Queue underflow (isempty): It shows the underflow condition when the Queue is empty, i.e., no
elements are in the Queue.

Conditions of Queue

Pointers(Rear ,Front) Condition

Front=-1 and rear=-1 Queue empty
Front=0 and rear=0 One element in the queue
Rear=N-1 Queue full

Array implementation of Queue

Algorithm to insert any element in a queue

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.

Otherwise keep increasing the value of rear and insert each element one by one having rear as the index.

Algorithm to delete an element from the queue

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.
Program:-

#include<stdio.h>

#include<stdlib.h>

void enqueue();

void dequeue();

void display();

int front = -1, rear = -1,size;

int queue[100];

void main ()

int choice;

printf("enter the size of the queue");

scanf("%d",&size);

while(choice != 4)

printf("\n*************************Main Menu*****************************\n");

printf("\n=================================================================\n");

printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");

printf("\nEnter your choice ?");

scanf("%d",&choice);

switch(choice)

case 1:

enqueue();

break;

case 2:
 dequeue();

break;

case 3:

display();

break;

case 4: exit(0);

break;

default:

printf("\nEnter valid choice??\n");

void enqueue()

int item;

printf("\nEnter the element\n");

scanf("\n%d",&item);

if(rear == size-1)

printf("\nOVERFLOW\n");

return;

if(front == -1 && rear == -1)

front = 0;

rear = 0;
 }

else

rear = rear+1;

queue[rear] = item;

printf("\nValue inserted ");

void dequeue()

int item;

if (front == -1 && rear==-1)

printf("\nUNDERFLOW\n");

return;

else if(front==rear)

front=rear=-1;

else

front++;

printf("\nvalue deleted ");

}
void display()

int i;

if(rear == -1)

printf("\nEmpty queue\n");

else

{ printf("\nprinting values .....\n");

for(i=front;i<=rear;i++)

printf("\n%d\n",queue[i]);

Linked List Implementation of Queue

In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear
pointer. The front pointer contains the address of the starting element of the queue while the rear
pointer contains the address of the last element of the queue.

Insertion and deletions are performed at rear and front end respectively. If front and rear both are
NULL, it indicates that the queue is empty.

The linked representation of queue is shown in the following figure.

Insert operation

The insert operation append the queue by adding an element to the end of the queue. The new
element will be the last element of the queue.

Firstly, allocate the memory for the new node ptr by using the following statement.

newnode= (struct node *) malloc (sizeof(struct node));

There can be the two scenario of inserting this newnode into the linked queue.

In the first scenario, we insert element into an empty queue. In this case, the condition front =
NULL becomes true. Now, the new element will be added as the only element of the queue and the
next pointer of front and rear pointer both, will point to NULL.

In the second scenario, we need to update the end pointer rear so that the next pointer of rear will
point to the newnode

Deletion

Deletion operation removes the element that is first inserted among all the queue elements. Firstly,
we need to check either the list is empty or not. The condition front == NULL becomes true if the list
is empty, in this case , we simply write underflow on the console and make exit.

Otherwise, we will delete the element that is pointed by the pointer front. For this purpose, copy the
node pointed by the front pointer into the pointer temp. Now, shift the front pointer, point to its
next node and free the node pointed by the node temp. This is done by using the following
statements.

temp = front;
front = front -> next;
free(temp);

Program;-

#include<stdio.h>

#include<stdlib.h>

struct node

int data;

struct node *next;

}*front,*rear,*newnode;
void enqueue();

void dequeue();

void display();

void main ()

int choice;

while(choice != 4)

printf("\n*************************Main Menu*****************************\n");

printf("\n===========================================================
======\n");

printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");

printf("\nEnter your choice ?");

scanf("%d",& choice);

switch(choice)

case 1:

enqueue();

break;

case 2:

dequeue();

break;

case 3:

display();

break;
 case 4:

exit(0);

break;

default:

printf("\nEnter valid choice??\n");

void enqueue()

int item;

newnode=(struct node *) malloc(sizeof(struct node));

printf("\nEnter value?\n");

scanf("%d",&item);

newnode-> data = item;

newnode->next=NULL;

if(front == NULL)

front = rear=newnode

else

rear -> next = newnode;

rear = newnode;
 }

void dequeue ()

struct node *temp;

if(front == NULL)

printf("\nUNDERFLOW\n");

return;

else

temp= front;

front = front -> next;

free(temp);

void display()

struct node *temp;

temp= front;

if(front == NULL)

printf("\nEmpty queue\n");

}
 else

{ printf("\nprinting values .....\n");

while(temp!= NULL)

printf("\n%d\n",temp -> data);

temp = temp-> next;

Applications of Queue
 Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
 In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order,
until a service representative is free.
 Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive
i.e First come first served.
 Queues are widely used as waiting lists for a single shared resource like printer, disk,CPU.

Types of Queues in Data Structure

Queue in data structure is of the following types
1. Priority Queue
2. Deque (Double Ended Queue)
3. Circular queue

Deque

The deque stands for Double Ended Queue. Deque is a linear data structure where the insertion and deletion
operations are performed from both ends. We can say that deque is a generalized version of the queue.

Though the insertion and deletion in a deque can be performed on both ends, it does not follow the FIFO rule.
The representation of a deque is given as follows –
Types of deque

There are two types of deque -

1. Input restricted queue

2. Output restricted queue

Input restricted Queue

In input restricted queue, insertion operation can be performed at only one end, while deletion can
be performed from both ends.

Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end, while insertion can
be performed from both ends.

Applications of deque
o Deque can be used as both stack and queue, as it supports both operations.
o Deque can be used as a palindrome checker means that if we read the string from both ends,
the string would be the same.
Priority Queue
A priority queue is an abstract data type that behaves similarly to the normal queue except that each element
has some priority, i.e., the element with the highest priority would come first in a priority queue. The priority
of the elements in a priority queue will determine the order in which elements are removed from the priority
queue.
The priority queue supports only comparable elements, which means that the elements are either arranged
in an ascending or descending order.

Characteristics of a Priority queue

A priority queue is an extension of a queue that contains the following characteristics:

o Every element in a priority queue has some priority associated with it.
o An element with the higher priority will be deleted before the deletion of the lesser priority.
o If two elements in a priority queue have the same priority, they will be arranged using the FIFO
principle.

Types of Priority Queue

There are two types of priority queue:

o Ascending order priority queue: In ascending order priority queue, a lower priority number is given
as a higher priority in a priority. For example, we take the numbers from 1 to 5 arranged in an
ascending order like 1,2,3,4,5; therefore, the smallest number, i.e., 1 is given as the highest priority in
a priority queue.
 o Descending order priority queue: In descending order priority queue, a higher priority number is
given as a higher priority in a priority. For example, we take the numbers from 1 to 5 arranged in
descending order like 5, 4, 3, 2, 1; therefore, the largest number, i.e., 5 is given as the highest priority
in a priority queue.

Circular Queue
A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle
except that the last position is connected to the first position in a circular queue that forms a circle. It is also
known as a Ring Buffer.

There was one limitation in the array implementation of Queue. If the rear reaches to the end position of the
Queue then there might be possibility that some vacant spaces are left in the beginning which cannot be
utilized. So, to overcome such limitations, the concept of the circular queue was introduced.

we can see in the above image, the rear is at the last position of the Queue and front is pointing somewhere
rather than the 0th position. In the above array, there are only two elements and other three positions are empty.
The rear is at the last position of the Queue; if we try to insert the element then it will show that there are no
empty spaces in the Queue. There is one solution to avoid such wastage of memory space by shifting both the
elements at the left and adjust the front and rear end accordingly. It is not a practically good approach because
shifting all the elements will consume lots of time. The efficient approach to avoid the wastage of the memory
is to use the circular queue data structure.
 Comparison of FIFO vs. LIFO datastructures

FIFO LIFO

It stands for First-In-First-Out approach in It stands for Last-In-First-Out approach in

programming. programming.

In this, the new element is inserted below the In this, the new element is inserted above the
existing element, So that the oldest element can existing element, So that the newest element can be
be at the top and taken out first. at the top and taken out first.

Therefore, the first element to be entered in this Therefore, the first element to be entered in this
approach, gets out First. approach, gets out Last.
FIFO LIFO

In computing, FIFO approach is used as an In computing, LIFO approach is used as a queuing

operating system algorithm, which gives every theory that refers to the way items are stored in
process CPU time in the order they arrive. types of data structures.

Time complexity of inserting element in FIFO is Time complexity of inserting element in LIFO is
O(1). O(1).

The data structure that implements FIFO is

Queue. The data structure that implements LIFO is Stack.

The following are the differences between the stack and queue:
Basis for Stack Queue
comparison

Principle It follows the principle LIFO It follows the principle FIFO (First In -First
(Last In- First Out), which implies Out), which implies that the element which is
that the element which is inserted added first would be the first element to be
last would be the first one to be removed from the list.
deleted.

Structure It has only one end from which It has two ends, i.e., front and rear end. The
both the insertion and deletion front end is used for the deletion while the
take place, and that end is known rear end is used for the insertion.
as a top.

Number of It contains only one pointer It contains two pointers front and rear pointer.
pointers used known as a top pointer. The top The front pointer holds the address of the first
pointer holds the address of the element, whereas the rear pointer holds the
last inserted or the topmost address of the last element in a queue.
element of the stack.

Operations It performs two operations, push It performs mainly two operations, enqueue
performed and pop. The push operation and dequeue. The enqueue operation
inserts the element in a list while performs the insertion of the elements in a
the pop operation removes the queue while the dequeue operation performs
element from the list. the deletion of the elements from the queue.

Examination of If top==-1, which means that the If front== -1 or front = rear+1, which means
the empty stack is empty. that the queue is empty.
condition
Examination of If top== max-1, this condition If rear==max-1, this condition implies that
full condition implies that the stack is full. the stack is full.

Variants It does not have any types. It is of three types like priority queue, circular
queue and double ended queue.