Module 2 M23BCS304

Module 2:
STACKS:
1. Definition
A Stack is a linear data structure that follows a particular order in which the operations are
performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). LIFO implies
that the element that is inserted last, comes out first and FILO implies that the element that is
inserted first, comes out last.

The stack abstract data type stack

• This is an ordered-list in which insertions(called push) and deletions(called pop) are made
atone end called the top
• Since last element inserted into a stack is first element removed, a stack is also known as
aLIFO list(Last In First Out).
When an element is inserted in a stack, the concept is called push, and when an element is
removed from the stack, the concept is called pop.
Trying to pop out an empty stack is called underflow and trying to push an element in a full
stack is called overflow.

As shown in above figure, the elements are added in the stack in the order A, B, C, D, E, then E

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 1

Module 2 M23BCS304

is the first element that is deleted from the stack and the last element is deleted from stack is
A. Figure illustrates this sequence of operations.
Since the last element inserted into a stack is the first element removed, a stack is also known
as a Last-In-First-Out (LIFO) list.
SYSTEM STACK

A stack used by a program at run-time to process function-calls is called system-stack.

• When functions are invoked, programs
→ create a stack-frame (or activation-record) &
→ place the stack-frame on top of system-stack
• Initially, stack-frame for invoked-function contains only
→ pointer to previous stack-frame &
→ return-address
• The previous stack-frame pointer points to the stack-frame of the invoking-function
while return-address contains the location of the statement to be executed after
the function terminates.
• If one function invokes another function, local variables and parameters of the
invoking- function are added to its stack-frame.
• A new stack-frame is then
→ created for the invoked-function &
→ placed on top of the system-stack
• When this function terminates, its stack-frame is removed (and processing of the
invoking-function, which is again on top of the stack, continues).
• Frame-pointer(fp) is a pointer to the current stack-frame.

2. Stack Operations

Standard Stack Operations

The following are some common operations implemented on the stack:

• push(): When we insert an element in a stack then the operation is known as a push. If the stack

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 2

Module 2 M23BCS304

is full then the overflow condition occurs.

• pop(): When we delete an element from the stack, the operation is known as a pop. If the stack
is empty means that no element exists in the stack, this state is known as an underflow state.
• isEmpty(): It determines whether the stack is empty or not.
• isFull(): It determines whether the stack is full or not.'

a) PUSH operation
The steps involved in the PUSH operation are given below:
o Before inserting an element in a stack, we check whether the stack is full.
o If we try to insert the element in a stack, and the stack is full, then
the overflow condition occurs.
o When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
o When the new element is pushed in a stack, first, the value of the top gets incremented,
i.e., top=top+1, and the element will be placed at the new position of the top.
o The elements will be inserted until we reach the max size of the stack.

b) POP operation
The steps involved in the POP operation are given below:

o Before deleting the element from the stack, we check whether the stack is empty.
o If we try to delete the element from the empty stack, then the underflow condition
occurs.
o If the stack is not empty, we first access the element which is pointed by the top

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 3

Module 2 M23BCS304

o Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

3. Array representation of stacks

• Stacks may be represented in the computer in various ways such as

one-waylinked list (Singly linked list) or linear array.
• Stacks are maintained by the two variables such as TOP and MAX_STACK_SIZE.
• TOP which contains the location of the top element in the stack. If TOP=
-1,then it indicates stack is empty.
• MAX_STACK_SIZE which gives maximum number of elements that can
bestored in stack.

Stack can represented using linear array as shown below

Stack ADT

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 4

Module 2 M23BCS304

• The following operations make a stack an ADT. For simplicity, assume the
data is an integertype.

• Main stack operations

– Push (int data): Inserts data onto stack.
– int Pop(): Removes and returns the last inserted element from the stack.
• Auxiliary stack operations
– int Top(): Returns the last inserted element without removing it.
– int Size(): Returns the number of elements stored in the stack.
– int IsEmptyStack(): Indicates whether any elements are stored in the stack or not.
– int IsFullStack(): Indicates whether the stack is full or not.
• The easiest way to implement this ADT is by using a one-dimensional array,
say, stack [MAX-STACK-SIZE], where MAX STACK SIZE is the maximum number of
entries.
• The first, or bottom, element of the stack is stored in stack[0], the second in

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 5

Module 2 M23BCS304

stack[1] andthe ith in stack [i-1].

• Associated with the array is a variable, top, which points to the top element in
the [Link], top is set to -1 to denote an empty stack.
• we have specified that element is a structure that consists of only a key field.

I. Create stack:

The element which is used to insert or delete is specified as a structure that

consists ofonly a key field.
1. Boolean IsEmpty(Stack)::= top < 0;
2. Boolean IsFull(Stack)::= top >= MAX_STACK_SIZE-1;
The IsEmpty and IsFull operations are simple, and is implemented directly
in the program push and pop functions. Each of these functions assumes
that the variablesstack and top are global.

II. Add an item to a stack

• Function push() checks to see if the stack is full. If it is, it calls stackFull, which
prints anerror message and terminates execution.
• When the stack is not full, we increment top and assign item to stack[top].

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 6

Module 2 M23BCS304

III. Delete an item in a stack

For deletion, the stack-empty function should print an error message and return an
item oftype element with a key field that contains an error code.

4. Stack using dynamic arrays

• Shortcoming of static stack implementation: is the need to know at compile-

time, a goodbound(MAX_STACK_SIZE) on how large the stack will become.
• This shortcoming can be overcome by
→ using a dynamically allocated array for the elements &
→ then increasing the size of the array as needed
• Initially, capacity=1 where capacity=maximum no. of stack-elements that may be
stored inarray.
• The CreateS() function can be implemented as follows
Stack CreateS(max-stack-size') ::=
#define MAX—STACK—SIZE 100 /*maximum stack size */
typedef struct
{
int key;
/* other fields */
} element;
element stack[MAX—STACK—SIZE];
int top - -1;
Boolean IsEmpty(Stack) ::= top <0;
Boolean IsFulI(Stack) ::= top >= MAX-STACK-SIZE-1;
• Once the stack is full, realloc() function is used to increase the size of array.
• In array-doubling, we double array-capacity whenever it becomes necessary to
increase thecapacity of an array.

ANALYSIS

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 7

Module 2 M23BCS304

• In worst case, the realloc function needs to

→ allocate 2*capacity*sizeof(*stack) bytes of memory and
→ copy capacity*sizeof(*stack) bytes of memory from the old array into the new
one.
• The total time spent over all array doublings = O(2k ) where capacity=2k
• Since the total number of pushes is more than 2k-1 , the total time spend in
array doublingis O(n) where n=total number of pushes.

5. Stack applications:
Polish notation
Expressions: It is sequence of operators and operands that reduces to a single
value afterevaluation is called an expression.
X=a/b–c+d*e– a*c
In above expression contains operators (+, –, /, *) operands (a, b, c, d, e).
Expression can be represented in in different format such as
• Prefix Expression or Polish notation
• Infix Expression
• Postfix Expression or Reverse Polish notation
• Infix Expression: In this expression, the binary operator is placed in-
between the operand. The expression can be parenthesized or un-
parenthesized.
Example: A + B
Here, A & B are operands and + is operand
• Prefix or Polish Expression: In this expression, the operator appears before
itsoperand.
Example: + A B
Here, A & B are operands and + is operand
• Postfix or Reverse Polish Expression: In this expression, the operator
appearsafter its operand.
Example: A B +
Here, A & B are operands and + is operand
Precedence of the operators

The first problem with understanding the meaning of expressions and

statements isfinding out the order in which the operations are performed.
Example: assume that a =4, b =c =2, d =e =3 in below
expressionX = a / b – c + d * e – a * c

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 8

Module 2 M23BCS304

((4/2)-2) + (3*3)-(4*2) (4/ (2-2 +3)) *(3-4)*2

=0+9-8 OR = (4/3) * (-1) * 2
=1 = -2.66666
The first answer is picked most because division is carried out before subtraction,
and multiplication before addition. If we wanted the second answer, write
expression differently using parentheses to change the order of evaluation
X= ((a / ( b – c + d ) ) * ( e – a ) * c
In C, there is a precedence hierarchy that determines the order in which operators
areevaluated. Below figure contains the precedence hierarchy for C.

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 9

Module 2 M23BCS304

• The operators are arranged from highest precedence to lowest.

Operators withhighest precedence are evaluated first.
• The associativity column indicates how to evaluate operators with the
same precedence. For example, the multiplicative operators have left-
to-right associativity. This means that the expression a * b / c % d / e
is equivalent to (( ( ( a * b ) / c ) % d ) / e )
• Parentheses are used to override precedence, and expressions are
always evaluatedfrom the innermost parenthesized expression first

6. Infix to postfix conversion

An algorithm to convert infix to a postfix expression as follows:

a. Fully parenthesize the expression.
b. Move all binary operators so that they replace their
corresponding rightparentheses.
c. Delete all parentheses.
Example: Infix expression: a/b -c

+d*e -a*c Fully parenthesized :

((((a/b)-c) + (d*e))-a*c))
:ab/e–de*+ ac*
Example [Parenthesized expression]: Parentheses make the translation
process more difficult because the equivalent postfix expression will be
parenthesis-free. The expression a*(b +c)*d which results abc +*d* in postfix.
Figure shows thetranslation process.

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 10

Module 2 M23BCS304

The analysis of the examples suggests a precedence-based scheme for stacking and
unstacking operators.
• The left parenthesis complicates matters because it behaves like a low-
precedence operator when it is on the stack and a high-precedence one when it
is not. It is placed in the stack whenever it is found in the expression, but it is
unstacked only when its matching right parenthesis is found.
• There are two types of precedence, in-stack precedence (isp) and incoming
precedence (icp).
The declarations that establish the precedence’s are:
/* isp and icp arrays-index is value of precedence lparen rparen, plus,
minus, times,divide, mod, eos */
int isp[] = {0,19,12,12,13,13,13,0};
int icp[] = {20,19,12,12,13,13,13,0};

Example: Consider the infix expression exp = “a+b*c+d” and the infix expression is scanned
using the iterator i, which is initialized as i = 0.

1st Step: Here i = 0 and exp[i] = ‘a’ i.e., an operand. So add this in the postfix expression.
Therefore, postfix = “a”.

Add ‘a’ in the postfix

2nd Step: Here i = 1 and exp[i] = ‘+’ i.e., an operator. Push this into the stack. postfix = “a” and
stack = {+}.

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 11

Module 2 M23BCS304

Push ‘+’ in the stack

3rd Step: Now i = 2 and exp[i] = ‘b’ i.e., an operand. So add this in the postfix expression.
postfix = “ab” and stack = {+}.

Add ‘b’ in the postfix

4th Step: Now i = 3 and exp[i] = ‘*’ i.e., an operator. Push this into the stack. postfix = “ab”
and stack = {+, *}.

Push ‘*’ in the stack

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 12

Module 2 M23BCS304

5th Step: Now i = 4 and exp[i] = ‘c’ i.e., an operand. Add this in the postfix expression. postfix
= “abc” and stack = {+, *}.

Add ‘c’ in the postfix

6th Step: Now i = 5 and exp[i] = ‘+’ i.e., an operator. The topmost element of the stack has
higher precedence. So pop until the stack becomes empty or the top element has less
precedence. ‘*’ is popped and added in postfix. So postfix = “abc*” and stack = {+}.

Pop ‘*’ and add in postfix

Now top element is ‘+‘ that also doesn’t have less precedence. Pop it. postfix = “abc*+”.

Pop ‘+’ and add it in postfix

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 13

Module 2 M23BCS304

Now stack is empty. So push ‘+’ in the stack. stack = {+}.

Push ‘+’ in the stack

7th Step: Now i = 6 and exp[i] = ‘d’ i.e., an operand. Add this in the postfix expression. postfix
= “abc*+d”.

Add ‘d’ in the postfix

Final Step: Now no element is left. So empty the stack and add it in the postfix expression.
postfix = “abc*+d+”.

Pop ‘+’ and add it in postfix

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 14

Module 2 M23BCS304

7. Evaluation of postfix expression

• The evaluation process of postfix expression is simpler than the
evaluation of infix expressions because there are no parentheses to
consider.
• To evaluate an expression, make a single left-to-right scan of it. Place the
operands on a stack until an operator is found. Then remove from the
stack, the correct number of operands for the operator, perform the
operation, and place the result back on the stack and continue this
fashion until the end of the expression. We then remove the answer from
the top of the stack.
Given a postfix expression, the task is to evaluate the postfix expression.

Postfix expression: The expression of the form “a b operator” (ab+) i.e., when a pair of
operands is followed by an operator.
Examples:
Input: str = “2 3 1 * + 9 -“
Output: -4
Explanation: If the expression is converted into an infix expression,
it will be 2 + (3 * 1) – 9 = 5 – 9 = -4.
Input: str = “100 200 + 2 / 5 * 7 +”
Output: 757
Evaluation of Postfix Expression using Stack:
To evaluate a postfix expression we can use a stack.
Iterate the expression from left to right and keep on storing the operands into a stack. Once
an operator is received, pop the two topmost elements and evaluate them and push the result
in the stack again.
Illustration:
Follow the below illustration for a better understanding:
Consider the expression: exp = “2 3 1 * + 9 -“
• Scan 2, it’s a number, So push it into stack. Stack contains ‘2’.

Push 2 into stack

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 15

Module 2 M23BCS304

• Scan 3, again a number, push it to stack, stack now contains ‘2 3’ (from bottom to top)

Push 3 into stack

• Scan 1, again a number, push it to stack, stack now contains ‘2 3 1’

Push 1 into stack

• Scan *, it’s an operator. Pop two operands from stack, apply the * operator on operands.
We get 3*1 which results in 3. We push the result 3 to stack. The stack now becomes ‘2 3’.

Evaluate * operator and push result in stack

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 16

Module 2 M23BCS304

• Scan +, it’s an operator. Pop two operands from stack, apply the + operator on operands.
We get 3 + 2 which results in 5. We push the result 5 to stack. The stack now becomes ‘5’.

Evaluate + operator and push result in stack

• Scan 9, it’s a number. So we push it to the stack. The stack now becomes ‘5 9’.

Push 9 into stack

• Scan -, it’s an operator, pop two operands from stack, apply the – operator on operands,
we get 5 – 9 which results in -4. We push the result -4 to the stack. The stack now becomes
‘-4’.

Evaluate ‘-‘ operator and push result in stack

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 17

Module 2 M23BCS304

• There are no more elements to scan, we return the top element from the stack (which is
the only element left in a stack).
So the result becomes -4.

Follow the steps mentioned below to evaluate postfix expression using stack:
• Create a stack to store operands (or values).
• Scan the given expression from left to right and do the following for every scanned
element.
o If the element is a number, push it into the stack.
o If the element is an operator, pop operands for the operator from the stack.
Evaluate the operator and push the result back to the stack.
• When the expression is ended, the number in the stack is the final answer.
Below is the implementation of the above approach:
// C program to evaluate value of a postfix expression
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Stack type
struct Stack
{
int top;
unsigned capacity;
int* array;
};
// Stack Operations
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack
= (struct Stack*)malloc(sizeof(struct Stack));
if (!stack)
return NULL;
stack->top = -1;
stack->capacity = capacity;
stack->array
= (int*)malloc(stack->capacity * sizeof(int));
if (!stack->array)
return NULL;
return stack;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 18

Module 2 M23BCS304

}
char peek(struct Stack* stack)
{
return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--];
return '$';
}
void push(struct Stack* stack, char op)
{
stack->array[++stack->top] = op;
}
// The main function that returns value
// of a given postfix expression
int evaluatePostfix(char* exp)
{
// Create a stack of capacity equal to expression size
struct Stack* stack = createStack(strlen(exp));
int i;
// See if stack was created successfully
if (!stack)
return -1;
// Scan all characters one by one
for (i = 0; exp[i]; ++i) {
// If the scanned character is an operand
// (number here), push it to the stack.
if (isdigit(exp[i]))
push(stack, exp[i] - '0');
// If the scanned character is an operator,
// pop two elements from stack apply the operator
else
{
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[i])
{
case '+':push(stack, val2 + val1);
break;
case '-': push(stack, val2 - val1);
break;
case '*': push(stack, val2 * val1);

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 19

Module 2 M23BCS304

break;
case '/': push(stack, val2 / val1);
break;
}
}
}
return pop(stack);
}
// Driver code
int main()
{
char exp[] = "231*+9-";

// Function call
printf("postfix evaluation: %d", evaluatePostfix(exp));
return 0;
}
Output
postfix evaluation: -4

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 20

Module 2 M23BCS304

Chapter 2:
1. Queues:
Queue is the data structure that is similar to the queue in the real world. A queue is a data
structure in which whatever comes first will go out first, and it follows the FIFO (First-In-First-
Out) policy. Queue can also be defined as the list or collection in which the insertion is done
from one end known as the rear end or the tail of the queue, whereas the deletion is done
from another end known as the front end or the head of the queue.
The real-world example of a queue is the ticket queue outside a cinema hall, where the person
who enters first in the queue gets the ticket first, and the last person enters in the queue gets
the ticket at last. Similar approach is followed in the queue in data structure.

The representation of the queue is shown in the below image -

A queue is an ordered list in which all insertions take place at one end and all deletions take
place at the opposite end. Given a queue Q = (a0, a1, • • • ,an-1),a0 is the front element, an-1 is
the rear element, and ai+1 is behind ai,0<= i < n-1. The restrictions on a queue imply that if we
insert A, B, C, D, in that order, then A is the first element deleted from the queue. Fig 2
illustrates this sequence of events. Since the first element inserted into a queue is the first
element removed, queues are also known as First-In- First-Out (FIFO) lists.

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 21

Module 2 M23BCS304

Fig 1: Railroad Switching Network

Fig 2: Inserting and Deleting Element in the Queue

2. Array representation of Queue

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.

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 22

Module 2 M23BCS304

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.

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 23

Module 2 M23BCS304

3. Queue Operations

The representation of a queue in sequential locations is more difficult than that of the tack. The
simplest scheme employs a one-dimensional array and two variables, front and rear. Given this
representation, we can define the queue operations in Structure as

Fig: Queue Abstract Data Type.

➢ CreateQueue: It is used to Create a Queue Data Structure

➢ InsertQueue: It is used to insert element to the queue.
➢ Delete Queue: It is used to delete element from the queue.
➢ IsFull: It is used to check weather queue is full or not
➢ IsEmpty: It is used to check weather queue is empty or not

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 24

Module 2 M23BCS304

Types of Queue

There are four different types of queue that are listed as follows -

o Simple Queue or Linear Queue

o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)

4. Linear Queue(Simple Queue/Ordinary Queue):

In Linear Queue, an insertion takes place from one end while the deletion occurs from another
end. The end at which the insertion takes place is known as the rear end, and the end at which
the deletion takes place is known as front end. It strictly follows the FIFO rule.

The major drawback of using a linear Queue is that insertion is done only from the rear end. If
the first three elements are deleted from the Queue, we cannot insert more elements even

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 25

Module 2 M23BCS304

though the space is available in a Linear Queue. In this case, the linear Queue shows the
overflow condition as the rear is pointing to the last element of the Queue.

The various operations performed on queue are:

Insert: An element is inserted at rear end.

Delete: An element is deleted from front end.
Overflow: If queue is full and try to insert an item, overflow condition occurs.
Underflow: If queue isempty and try to delete an item, underflow condition occurs.

Queue Implementation using Arrays:

Before implementing queue operations, we need to initialize the following variables:
#define QUEUESIZE 5 //define symbolic constant Queue size as 5
Int q[QUEUESIZE];
int f=0; // initialize front end as 0
intr=-1;//initializerearendas-1

Isfull(): Before inserting an item into the queue, we need to check whether the queue is full or
not. If rear is the same as QUEESIZE-1, then queue isfull. Isfull() function can be implemented
as:
Int Isfull(int r)
{
return r==QUEUESIZE-1; //returns1, if the queue is full, else returns 0 if the queue is not full.
}

InsertQ(): To insert the item, rear has to be increment by 1 and then item can be
inserted at rear end of queue. Before inserting, we check queue is full or not using Isfull
() function. Hence, InsertQ () function can be implemented as:
void insertQ(int item,int *r,int *q)
{
if(Isfull(*r)
{

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 26

Module 2 M23BCS304

printf(“queueoverflow\n”);
return;
}
q[++(*r)]=item;//rear is incrementing first and then item is inserted at rear
}

Isempty():Whenever the value of front is greater than that of rear, then queue is empty.
Isempty () function can be implemented as:
intIsempty(int f,int r)
{
return f>r;//returns1,if queue is empty, else returns0.
}
deleteQ ();
In a queue, element is always deleted from the front end. Before deleting, check whether
queue is empty. This can be done using Isempty () function. To delete an item,we have to
access the item at front and then increment front value by [Link] deleteQ () can be
implemented as:
void deleteQ(int *q,int *f,int *r)
{
if(Isempty(*f,*r))
{
printf(“Queue Empty\n”);
return;
}
printf(“itemdeletedis%d\n”,q[(*f)++]);
}
Display():
If the queue already has some elements, all those elements are displayed one after the other.
If no elements are present, appropriate error message can be displayed. Hence displayQ ()
function can be implemented as:

void displayQ(int *q,int f,int r)

{
int i;
if(Isempty(*f,*r))
{
printf(“QueueEmpty\n”); return;
}

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 27

Module 2 M23BCS304

for (i=f; i<=r; i++)

printf(“%d\n”,q[i]);
}

C program to implement Linear queue(ordinary queue) operations:

#define QUEUE_SIZE 5 //definesymbolicconstantQueuesizeas5

int q[QUEUE_SIZE];
int Isfull(int r)
{
Return r==QUEUESIZE-1;//returns1,ifthequeueisfull,elsereturns0ifthe
thequeue isnotfull.
}
void insertQ(int item,int *r,int *q)
{
if(Isfull(*r)
{
printf(“queueoverflow\n”);
return;
}
q[++(*r)]=item;//rearisincrementingfirstandthenitemisinsertedatrear
}
Int Isempty(int f,int r)
{
return f>r;//returns1,if the queue is empty ,else returns 0.
}
Void deleteQ(int *q,int *f,int *r)
{
if(Isempty(*f,*r))
{
printf(“QueueEmpty\n”);
return;
}
printf(“item deleted is%d\n”,q[(*f)++]);
}
void displayQ(int *q,int f,int r)
{
int i;
if(Isempty(*f,*r))

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 28

Module 2 M23BCS304

{
printf(“QueueEmpty\n”); return;
}
for (i=f; i<=r; i++)
printf(“%d\n”,q[i]);
}
voidmain()
{
int choice, item, f, r, q [10];
f=0; // initialize front end as 0
r=-1; // initialize rear end as -1
for (; ;)
{
printf("\[Link]");
printf ("\n enter choice");
scanf("%d”,&choice);
switch(choice)
{
case1: printf("\n enter item to be inserted");
scanf ("%d", &item);
insertQ(item, &r, q);
break;
case2: deleteQ(q,&f,&r);
break;
case3: displayQ(q,f,r);
break;
default: exit(0);
}
}
}
Disadvantage of queue: Consider the queue as shown below:

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 29

Module 2 M23BCS304

In the above situation, rear insertion is denied even if space is available at the front end.
This is because, before inserting an element, it checks whether the rear is
[Link] so, the Queue is full and the element can’t be inserted. This is a
disadvantage. This disadvantage can be overcome by using a circular queue.

5. Circular Queue: The elements of a given queue can be stored in an array so as to “wrap
around” so that end of the queue is followed by the front of queue.
The pictorial representation of a circular queue is as shown below:

InsertcircularQ (): While inserting elements into the circular queue, the various steps
have to be followed as shown below:
i) Check for Overflow: Before inserting elements, check whether sufficient space is available in
the queue.
ii) Insert item: Increment rear by 1 and then take mod operation and insert item.

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 30

Module 2 M23BCS304

iii) Update count: After inserting item, increment count by 1. Count contains the total number
of elements present in the queue.
The complete insertcircularQ () function is as follows:
void insertcircularQ (int item, int *rear, int *count, int *q)
{
if (*count ==QUEUESIZE)
{
printf (“Queue Full\n”);
return;
}
*rear =(*rear+1) %QUEUESIZE;
q[*rear] = item;
(*count) ++;
}

DeletecircularQ (): While deleting elements from the circular queue, the various steps have
to be followed as shown below:
i) Check for Underflow: Before deleting elements, check whether the queue is empty.
ii) Access item: Access the element by using the front index and then increment the front by 1
and then take mod operation.
iii) Update count: After deleting the item, decrement the count by 1.
iv) Return the item: return the element which was at the index front.

The complete deletecircularQ () function is as follows:

void deletecircularQ (int *front, int *count, int *q)

{
int item;
if (*count ==-1) return -1;
item = q[*front];
*front =(*front+1) %QUEUESIZE;
(*count) --;
}

DisplaycircularQ (): this function first check for a queue empty, if not it will display the
contents of the circular queue starting from the index front. The procedure is repeated for
‘count’ number of times. Here, count gives the total number of elements in the queue. If queue
is empty, it displays the error message as queue empty.

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 31

Module 2 M23BCS304

The displaycircularQ () function is as follows:

void display(int front, int q [ ], int count)

{
int i, j;
if (count ==-1)
{
printf (“Queue Empty”);
return;
}
for (i=1, j=front; i<=count; i++)
{
printf (“%d\n”, q[j]);
j=(j+1) %QUEUESIZE;
}
}
The complete program to implement circular queue using static array is as
follows :
#include <stdio.h>
#include<stdlib.h>
#define MAXSIZE 5
void insert (int item, int *q, int *f, int *r, int *c)
{
if(*c==MAXSIZE)
{
printf ("\n Queue Full ");
return;
}
*r=(*r+1) %MAXSIZE;
q[*r] =item;
(*c) ++;
}
int delete (int *q, int *f, int *c)
{
int x;
if(*c==0) return -1;
x = q[*f];
*f=(*f+1) % MAXSIZE;

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 32

Module 2 M23BCS304

(*c) --;
return x;
}
void display (int *q, int f, int c)
{
int i, j;
if(c==0)
{
printf ("\nQueue is empty");
return;
}
printf ("contents of queue is\n");
for (i=1, j=f; i<=c; i++)
{
printf ("\n%d", q[j]);
j=(j+1) %MAXSIZE;
}
}
void main ()
{
int choice;
int *q, r, f, c, item;
r=-1;
f=0;
c=0;
for (; ;)
{
printf ("\nenter choice");
scanf("%d",&choice);
switch(choice)
{
case 1: printf ("\nenter the item");
scanf ("%d”, &item);
insert (item, q, &f, &r, &c);
break;
case 2: item=delete(q,&f,&c);
if(item==-1)
printf ("\nQueue Empty");

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 33

Module 2 M23BCS304

else
printf ("\nitem deleted = %d”, item);
break;
case 3: display(q,f,c);
break;
default: exit (0);
}
}
}

Circular Queue using Dynamic arrays: If static arrays are used to implement queue, then
the maximum size of the queue should be known during compilation. Since queue size is fixed
during compilation, it is not possible to alter the queue size during execution. This disadvantage
can be overcome using dynamic arrays.
C program to implement circular queue using dynamic arrays
#include <stdio.h>
#include<stdlib.h>
int MAXSIZE=1;
#define MALLOC(p,s)\
if (! (p=malloc(s))) \
{\
printf ("\n memory insufficient"); \
exit(0); \
}
#define REALLOC(p,s) \
if(!(p=realloc(p,s))) \
{\
printf("\n memory insufficient");\
exit(0);\
}
void insert(int item,int *q, int *f, int *r, int *c)
{
int i ;
if(*c==MAXSIZE)
{
printf ("\n QFull: increase size ");
MAXSIZE++;
REALLOC (q, MAXSIZE*sizeof(int));
}
if(*f>*r && *r! =-1)
{

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 34

Module 2 M23BCS304

for (i=MAXSIZE-2; i>=*f; i--)

q[i+1] =q[i]; // shift elements towards right from index ‘f’ to make space for new
item
(*f) ++;
}
*r=(*r+1) %MAXSIZE;
q[*r]=item;
(*c)++;
}
int delete (int *q,int *f,int *c)
{
int x;
if(*c==0)
return -1;
x = q[*f];
*f=(*f+1) % MAXSIZE;
(*c) --;
return x;
}
void display (int *q, int f, int c)
{
int i, j;
if(c==0)
{
printf ("\nQueue is empty");
return;
}
printf ("contents of queue is\n");
for (i=1, j=f; i<=c; i++)
{
printf ("\n%d", q[j]);
j=(j+1) %MAXSIZE;
}
}
void main ()
{
int choice;
int *q,r,f,c,item;
MALLOC(q,sizeof(int));
r=-1;
f=0;
c=0;
for (; ;)
{

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 35

Module 2 M23BCS304

printf ("\nenter choice");

scanf("%d",&choice);
switch(choice)
{
case 1: printf ("\nenter the item");
scanf("%d",&item);
insert(item,q,&f,&r,&c);
break;
case 2: item=delete(q,&f,&c);
if(item==-1)
printf ("\nQueue Empty");
else
printf ("\nitem deleted = %d",item);
break;
case 3: display(q,&f,&c);
break;
default: exit (0);
}
}
}

6. Priority Queue:
It is a special type of queue in which the elements are arranged based on the priority. It is a
special type of queue data structure in which every element has a priority associated with it.
Suppose some elements occur with the same priority, they will be arranged according to the
FIFO principle. The representation of priority queue is shown in the below image -

Insertion in priority queue takes place based on the arrival, while deletion in the priority queue
occurs based on the priority. Priority queue is mainly used to implement the CPU scheduling
algorithms.

There are two types of priority queue that are discussed as follows -

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 36

Module 2 M23BCS304

o Ascending priority queue - In ascending priority queue, elements can be inserted in

arbitrary order, but only smallest can be deleted first. Suppose an array with elements 7,
5, and 3 in the same order, so, insertion can be done with the same sequence, but the
order of deleting the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements can be
inserted in arbitrary order, but only the largest element can be deleted first. Suppose an
array with elements 7, 3, and 5 in the same order, so, insertion can be done with the
same sequence, but the order of deleting the elements is 7, 5, 3.

7. Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can be done from both ends of the
queue either from the front or rear. It means that we can insert and delete elements from both
front and rear ends of the queue. Deque can be used as a palindrome checker means that if we
read the string from both ends, then the string would be the same.

Deque can be used both as stack and queue as it allows the insertion and deletion operations
on both ends. Deque can be considered as stack because stack follows the LIFO (Last In First
Out) principle in which insertion and deletion both can be performed only from one end. And in
deque, it is possible to perform both insertion and deletion from one end, and Deque does not
follow the FIFO principle.

The representation of the deque is shown in the below image -

There are two types of deque that are discussed as follows -

o Input restricted deque - As the name implies, in input restricted queue, insertion
operation can be performed at only one end, while deletion can be performed from

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 37

Module 2 M23BCS304

both ends.

o Output restricted deque - As the name implies, in output restricted queue, deletion
operation can be performed at only one end, while insertion can be performed from
both ends.

8. A MAZING PROBLEM

Mazes have been an intriguing subject for many years. Experimental psychologists train rats to
search mazes for food, and many a mystery novelist has used an English country garden maze
as the setting for a murder. We also are interested in mazes since they present a nice
application of stacks. In this section, we develop a program that runs a maze. Although this
program takes many false paths before it finds a correct one, once found it can correctly rerun
the maze without taking any false paths.
In creating this program the first issue that confronts us is the representation of the maze. The
most obvious choice is a two dimensional array in which zeros represent the open paths and
ones the baiTiers. Figure 3.8 shows a simple maze. We assume that the rat starts at the top left
and is to exit at the bottom right. With the maze represented as a two-dimensional array, the
location of the rat in the maze can at any time be described by the row and column position. If
X marks the spot of our current location, maze[row}[col], then Figure 3.9 shows the possible
moves from this position. We use compass points to specify the eight directions of movement:

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 38

Module 2 M23BCS304

north, northeast, east, southeast, south, southwest, west, and northwest, or N, NE, E, SE, S, SW,
W, NW.
We must be careful here because not every position has eight neighbors. If [row,col} is on a
border then less than eight, and possibly only three, neighbors exist. To avoid checking for
these border conditions we can surround the maze by a border of ones. Thus an m x p maze will
require an (m +2) x (p +2) array. The entrance is at position r 1][1 ] and the exit at [w][p].
Another device that will simplify the problem is to predefine the possible directions to move in
an array, move, as in Figure 3.10. This is obtained from Figure 3.9. We represent the eight
possible directions of movement by the numbers from 0 to 7. For each direction, we indicate
the vertical and horizontal offset.
The C declarations needed to create this table are:
typedef struct
{
short int vert;
short int horiz;
} offsets;
offsets move[8]; /*array of moves for each direction*/

We assume that move is initialized according to the data provided in Figure 3.10. This means
that if we are at position, maze[row}[col}, and we wish to find the position of the next move,
maze[next-row\[next~col\, we set:

Fig: An example maze

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 39

Module 2 M23BCS304

Fig: Allowable moves

Fig: Table of moves

next—row = row + move[dir].vert;

next—col = col + move[dir] .horiz;
As we move through the maze, we may have the choice of several directions of movement.
Since we do not know which choice is best, we save our current position and arbitrarily pick a
possible move. By saving our current position, we can return to it and try another path if we
take a hopeless path. We examine the possible moves starting from the north and moving
clockwise. Since we do not want to return to a previously tried path, we maintain a second two-
dimensional array, mark, to record the maze positions already checked. We initialize this array’s
entries to zero. When we visit a position, maze[raw][col], we change mark[row][cal] to one.
Program 3.7 is our initial attempt at a maze traversal algorithm. EXIT_ROW and EXIT_COL give
the coordinates of the maze exit.

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 40

Module 2 M23BCS304

Although this algorithm describes the essential processing, we must still resolve several issues.
Our first concern is with the representation of the stack. Examining Program 3.7, we see that
the stack functions created in Section 3.2 will work if we redefine element as:

Fig: Initial maze algorithm

We also need to determine a reasonable bound for the stack size. Since each position in the
maze is visited no more than once, the stack need have only as many positions as there are
zeroes in the maze. The maze of Figure 3.11 has only one entrance to exit path. When searching
this maze for an entrance to exit path, all positions (except the exit) with value zero will be on
the stack when the exit is reached. Since, an m x p maze, can have at most mp zeroes, it is
sufficient for the stack to have this capacity.
Program 3.8 contains the maze search algorithm. We assume that the arrays, maze, mark,
move, and stack, along with the constants EXIT-ROW, EXIT-COL, TRUE, and EALSE, and the
variable, top, are declared as global. Notice that path uses a variable found that is initially set to

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 41

Module 2 M23BCS304

zero (i.e., EALSEf. If we find a path through the maze, we set this variable to TRUE, thereby
allowing us to exit both while loops gracefully.
Analysis of path: The size of the maze determines the computing time of path. Since each
position within the maze is visited no more than once, the worst case complexity of the
algorithm is O(mp) where m and p are, respectively, the number of rows and columns of the
maze.

Fig: Simple maze with a long path

Dr. Ranjith K C, Associate Professor, Dept. of CSE(AI&ML), MIT Mysore Page 42