ACADEMIC YEAR :2018-19

BATCH :2017-2021

YEAR/SEM :II/III

SUB CODE : CS8391

SUB TITLE : DATA STRUCTURS

UNIT-II-NOTES
LINEAR DATA STRUCTURES-STACKS, QUEUES
PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

UNIT II LINEAR DATA STRUCTURES – STACKS, QUEUES 9

Stack ADT – Operations - Applications - Evaluating arithmetic expressions- Conversion of Infix to
postfix expression - Queue ADT – Operations - Circular Queue – Priority Queue - deQueue – applications
of queues

STACK

 Stack is a Linear Data Structure that follows Last In First Out(LIFO) principle.
 Insertion and deletion can be done at only one end of the stack called TOP of the stack.
 Example: - Pile of coins, stack of trays

STACK ADT:

STACK MODEL

TOP pointer

It will always point to the last element inserted in the stack.

For empty stack, top will be pointing to -1. (TOP = -1)

Operations on Stack (Stack ADT)

Two fundamental operations performed on the stack are PUSH and POP.

(a) PUSH:

It is the process of inserting a new element at the Top of the stack.

For every push operation:

1. Check for Full stack ( overflow ).

2. Increment Top by 1. (Top = Top + 1)

CS6202 1 PDS-1NOTES
PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

3. Insert the element X in the Top of the stack.

(b) POP:

It is the process of deleting the Top element of the stack.

For every pop operation:

1. Check for Empty stack ( underflow ).

2. Delete (pop) the Top element X from the stack
3. Decrement the Top by 1. (Top = Top - 1 )

Exceptional Conditions of stack

1. Stack Overflow


An Attempt to insert an element X when the stack is Full, is said to be stack
overflow.
 For every Push operation, we need to check this condition.
2. Stack Underflow:

 An Attempt to delete an element when the stack is empty, is said to be stack

underflow.
 For every Pop operation, we need to check this condition.

12.4 Implementation of Stack

Stack can be implemented in 2 ways.

1. Static Implementation (Array implementation of Stack)

2. Dynamic Implementation (Linked List Implementation of Stack)

12.4.1 Array Implementation of Stack

 Each stack is associated with a Top pointer.

 For Empty stack, Top = -1.
 Stack is declared with its maximum size.
Array Declaration of Stack:
#define ArraySize 5
int S [ Array Size];
or
int S [ 5 ];

CS8391 2 DATA STRUCTURES

 PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

(i) Stack Empty Operation:

 Initially Stack is Empty.
 With Empty stack Top pointer points to – 1.
 It is necessary to check for Empty Stack before deleting (pop) an element from the stack.

Routine to check whether stack is empty

int IsEmpty ( Stack S )

{
if( Top = = - 1 )
return(1);
}

(ii) Stack Full Operation:

 As we keep inserting the elements, the Stack gets filled with the elements.
 Hence it is necessary to check whether the stack is full or not before inserting a new
element into the stack.

Routine to check whether a stack is full

int IsFull ( Stack S )

{ if( Top = = Arraysize – 1 )

return(1);

(ii) Push Operation

 It is the process of inserting a new element at the Top of the stack.
 It takes two parameters. Push(X, S) the element X to be inserted at the Top of the Stack
S.
 Before inserting an Element into the stack, check for Full Stack.
 If the Stack is already Full, Insertion is not possible.

CS8391 3 DATA STRUCTURES

 PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

 Otherwise, Increment the Top pointer by 1 and then insert the element X at the Top of the
Stack.
Routine to push an element into the stack

void Push ( int X , Stack S )

{
if ( Top = = Arraysize - 1)
Error(“Stack is full!!Insertion is not possible”);
else
{ Top = Top + 1;
S [ Top ] =X;
}
}
(iv) Pop Operation
 It is the process of deleting the Top element of the stack.
 It takes only one parameter. Pop(X).The element X to be deleted from the Top of the
Stack.
 Before deleting the Top element of the stack, check for Empty Stack.
 If the Stack is Empty, deletion is not possible.
 Otherwise, delete the Top element from the Stack and then decrement the Top pointer by
1.
Routine to Pop the Top element of the stack
void Pop ( Stack S )
{
if ( Top = = - 1)
Error ( “Empty stack! Deletion not possible”);
else
{ X = S [ Top ] ;
Top = Top – 1 ;
}
}

CS8391 4 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

(v) Return Top Element

 Pop routine deletes the Top element in the stack.
 If the user needs to know the last element inserted into the stack, then the user can return
the Top element of the stack.
 To do this, first check for Empty Stack.
 If the stack is empty, then there is no element in the stack.
 Otherwise, return the element which is pointed by the Top pointer in the Stack.

Routine to return top Element of the stack

int TopElement(Stack S)
{
if(Top==-1)
{
Error(“Empty stack!!No elements”);
return 0;
}
else
return S[Top];
}

Implementation of stack using Array

/* static implementation of stack*/

#include<stdio.h>
#include<conio.h>
#define size 5
int stack [ size ];
int top;
void push( )
{
int n ;
printf( "\n Enter item in stack" ) ;
scanf( " %d " , &n ) ;
if( top = = size - 1)
{
printf( "\nStack is Full" ) ;
}
else
{
top = top + 1 ;

CS8391 5 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

stack [ top ] = n ;
}
}
void pop( )
{
int item;
if( top = = - 1)
{
printf( "\n Stack is empty" );
}
else
{
item = stack[ top ] ;
printf( "\n item popped is = %d" , item );
top - -;
}
}
void display( )
{
int i;
printf("\n item in stack are");
for(i = top; i > = 0; i --)
printf("\n %d", stack[ i ] );
}
void main( )
{
char ch,ch1;
ch = 'y';
ch1 = 'y';
top = -1;
clrscr( );
while(ch !='n')
{
push( );
printf("\n Do you want to push any item in stack y/n");
ch=getch( );
}
display( );
while( ch1!='n' )
{
printf("\n Do you want to delete any item in stack y/n");
ch1=getch( );
pop( );
}
display( );
getch( );}

CS8391 6 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

OUTPUT:
Enter item in stack20
Do you want to push any item in stack y/n
Enter item in stack25
Do you want to push any item in stack y/n
Enter item in stack30
Stack is Full
Do you want to push any item in stack y/n
item in stack are
25
20
15
10
5
Do you want to delete any item in stack y/n
item popped is = 25
Do you want to delete any item in stack y/n
item popped is = 20
Do you want to delete any item in stack y/n
item popped is = 15
item in stack are
10
5
Linked list implementation of Stack
 Stack elements are implemented using SLL (Singly Linked List) concept.
 Dynamically, memory is allocated to each element of the stack as a node.
Type Declarations for Stack using SLL
struct node;
typedef struct node *stack;
typedef struct node *position;
stack S;
struct node{
int data;
position next;};
int IsEmpty(Stack S);
void Push(int x, Stack S);
void Pop(Stack S);
int TopElement(Stack S);

CS8391 7 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

(i) Stack Empty Operation:

 Initially Stack is Empty.
 With Linked List implementation, Empty stack is represented as S -> next = NULL.
 It is necessary to check for Empty Stack before deleting ( pop) an element from the stack.
Routine to check whether the stack is empty S

int IsEmpty( Stack S)

HEADER NULL
{
if ( S -> next = = NULL)
return ( 1 ); EMPTY STACK
}

(ii) Push Operation

 It is the process of inserting a new element at the Top of the stack.
 With Linked List implementation, a new element is always inserted at the Front of the
List.(i.e.) S -> next.
 It takes two parameters. Push(X, S) the element X to be inserted at the Top of the StackS.
 Allocate the memory for the newnode to be inserted.
 Insert the element in the data field of the newnode.
 Update the next field of the newnode with the address of the next node which is stored
in the S -> next.

Header

30 20 10 NULL

40

newnode
Before Insertion

CS8391 8 DATA STRUCTURES

 PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Push routine /*Inserts element at front of the list

void push(int X, Stack S)
{
Position newnode, Top;
newnode = malloc (sizeof( struct node ) );
newnode -> data = X;
newnode -> next = S -> next;
S -> next = newnode;
Top = newnode;
}

Header

40 30 20 10 NULL

After Insertion

TOP
(iii) Pop Operation
 It is the process of deleting the Top element of the stack.
 With Linked List implementations, the element at the Front of the List
(i.e.) S -> next is always deleted.
 It takes only one parameter. Pop(X).The element X to be deleted from the Front of the
List.
 Before deleting the front element in the list, check for Empty Stack.
 If the Stack is Empty, deletion is not possible.
 Otherwise, make the front element in the list as “temp”.
 Update the next field of header.
 Using free ( ) function, Deallocate the memory allocated for temp node.

CS8391 9 DATA STRUCTURES

 PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE
S

Header

40 30 20 10 NULL

TOP
Before Deletion
Pop routine /*Deletes the element at front of list
void Pop( Stack S )
{
Position temp, Top;
Top = S -> next;
if( S -> next = = NULL)
Error(“empty stack! Pop not possible”);
else
{
Temp = S -> next;
S -> next = temp -> next;
free(temp);
Top = S -> next;
}}

S
Header

40 30 20 10 NULL

Temp
S

HEADER

30 20 10 NULL
After Deletion

CS8391 10 DATA STRUCTURES

TOP
 PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

(iv) Return Top Element

 Pop routine deletes the Front element in the List.
 If the user needs to know the last element inserted into the stack, then the user can
return the Top element of the stack.
 To do this, first check for Empty Stack.
 If the stack is empty, then there is no element in the stack.
 Otherwise, return the element present in the S -> next -> data in the List.

Routine to Return Top Element

int TopElement(Stack S)

if(S->next==NULL)

error(“Stack is empty”);

return 0;

else

return S->next->data;

Header

40 30 20 10 NULL

TOP

CS8391 11 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Implementation of stack using 'Linked List'

/* Dynamic implementation of stack*/

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node * position ;
struct node
{
int data ;
position next ;
};
void create( ) ;
void push( ) ;
void pop( ) ;
void display( ) ;
position s, newnode, temp, top ; /* Global Declarations */
void main() {
/* Main Program */
int op ;
clrscr( ) ;
do {
printf( "\n ### Linked List Implementation of STACK Operations ### \n\n" ) ;
printf( "\n Press 1-create\n 2-Push\n 3-Pop\n 4-Display\n5-Exit\n" ) ;
printf( "\n Your option ? " ) ;
scanf( " % d ", & op) ;
switch (op) {
case 1:
create( ) ;
break ;
case 2:
push();
break;
case 3:
pop();
break;

case 4:
display();
break;
case 5:
exit(0);

}
}while(op<5);

CS8391 12 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

getch();
}
void create()
{
int n,i;
s=NULL;
printf("Enter the no of nodes to be created\n");
scanf("%d",&n);
newnode=(struct node*)malloc(sizeof(struct node));
printf("Enter the data\t");
scanf("%d",&newnode->data);
newnode->next=NULL;
top=newnode;
s=newnode;
for(i=2;i<=n;i++)
{
newnode=(struct node*)malloc(sizeof(struct node));
printf("Enter the data\t");
scanf("%d",&newnode->data);
newnode->next=top;
s=newnode;
top=newnode;
} }
void display()
{
top=s;
while(top!=NULL)
{
printf("%d->",top->data);
top=top->next;
}
printf("NULL\n");
}
void push()
{ top=s;
newnode=(struct node*)malloc(sizeof(struct node));
printf("Enter the data\t");
scanf("%d",&newnode->data);
newnode->next=top;
top=newnode;
s=newnode;
display();
}
void pop()
{
top=s;

CS8391 13 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

if(top==NULL)
printf("Empty stack\n\n");
else
{
temp=top;
printf("Deleted element is \t %d\n\n",top->data);
s=top->next;
free(temp);
display();
} }

Output
### Linked List Implementation of STACK Operations ###
Press 1-create
2-Push
3-Pop
4-Display
5-Exit
Your option ? 1
Enter the no of nodes to be created5
Enter the data 10
Enter the data20
Enter the data30
Enter the data40
Enter the data50
### Linked List Implementation of STACK Operations ###
Press 1-create
2-Push
3-Pop
4-Display
5-Exit
Your option ? 4
50->40->30->20->10->NULL
### Linked List Implementation of STACK Operations ###
Press 1-create
2-Push
3-Pop
4-Display
5-Exit
Your option ?2
Enter the data60
Your option ? 4
60->50->40->30->20->10->NULL
Your option ?2
Enter the data70
Your option ? 4

CS8391 14 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

70->60->50->40->30->20->10->NULL
Your option ?3
Deleted element is70
Your option ? 4
50->40->30->20->10->NULL

Applications of Stack

The following are some of the applications of stack:

1. Evaluating the arithmetic expressions

o Conversion of Infix to Postfix Expression
o Evaluating the Postfix Expression
2. Balancing the Symbols
3. Function Call
4. Tower of Hanoi
5. 8 Queen Problem
Evaluating the Arithmetic Expression
There are 3 types of Expressions
 Infix Expression
 Postfix Expression
 Prefix Expression

INFIX:

The arithmetic operator appears between the two operands to which it is being
applied.

POSTFIX:

The arithmetic operator appears directly after the two operands to which it applies.
Also called reverse polish notation.

CS8391 15 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

PREFIX:
The arithmetic operator is placed before the two operands to which it applies. Also
called polish notation.

Evaluating Arithmetic Expressions

1. Convert the given infix expression to Postfix expression

2. Evaluate the postfix expression using stack.

Algorithm to convert Infix Expression to Postfix Expression:

Read the infix expression one character at a time until it encounters the delimiter “#”

Step 1: If the character is an operand, place it on the output.

Step 2: If the character is an operator, push it onto the stack. If the stack operator has a higher or
equal priority than input operator then pop that operator from the stack and place it onto the
output.

Step 3:If the character is left parenthesis, push it onto the stack

Step 4:If the character is a right parenthesis, pop all the operators from the stack till it encounters
left parenthesis, discard both the parenthesis in the output.

CS8391 16 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

E.g. Consider the following Infix expression: - A*B+(C-D/E)#

Read char Stack Output

A A

*
A

B
+ AB
*

+ AB*

( AB*
(
+

CS8391 17 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Read char Stack Output

C AB*C
(
+

- AB*C
-
(
+

-
D AB*CD
(
+

/ / AB*CD
-
(
+

E / AB*CDE
-
(
+

AB*CDE/-
) /
-
(
+

CS8391 18 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Read char Stack Output

AB*CDE/-+

Output: Postfix expression:- AB*CDE/-+

Evaluating the Postfix Expression

Algorithm to evaluate the obtained Postfix Expression

Read the postfix expression one character at a time until it encounters the delimiter „#‟

Step 1: If the character is an operand, push its associated value onto the stack.

Step 2: If the character is an operator, POP two values from the stack, apply the operator to
them and push the result onto the stack.

E.g consider the obtained Postfix expression:- AB*CDE/-+

Operand Value
A 2
B 3
C 4
D 4
E 2

Char Read Stack

A 2

B 3
2

CS8391 19 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Char Read Stack

* 6

4
C
6

4
D 4
6

2
4
E 4
6

2
/ 4
6

2
- 6

+ 8
OUTPUT = 8

Example 2: Infix expression:- (a+b)*c/d+e/f#

Read char Stack Output

(
(

a a
(

CS8391 20 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

+ a
+
(

b ab
+
(

) ab+

* ab+

c ab+c

/ ab+c*

d ab+c*d

ab+c*d/
+

CS8391 21 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

e ab+c*d/e

/ ab+c*d/e
/
+

f ab+c*d/ef
/
+

# ab+c*d/ef/+

Postfix expression:- ab+c*d/ef/+

Evaluating the Postfix Expression

Operand Value
a 1
b 2
c 4
d 2
e 6
f 3

CS8391 22 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Char Read Stack

a 1

2
b
1

+ 3

4
c
3

* 12

2
d
12

/ 6

6
e
6

3
f 6
6

2
/
6

+ 8

Output = 8
CS8391 23 DATA STRUCTURES
PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Infix to Postfix Conversion Output

#define SIZE 50 /* Size of Stack */
#include <ctype.h>
char s[SIZE];
int top=-1; /* Global declarations */

void push(char elem)

{
s[++top]=elem;
} Read the Infix Expression ?

char pop()
{
return(s[top--]);
} (a+b)-(c-d)

int pr(char elem)

{ /* Function for precedence */
switch(elem)
{ Given Infix Expn: (a+b)*(c-d)
case '#': return 0;
case '(': return 1; Postfix Expn: ab+cd-*
case '+':
case '-': return 2;
case '*':
case '/': return 3;
}
return 0;
}

Void main()
{ /* Main Program */
char infx[50],pofx[50],ch,elem;
int i=0,k=0;
printf("\nRead the Infix Expression ? ");
scanf("%s",infx);
push('#');
while( (ch=infx[i++]) != '\0')
{
if( ch == '(') push(ch);
else
if(isalnum(ch)) pofx[k++]=ch;
else
if( ch == ')')
{
while( s[top] != '(')

CS8391 24 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

pofx[k++]=pop();
elem=pop(); /* Remove */
}
else
{ /* Operator */
while( pr(s[top]) >= pr(ch) )
pofx[k++]=pop();
push(ch);
}
}
while( s[top] != '#') /* Pop from stack
till empty
pofx[k++]=pop();
pofx[k]='\0'; /* Make pofx as valid
string */
printf("\n\nGiven Infix Expn: %s Postfix
Expn: %s\n",infx,pofx);
}

Towers of Hanoi

Towers of Hanoi can be easily implemented using recursion. Objective of the problem is
moving a collection of N disks of decreasing size from one pillar to another pillar. The
movement of the disk is restricted by the following rules.

Rule 1 : Only one disk could be moved at a time.

Rule 2 : No larger disk could ever reside on a pillar on top of a smaller disk.

Rule 3 : A 3rd pillar could be used as an intermediate to store one or more disks, while they

were being moved from source to destination.

Tower 1 Tower 2 Tower 3

A B C

Initial Setup of Tower of Hanoi

CS8391 25 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Recursive Solution

N - represents the number of disks.

Step 1. If N = 1, move the disk from A to C.

Step 2. If N = 2, move the 1st disk from A to B. Then move the 2nd disk from A to C, The move
the 1st disk from B to C.

Step 3. If N = 3, Repeat the step (2) to more the first 2 disks from A to B using C as
intermediate. Then the 3rd disk is moved from A to C. Then repeat the step (2) to move 2 disks
from B to C using A as intermediate.

In general, to move N disks. Apply the recursive technique to move N - 1 disks from A to B
using C as an intermediate. Then move the Nth disk from A to C. Then again apply the recursive
technique to move N - 1 disks from B to C using A as an intermediate.

Recursive Routine for Towers of Hanoi

void hanoi (int n, char s, char d, char i)

{
/* n no. of disks, s source, d destination i intermediate */
if (n = = 1)
{
print (s, d);
return;
}
else
{
hanoi (n - 1, s, i, d);
print (s, d)
hanoi (n-1, i, d, s);
return;
}
}

CS8391 26 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Source Pillar Intermediate Pillar Destination Pillar

Tower 1 Tower 2 Tower 3

1. Move Tower1 to Tower3

Tower 1 Tower 2 Tower 3

2. Move Tower1 to Tower2

Tower 1 Tower 2 Tower 3

3. Move Tower 3 to Tower 2

Tower 1 Tower 2 Tower 3

4. Move Tower 1 to Tower 3

Tower 1 Tower 2 Tower 3

CS8391 27 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

5. Move Tower 2 to Tower 1

Tower 1 Tower 2 Tower 3

6. Move Tower 2 to Tower 3

Tower 1 Tower 2 Tower 3

7. Move Tower 1 to Tower 3

Tower 1 Tower 2 Tower 3

Since disks are moved from each tower in a LIFO manner, each tower may be considered
as a Stack. Least Number of moves required solving the problem according to our algorithm is
given by,

O(N)=O(N-1)+1+O(N-1) =2N-1

Function Calls

When a call is made to a new function all the variables local to the calling routine need to
be saved, otherwise the new function will overwrite the calling routine variables. Similarly the
current location address in the routine must be saved so that the new function knows where to go
after it is completed.

Main() Balance() Push()

Call
balance()
Call push()

CS8391 28 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Recursive Function to Find Factorial

int fact(int n)
{
int S;
if(n==1)
return(1);
else
S = n * fact( n – 1 );
return(S)
}

Balancing the Symbols

 Compilers check the programs for errors, a lack of one symbol will cause an error.
 A Program that checks whether everything is balanced.
 Every right parenthesis should have its left parenthesis.
 Check for balancing the parenthesis brackets braces and ignore any other character.

Algorithm for balancing the symbols

Read one character at a time until it encounters the delimiter `#'.
Step 1 : - If the character is an opening symbol, push it onto the stack.
Step 2 : - If the character is a closing symbol, and if the stack is empty report an error as
missing opening symbol.
Step 3 : - If it is a closing symbol and if it has corresponding opening symbol in the stack, POP
it from the stack. Otherwise, report an error as mismatched symbols.
Step 4 : - At the end of file, if the stack is not empty, report an error as Missing closing symbol.
Otherwise, report as balanced symbols.

CS8391 29 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Example for Balanced symbols:

E.g. Let us consider the expression ((B*B)-{4*A*C}/[2*A]) #

((B*B)-{4*A*C}/[2*A]) #

Read Character Stack

( (
(

)
(

{ {
(

}
(

CS8391 30 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

[ [
(

]
(

Empty stack, hence the symbols the balanced in the given expression.

CS8391 31 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Example for unbalanced symbols:

QUEUES:

CS8391 32 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

 Queue is a Linear Data Structure that follows First in First out (FIFO) principle.
 Insertion of element is done at one end of the Queue called “Rear “end of the Queue.
 Deletion of element is done at other end of the Queue called “Front “end of the Queue.
 Example: - Waiting line in the ticket counter.

Front End
RearEnd
QUEUE Q
Deletion
Insertion

Queue Model

Front Pointer:-

It always points to the first element inserted in the Queue.

Rear Pointer:-

It always points to the last element inserted in the Queue.

For Empty Queue:-

Front (F) = - 1

Rear (R) = - 1

Operations on Queue

Fundamental operations performed on the queue are

1. EnQueue
2. DeQueue

(i) EnQueue operation:-

CS8391 33 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

 It is the process of inserting a new element at the rear end of the Queue.
 For every EnQueue operation
o Check for Full Queue
o If the Queue is full, Insertion is not possible.
o Otherwise, increment the rear end by 1 and then insert the element in the rear end
of the Queue.

(ii) DeQueue Operation:-

 It is the process of deleting the element from the front end of the queue.
 For every DeQueue operation
o Check for Empty queue
o If the Queue is Empty, Deletion is not possible.
o Otherwise, delete the first element inserted into the queue and then increment the
front by 1.

Exceptional Conditions of Queue

 Queue Overflow
 Queue Underflow

(i) Queue Overflow:

 An Attempt to insert an element X at the Rear end of the Queue when the
Queue is full is said to be Queue overflow.
 For every Enqueue operation, we need to check this condition.
(ii) Queue Underflow:
 An Attempt to delete an element from the Front end of the Queue when the
Queue is empty is said to be Queue underflow.
 For every DeQueue operation, we need to check this condition.

Implementation of Queue

CS8391 34 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Queue can be implemented in two ways.

1. Implementation using Array (Static Queue)

2. Implementation using Linked List (Dynamic Queue)

Array Declaration of Queue:

#define ArraySize 5
int Q [ ArraySize];
or
int Q [ 5 ];

Initial Configuration of Queue:

(i) Queue Empty Operation:

 Initially Queue is Empty.
 With Empty Queue, Front ( F ) and Rear ( R ) points to – 1.
 It is necessary to check for Empty Queue before deleting (DeQueue) an element from the
Queue (Q).

Routine to check for Empty Queue

CS8391 35 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

int IsEmpty ( Queue Q )

if( ( Front = = - 1) && ( Rear = = - 1 ) )

return ( 1 );

(ii) Queue Full Operation

 As we keep inserting the new elements at the Rear end of the Queue, the Queue becomes
full.
 When the Queue is Full, Rear reaches its maximum Arraysize.
 For every Enqueue Operation, we need to check for full Queue condition.

Routine to check for Full Queue

int IsFull( Queue Q )

if ( Rear = = ArraySize - 1 )

return ( 1 );

(iii) Enqueue Operation

 It is the process of inserting a new element at the Rear end of the Queue.
 It takes two parameters, Enqueue(X, Q). The elements X to be inserted at the Rear end of
the Queue Q.
 Before inserting a new Element into the Queue, check for Full Queue.
 If the Queue is already Full, Insertion is not possible.

CS8391 36 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

 Otherwise, Increment the Rear pointer by 1 and then insert the element X at the Rear end
of the Queue.
 If the Queue is Empty, Increment both Front and Rear pointer by 1 and then insert the
element X at the Rear end of the Queue.

Routine to Insert an Element in a Queue

void EnQueue (int X , Queue Q)

{
if ( Rear = = Arraysize - 1)
print (" Full Queue !!!!. Insertion not
possible");
else if (Rear = = - 1)
{
Front = Front + 1;
Rear = Rear + 1;
Q [Rear] = X;
}
else
{
Rear = Rear + 1;
Q [Rear] = X;
}
}

(iv) DeQueue Operation

 It is the process of deleting a element from the Front end of the Queue.
 It takes one parameter, DeQueue (Q). Always front element in the Queue will be deleted.
 Before deleting an Element from the Queue, check for Empty Queue.
 If the Queue is empty, deletion is not possible.

CS8391 37 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

 If the Queue has only one element, then delete the element and represent the empty queue
by updating Front = - 1 and Rear = - 1.
 If the Queue has many Elements, then delete the element in the Front and move the Front
pointer to next element in the queue by incrementing Front pointer by 1.

ROUTINE FOR DEQUEUE

void DeQueue ( Queue Q )

{
if ( Front = = - 1)
print (" Empty Queue !. Deletion not possible " );
else if( Front = = Rear )
{
X = Q [ Front ];
Front = - 1;
Rear = - 1;
}
else
{
X = Q [ Front ];
Front = Front + 1 ;
}

Array implementation of Queue

#include<stdio.h>
#include<conio.h>
#define SIZE 5
int front = - 1;
int rear = - 1;
int q[SIZE];

CS8391 38 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

void insert( );
void del( );
void display( );
void main( )
{
int choice;
clrscr( );
do
{
printf("\t Menu");
printf("\n 1. Insert");
printf("\n 2. Delete");
printf("\n 3. Display ");
printf("\n 4. Exit");

printf("\n Enter Your Choice:");

scanf("%d", &choice);
switch(choice)
{
case 1:
insert( );
display( );
break;
case 2:
del( );
display( );
break;
case 3:
display( );
break;
case 4:
printf("End of Program....!!!!");
exit(0);
}
}while(choice != 4);}
void insert( )
{
int no;
printf("\n Enter No.:");
scanf("%d", &no);

if(rear < SIZE - 1)

{
q[++rear]=no;
if(front = = - 1)
front=0;// front=front+1;

CS8391 39 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

}
else
{
printf("\n Queue overflow");
}}

void del( )
{
if(front = = - 1)
{
printf("\n Queue Underflow");
return;
}
else
{
printf("\n Deleted Item:-->%d\n", q[front]);
}
if(front = = rear)
{ output

Front = - 1;
Rear = - 1;
}
else
{
Front = front + 1;
}}

void display( )
{
int i;
if( front = = - 1)
{
printf("\nQueue is empty....");
return;
}
for(i = front; i<=rear; i++)
printf("\t%d",q[i]);}

CS8391 40 DATA STRUCTURES

 PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Linked List Implementation of Queue

 Queue is implemented using SLL (Singly Linked List ) node.

 Enqueue operation is performed at the end of the Linked list and DeQueue
operation is performed at the front of the Linked list.
 With Linked List implementation, for Empty queue
Front = NULL & Rear = NULL
Linked List representation of Queue with 4 elements

Header

10 20 30 40 NULL

Front Rear

Declaration for Linked List Implementation of Queue ADT

struct node;
typedef struct node * Queue;
typedef struct node * position;
int IsEmpty (Queue Q);
Queue CreateQueue (void);
void MakeEmpty (Queue Q);
void Enqueue (int X, Queue Q);
void Dequeue (Queue Q);
struct node
{
int data ;
position next;
}* Front = NULL, *Rear = NULL;

CS8391 41 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

(i) Queue Empty Operation:

 Initially Queue is Empty.
 With Linked List implementation, Empty Queue is represented as S -> next = NULL.
 It is necessary to check for Empty Queue before deleting the front element in the Queue.

ROUTINE TO CHECK WHETHER THE QUEUE IS EMPTY

int IsEmpty (Queue Q

{ Q

if ( Q Next = = NULL) Header NULL

return (1);
Empty Queue
}

(ii) EnQueue Operation

 It is the process of inserting a new element at the Rear end of the Queue.
 It takes two parameters, EnQueue ( int X , Queue Q ). The elements X to be inserted into
the Queue Q.
 Using malloc ( ) function allocate memory for the newnode to be inserted into the Queue.
 If the Queue is Empty, the newnode to be inserted will become first and last node in the
list. Hence Front and Rear points to the newnode.
 Otherwise insert the newnode in the Rear -> next and update the Rear pointer.

CS8391 42 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Routine to EnQueue an Element in Queue

void EnQueue ( int X, Queue Q )

{
struct node *newnode; Q
newnode = malloc (sizeof (struct node));
if (Rear = = NULL) Header NULL
{
newnode data = X;
newnode next = NULL; Empty Queue
Q -> next = newnode;
Front = newnode; Before Insertion
Rear = newnode;
}
else
{ Q
newnode data = X;
newnode next = NULL; Header
Rear next = newnode;
Rear = newnode;
} 10 NULL
}

(iii) DeQueue Operation Front Rear

 It is the process of deleting the front element from the Queue. After Insertion
 It takes one parameter, Dequeue ( Queue Q ). Always element in the front (i.e)
element pointed by Q -> next is deleted always.
 Element to be deleted is made “temp”.
 If the Queue is Empty, then deletion is not possible.
 If the Queue has only one element, then the element is deleted and Front and Rear
pointer is made NULL to represent Empty Queue.
 Otherwise, Front element is deleted and the Front pointer is made to point to next
node in the list.
 The free ( ) function informs the compiler that the address that temp is pointing to,
is unchanged but the data present in that address is now undefined.

CS8391 43 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Header

20 30 40 NULL

Front Rear

Routine to DeQueue an Element from the Queue

void DeQueue ( Queue Q )

{
struct node *temp;
if ( Front = = NULL )
Error (“Empty Queue!!! Deletion not possible.” );
else if (Front = = Rear)
{
temp = Front;
Q -> next = NULL;
Front = NULL;
Rear = NULL;
free ( temp );
}
else
{
temp = Front;
Q -> next = temp -> next;
Front = Front Next;
free (temp);
}

CS8391 44 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Linked list implementation of Queue

#include<stdio.h>
#include<conio.h>
void enqueue();
void dequeue();
void display();
typedef struct node *position;
position front=NULL,rear=NULL,newnode,temp,p;

struct node
{
int data;
position next;
};
void main()
{
int choice;
clrscr();
do
{
printf("1.Enqueue\n2.Dequeue\n3.display\n4.exit\n");
printf("Enter your choice\n\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(0);
}
}
while(choice<5);
}

void enqueue()
{
newnode=(struct node*)malloc(sizeof(struct node));
printf("\n Enter the data to be enqueued\n");
scanf("%d",&newnode->data);
newnode->next=NULL;
if(rear==NULL)
front=rear=newnode;
else {

CS8391 45 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

rear->next=newnode;
rear=newnode;
}
display();
}
void dequeue()
{
if(front==NULL)
printf("\nEmpty queue!!!!! Deletion not possible\n");
else if(front==rear)
{
printf("\nFront element %d is deleted from queue!!!! now queue is
empty!!!! no more deletion possible!!!!\n",front->data);
front=rear=NULL;
}
else
{
temp=front;
front=front->next;
printf("\nFront element %d is deleted from queue!!!!\n",temp->data);
free(temp);
}
display();
}
void display()
{
p=front;
while(p!=NULL)
{
printf("%d -> ",p->data);
p=p->next;
}
printf("Null\n");
}
Output

CS8391 46 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Applications of Queue

1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life, Call Center phone systems will use Queues, to hold people calling them in an
order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order
as they arrive, First come first served.
4. Batch processing in operating system.
5. Job scheduling Algorithms like Round Robin Algorithm uses Queue.

Drawbacks of Queue (Linear Queue)

 With the array implementation of Queue, the element can be deleted logically only by
moving Front = Front + 1.
 Here the Queue space is not utilized fully.

To overcome the drawback of this linear Queue, we use Circular Queue.

CIRCULAR QUEUE

In Circular Queue, the insertion of a new element is performed at the very first location of the
queue if the last location of the queue is full, in which the first element comes just after the last
element.

 A circular queue is an abstract data type that contains a collection of data which allows
addition of data at the end of the queue and removal of data at the beginning of the
queue.
 Circular queues have a fixed size.
 Circular queue follows FIFO principle.
 Queue items are added at the rear end and the items are deleted at front end of the circular
queue
 Here the Queue space is utilized fully by inserting the element at the Front end if the rear
end is full.

CS8391 47 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Operations on Circular Queue

Fundamental operations performed on the Circular Queue are

 Circular Queue Enqueue

 Circular Queue Dequeue

Formula to be used in Circular Queue

For Enqueue Rear = ( Rear + 1) % ArraySize

For Dequeue Front = ( Front + 1) % ArraySize

(i) Circular Queue Enqueue Operation

 It is same as Linear Queue EnQueue Operation (i.e) Inserting the element at the Rear end.
 First check for full Queue.
 If the circular queue is full, then insertion is not possible.
 Otherwise check for the rear end.
 If the Rear end is full, the elements start getting inserted from the Front end.

CS8391 48 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Routine to Enqueue an element in circular queue

void Enqueue ( int X, CircularQueue CQ )

{
if( Front = = ( Rear + 1 ) % ArraySize)
Error( “Queue is full!!Insertion not possible” );
else if( Rear = = -1 )
{
Front = Front + 1;
Rear = Rear + 1;
CQ[ Rear ] = X;
}
else
{
Rear = ( Rear + 1 ) % Arraysize;
CQ[ Rear ] = X;
}
}

Circular Queue DeQueue Operation

 It is same as Linear Queue DeQueue operation (i.e) deleting the front element.
 First check for Empty Queue.
 If the Circular Queue is empty, then deletion is not possible.

 If the Circular Queue has only one element, then the element is deleted and Front and Rear
pointer is initialized to - 1 to represent Empty Queue.
 Otherwise, Front element is deleted and the Front pointer is made to point to next element in the
Circular Queue.

CS8391 49 DATA STRUCTURES

 PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

F, R
F= -1,R= --1

Routine To DeQueue An Element In Circular Queue

void DeQueue (CircularQueue CQ)

{
if(Front== - 1)
Empty(“Empty Queue!”);
else if(Front==rear)
{
X=CQ[Front];
Front=-1;
Rear=-1;
}
else
{
X=CQ[Front];
Front=(Front+1)%Arraysize;
}}

Implementation of Circular Queue

#include<stdio.h>
#include<conio.h>
#define max 3
void insert(); void delet(); void display();
int q[10],front=0,rear=-1;
void main()
{ int ch;
clrscr();
printf("\nCircular Queue operations\n"); printf("1.insert\n2.delete\n3.display\n4.exit\n");
while(1)
{
printf("Enter your choice:");

CS8391 50 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

scanf("%d",&ch);
switch(ch)
{
case 1:
insert(); break;
case 2:
delet(); break;
case 3:
display(); break;
case 4:
exit();
default:
printf("Invalid option\n");
}}}

void insert()
{
int x;
if((front==0&&rear==max-1)||(front>0&&rear==front-1))
printf("Queue is overflow\n");
else
{
printf("Enter element to be insert:");
scanf("%d",&x);
if(rear==max-1&&front>0)
{
rear=0;
q[rear]=x;
}
else
{
if((front==0&&rear==-1)||(rear!=front-1))
q[++rear]=x;
} }}
void delet()
{
int a;
if((front==0)&&(rear==-1))
printf("Queue is underflow\n");
if(front==rear)
{
a=q[front];
rear=-1;
front=0;
}
else if(front==max-1)

CS8391 51 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

{
a=q[front];
front=0;
}
else
a=q[front++];
printf("Deleted element is:%d\n",a);
}
void display()
{
int i,j;
if(front==0&&rear==-1)
printf("Queue is underflow\n");
if(front>rear) {
for(i=0;i<=rear;i++)
printf("\t%d",q[i]);
for(j=front;j<=max-1;j++)
printf("\t%d",q[j]);
printf("\nrear is at %d\n",q[rear]);
printf("\nfront is at %d\n",q[front]); }
else
{
for(i=front;i<=rear;i++)
printf("\t%d",q[i]);
printf("\nrear is at %d\n",q[rear]);
printf("\nfront is at %d\n",q[front]);
}
printf("\n");
}

OUTPUT

CS8391 52 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

DOUBLE-ENDED QUEUE (DEQUE)

In DEQUE, insertion and deletion operations are performed at both ends of the Queue.

Exceptional Condition of DEQUE

(i) Input Restricted DEQUE

Here insertion is allowed at one end and deletion is allowed at both ends.

Insertion
Deletion
Deletion

Front Rear

(ii) Output Restricted DEQUE

Here insertion is allowed at both ends and deletion is allowed at one end.

Insertion
Insertion
Deletion

Front Rear

CS8391 53 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Operations on DEQUE

Four cases for inserting and deleting the elements in DEQUE are

 Insertion At Rear End [ same as Linear Queue ]

 Insertion At Front End
 Deletion At Front End [ same as Linear Queue ]
 Deletion At Rear End

Case 1: Routine to insert an element at Rear end

void Insert_Rear (int X, DEQUE DQ)

{
if( Rear = = Arraysize - 1)
Error(“Full Queue!!!! Insertion not possible”);
else if( Rear = = -1)
{
Front = Front + 1;
Rear = Rear + 1;
DQ[ Rear ] = X;
}
else
{
Rear = Rear + 1;
DQ[ Rear ] = X;
}

CS8391 54 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

CS8391 55 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Case 2: Routine to insert an element at Front end

void Insert_Front ( int X, DEQUE DQ )

{
if( Front = = 0 )
Error(“Element present in Front!!!!! Insertion not possible”);
else if(Front = = -1)
{
Front = Front + 1;
Rear = Rear + 1;
DQ[Front] = X;
}
else
{
Front = Front - 1;
DQ[Front] = X;
}
}

CS8391 56 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

CS8391 57 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Case 3: Routine to delete an element from Front end

void Delete_Front(DEQUE DQ)

{
if(Front = = - 1)
Error(“Empty queue!!!! Deletion not possible”);
else if( Front = = Rear )
{
X = DQ[ Front];
Front = - 1;
Rear = - 1;
}
else
{
X = DQ [ Front ];
Front = Front + 1;
}
}

CS8391 58 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

CS8391 59 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

Case 4: Routine to delete an element from Rear end

void Delete_Rear(DEQUE DQ)

{
if( Rear = = - 1)
Error(“Empty queue!!!! Deletion not possible”);
else if( Front = = Rear )
{
X = DQ[ Rear ];
Front = - 1;
Rear = - 1;
}
else
{
X = DQ[ Rear ];
Rear = Rear - 1;
}

CS8391 60 DATA STRUCTURES

PANIMALAR INSTITUTE OF TECHNOLOGY II YEAR/III SEM B.E-CSE

CS8391 61 DATA STRUCTURES