BCS304 - Module 1: Stack 1

Module 2
Stacks and Queues
Stacks: Definition, Stack Operations, Array Representation of Stacks, Stacks using Dynamic Arrays, Stack
Applications: Polish notation, Infix to postfix conversion, Infix to Prefix, evaluation of postfix expression.
Recursion - Factorial, GCD, Fibonacci Sequence, Tower of Hanoi.
Queues: Definition, Array Representation, Queue Operations, Circular Queues, Circular queues using
Dynamic arrays, Dequeues, Priority Queues, Programming Examples.

2.1.1 STACK DEFINITION

“Stack is an ordered collection of elements or items of same type can be inserted and deleted at
only one end called Top of stack”.
STACK is an ordered-list in which insertions (called push) and deletions (called pop) are
made at one end called the top. Since last element inserted into a stack is first element removed,
a stack is also known as a LIFO list (Last In First Out). Stack can be implemented using the
Linked List or Array. Stack belongs to non-primitive linear data structure.

Given a stack S= (a0, ... ,an-1), where a0 is the bottom element, an-1 is the top element, and ai is
on top of element ai-1, 0 < i < n.

Figure 2.1: Inserting and deleting elements in a stack

As shown in the figure 2.1, the elements are added in the stack in the order A, B, C, D, E, then E
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.

2.1.2 ARRAY REPRESENTATION OF STACKS

• Stacks may be represented in the computer in various ways such as one-way linked 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.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 2

• MAX_STACK_SIZE which gives maximum number of elements that can be stored in stack.
Stack can be represented using linear array as shown in the Figure 2.2.

Figure 2.2 : Stack Representation using Array

2.1.3 STACK OPERATIONS

Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from
these basic stuffs, a stack is used for the following two primary operations −
push() − pushing (storing / inserting) an element on the stack.
pop() − removing (accessing/ deleting) an element from the stack.

When data is pushed onto stack, to use a stack efficiently we need to check status of stack as well.
For the same purpose, the following functionality is added to stacks
peek() − get the top data element of the stack, without removing it.
isFull() − check if stack is full or overflow.
isEmpty() − check if stack is empty or underflow.
At all times, we maintain a pointer to the last pushed data on the stack. As this pointer always
represents the top of the stack, hence named top. The top pointer provides top value of the stack
without actually removing it.
Implementation of the stack operations as follows.

1. Stack Create

Stack CreateS(maxStackSize )::=

#define MAX_STACK_SIZE 100 /* maximum stack size*/
typedef typedef struct
{
int key; /* other fields */
} element;
element stack[MAX_STACK_SIZE];
int top = -1;

The element which is used to insert or delete is specified as a structure that consists of only a key
field.
2. Boolean IsEmpty(Stack)::= top < 0;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 3

3. 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 variables stack and top are
global.
bool isFull(){
if(top == N-1){
printf("Stack is full: Overflow State\n");
return true;
}
printf("Stack is not full\n");
return false;
}

4. Push( ) : Function push checks whether stack is full. If it is, it calls stackFull( ), which prints an
error message and terminates execution. When the stack is not full, increment top and assign item
to stack [top].

void push()
{
if(top == N-1) // Checking overflow state
printf("Overflow State: can't add elements into the stack\n");
else{
int x;
printf("Enter element to be pushed into the stack: ");
scanf("%d", &x);
stack[++top] = x;
}
}

5. Pop( ) : Deleting an element from the stack is called pop operation. The element is deleted
only from the top of the stack and only one element is deleted at a time.
int pop ()
{
if(top == -1) // Checking underflow state
printf("Underflow State: empty Stack, can't remove element\n");
else {
int x = stack[top--];
printf("Popping %d out of the stack\n", x);
return x;
}
return -1;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 4

6. stackFull( ) : The stackFull which prints an error message and terminates execution.

bool isFull(){
if(top == N-1){
printf("Stack is full: Overflow State\n");
return true;
}
printf("Stack is not full\n");
return false;
}

2.1.4 C PROGRAM TO IMPLEMENT FIXED STACK OPERATIONS

// Implementing Fixed Stack using an Array in C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define N 10 // N will be the capacity of the Static Stack

int top = -1; // Initializing the top of the stack to be -1
int stack[N]; // Initializing the stack using an array

void push(); // Push element to the top of the stack

int pop(); // Remove and return the top most element of the stack
int peek(); // Return the top most element of the stack
bool isEmpty(); // Check if the stack is in Underflow state or not
bool isFull(); // Check if the stack is in Overflow state or not

int main()
{
printf("FIXED ARRAY (Total Capacity: %d)\n", N);
int choice;
while(1){
printf("\nChoose any of the following options:\n");
printf(" 0: Exit 1: Push 2: Pop 3: Peek\n");
printf(" 4: display 5: Is empty 6: Is full\n\n");
scanf("%d", &choice);
switch(choice){
case 0: return;
case 1: push(); break;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 5

case 2: pop(); break;

case 3: peek(); break;
case 4: display(); break;
case 5: isEmpty(); break;
case 6: isFull(); break;
default: printf("Please choose a correct option!");
}
}
return 0;
}

void push()
{
if(top == N-1) // Checking overflow state
printf("Overflow State: can't add elements into the stack\n");
else{
int x;
printf("Enter element to be pushed into the stack: ");
scanf("%d", &x);
stack[++top] = x;
}
}
int pop()
{
if(top == -1) // Checking underflow state
printf("Underflow State: empty Stack, can't remove element\n");
else{
int x = stack[top--];
printf("Popping %d out of the stack\n", x);
return x;
}
return -1;
}

int peek()
{
int x = stack[top];
printf("%d is the top most element of the stack\n", x);
return x;
}

void display()
{

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 6

int i;
if(top == -1)
printf("\n ** Stack is Empty ** \n");
else {
printf("\n The stack contents are:\n top->");
for(i=top; i>=0; i--)
printf("\t %d", stack[i]);
}
}

bool isEmpty(){
if(top == -1){
printf("Stack is empty: Underflow State\n");
return true;
}
printf("Stack is not empty\n");
return false;
}

bool isFull(){
if(top == N-1){
printf("Stack is full: Overflow State\n");
return true;
}
printf("Stack is not full\n");
return false;
}

2.2 STACKS USING DYNAMIC ARRAYS

The array is used to implement stack, but the bound (MAX_STACK_SIZE) should be
known during compile time. The size of bound is impossible to alter during compilation
hence this can be overcome by using dynamically allocated array for the elements and
then increasing the size of array as needed.

2.2.1 IMPLEMENTING STACK OPERATIONS USING DYNAMIC ARRAY

1. Stack CreateS( ) : Here the MAX_STACK_SIZE is replaced with capacity

{ int capacity=1, top= -1;
int *stack;
stack = (int*) malloc (capacity*sizeof(int)); }

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 7

2. Boolean IsEmpty(Stack)::= top < 0;

3. Boolean IsFull(Stack)::= top >= capacity-1;
4. push()

void push(int item)

{ /* add an item to the global stack */
if(top >= capacity-1)
stackFull();
stack[++top] = item;
}

5. pop( ) : In this function, no changes are made, is same as fixed stack pop()
int pop ( )
{ /* delete and return the top element from the stack */
if (top == -1)
return stackEmpty(); /* returns an error key */
return stack[top--];
}

6. stackFull( )
The new code shown below, attempts to increase the capacity of the array stack so that
new element can be added into the stack. Before increasing the capacity of an array, decide
what the new capacity should be. In array doubling, array capacity is doubled whenever
it becomes necessary to increase the capacity of an array.
void stackFull()
{
capacity *= 2;
stack=(int*)realloc(stack, capacity*sizeof(*stack));
}

2.2.2 IMPLEMENTING DYNAMIC STACK WITH ARRAY DOUBLING

#include<stdio.h>
#include<stdlib.h>
int *stack, capacity=5;
int top=-1, item;
void push()
{
if(top == capacity-1)
doubleStack();//which double the memory when stack is full
printf("enter an item to insert\n");

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 8

scanf("%d", &item);
stack[++top] = item;
}
void pop()
{
if(top == -1)
{
printf("underflow\n"); return;
}
item = stack[top--];
printf("item deleted is %d \n", item);
}
void doubleStack()
{
capacity=capacity*2; // doubling the stack size
stack=realloc(stack,capacity*sizeof(int));// doubling the memory
if(stack==NULL) // if memory is in sufficient
{
printf("memory is insuffient\n"); exit(0);
}
}
void display()
{
int i;
if(top==-1)
{
printf("stack is empty \n");
return;
}
for(i=top;i>=0;i--)
printf("%d",*(stack+i));
}
void main()
{
int choice=1;
stack=malloc(capacity*sizeof(int));// dynamic memory allocatation
while(choice)
{
printf("enter your choice\n [Link]\n [Link]\n [Link] \n * exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1:push(); break;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 9

case 2:pop();break;
case 3:display(); break;
default: free(stack);// deallocating memory
return; // exit from main()
}
}
}

2.2.3 STACK FULL WITH ARRAY DOUBLING ANALYSIS :

In the 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.
Under the assumptions that memory may be allocated in O(1) time and that a stack element can be
copied in O(1) time, the time required by array doubling is O(capacity). Initially, capacity is 1.
Suppose that, if all elements are pushed in stack and the capacity is 2k for some k, k>O, then the

total time spent over all array doublings is O . Since the total
number of pushes is more than 2k-1, the total time spend in array doubling is O(n), where n is the
total number of pushes. Hence, even with the time spent on array doubling added in, the total run
time of push over all n pushes is O(n).

2.3 APPLICATIONS OF STACKS

i Stack is used by compilers to check for balancing of parentheses, brackets and braces.
ii Stack is used to evaluate a postfix expression.
iii Stack is used to convert an infix expression into postfix/prefix form.
iv In recursion, all intermediate arguments and return values are stored on the processor’s stack.
v During a function call the return address and arguments are pushed onto a stack and on return
they are popped off.

2.3.1 EXPRESSIONS

• An algebraic expression is a legal combination of operators and operands. “The sequence of

operators and operands that reduces to a single value after evaluation is called Expression”.
• Operand is the quantity on which a mathematical operation is performed. Operand may be a
variable like x, y, z or a constant like 5, 4, 6 etc.
• Operator is a symbol which signifies a mathematical or logical operation between the operands.
• Examples of familiar operators include +, -, *, /, ^ etc.
• An algebraic expression can be represented using three different notations. They are infix.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 10

Expressions: It is sequence of operators and operands that reduces to a single value after
evaluation 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
➢ 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 its operand.
Example: + A B Here, A & B are operands and + is operand
➢ Postfix or Reverse Polish Expression: In this, the operator appears after its operand.
Example: A B + Here, A & B are operands and + is operand
The three important features of postfix expression are:
• Postfix expression is parenthesis-free expression.
• While evaluating the postfix expression the precedence and Associativity of the
operators is no longer required
• All expressions given to the system, will be converted into postfix form by the complier
since it is easy and more efficient to evaluate.

2.3.2 PRECEDENCE OF THE OPERATORS

We consider six binary arithmetic operations: +, -, *, / and % or ^ (power).

Operators precedence Operators precedence
^ &  4
* / % 3
+ - 2
# ( 1

2.3.3 INFIX TO POSTFIX CONVERSION

Procedure to convert from infix expression to postfix expression is as follows:
1. Push ‘#’ to stack. Scan the infix expression from left to right.
2. If the scanned symbol is an operand, then place directly in the postfix expression (output).
3. If the scanned symbol is left parenthesis, push it onto the stack.
4. If the symbol scanned is a right parenthesis, then go on popping all the items from the stack
and place them in the postfix expression till we get the matching left parenthesis.
5. If the scanned symbol is an operator, then go on removing all the operators from the stack and
place them in the postfix expression, if and only if the precedence of the operator which is on
the top of the stack is greater than (or greater than or equal) to the precedence of the scanned
operator and push the scanned operator onto the stack otherwise,
6. At the END Pop all remining elements in the stack and store in Postfix

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 11

Example -1: The expression a*(b+c)*d which results abc+*d* in postfix.

Symbol Remarks Stack Postfix String
A R1&2: Store in Postfix: a # a
* R5: Push * # * a
( R3: Push ( # * ( a
B R2: Store in Postfix: b # * ( ab
+ R5: Push + # * ( + ab
C R2: Store in Postfix: c # * ( + abc
) R4: Pop until ( and store in Postfix # * abc+
* R5: Pop *, store in Postfix and push * # * abc+*
D R2: Store in Postfix: d # * abc+*d
END R6: Pop all items and store in Postfix # abc+*d*

Example -2: Convert ((A – (B + C)) * D) ^ (E + F) infix expression to postfix form:

Symbol Remarks Stack Postfix String
( R1 & R3: Push ( # (
( R3: Push ( # ( (
A R2: Store in Postfix: A # ( ( A
- R5: Push - # ( ( - A
( R3: Push ( # ( ( - ( A
B R2: Store in Postfix: B # ( ( - ( AB
+ R5: Push + # ( ( - ( +
C R2: Store in Postfix: C # ( ( - ( + ABC
) R4: Pop until ( and store in Postfix # ( ( - ABC+
) R4: Pop until ( and store in Postfix # ( ABC+-
* R5: Push * # ( * ABC+-
D R2: Store in Postfix: D # ( * ABC+-D
) R4: Pop until ( and store in Postfix # ABC+-D*
^ R5: Push ^ # ^ ABC+-D*
( R3: Push ( # ^ ( ABC+-D*
E R2: Store in Postfix: E # ^ ( ABC+-D*E
+ R5: Push + # ^ ( + ABC+-D*E
F R2: Store in Postfix: F # ^ ( + ABC+-D*EF
) R4: Pop until ( and store in Postfix # ^ ABC+-D*EF+
END R6: Pop all items and store in Postfix # ABC+-D*EF+^

Example -3: Convert the following infix expression A + B * C – D / E * H to postfix expression

Symbol Remarks Stack Postfix String
A R2: Store in Postfix: A # A
+ R5: Push + # + A
B R2: Store in Postfix: B # + AB
* R5: Push * # + * AB
C R2: Store in Postfix: C # + * ABC
- R5: pop and push - # - ABC*+
D R2: Store in Postfix: D # - ABC*+D
/ R5: Push / # - / ABC*+D
E R2: Store in Postfix: E # - / ABC*+DE
* R5: pop and push * # - * ABC*+DE/
H R2: Store in Postfix: H # - * ABC*+DE/H
END R6: Pop all items and store in Postfix # ABC*+DE/H*-

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 12

#include<stdio.h> // Program to convert infix to postfix expression

char s[100], top=-1;
void push(char opr)
{
s[++top]=opr;
}
char pop()
{
return(s[top--]);
}
int priority(char opr)
{
if(opr=='('|| opr=='#') return(1);
if(opr=='+'|| opr=='-') return(2);
if(opr=='*'|| opr=='/' || opr=='%') return(3);
if(opr=='^') return(4);
}
void main()
{
char infix[20],postfix[20];
int i,j=0;
printf("\nEnter valid INFIX expression\n");
gets(infix);
push('#');
for(i=0;infix[i]!='\0';i++) { // Rule 1
if(isalnum(infix[i])) // Rule 2
postfix[j++]=infix[i];
else if(infix[i]=='(') // Rule 3
push('(');
else if(infix[i]==')') // Rule 4
{
while(s[top]!='(') {
postfix[j++]=pop();
}
pop();
}
else
{
while(priority(s[top])>=priority(infix[i])) { // Rule 5
postfix[j++]=pop();
}
push(infix[i]);
}
}
while(s[top]!='#') // Rule 6 at the END pop all the elements
postfix[j++]=pop();
postfix[j]='\0';
printf("\n INFIX EXPRESSION = %s",infix);
printf("\n POSTFIX EXPRESSION = %s",postfix);
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 13

Analysis of postfix: Let n be the number of tokens in the expression. Ө (n) time is spent extracting
tokens and outputting them. Time is spent in the two while loops, is Ө (n) as the number of tokens
that get stacked and unstacked is linear in n. So, the complexity of function postfix is Ө (n).

2.3.4 EVALUATION OF POSTFIX EXPRESSION

The postfix expression is evaluated easily by the use of a stack. When a number is seen, it is pushed
onto the stack; when an operator is seen, the operator is applied to the two numbers that are popped
from the stack and the result is pushed onto the stack. When an expression is given in postfix
notation, there is no need to know any precedence rules; this is our obvious advantage. Although
infix notation is the most common way of writhing expressions, it is not the one used by compilers
to evaluate expressions. Instead compilers typically use a parenthesis-free postfix notation.
Algorithm Steps for evaluating postfix expression
1) Scan the symbol from left to right.
2) If the scanned-symbol is an operand, push it on to the stack.
3) If the scanned-symbol is an operator, pop two operands from the stack. The first popped
operand acts as operand2 and the second popped operand act as operand 1. Now perform the
indicated operation and Push the result on to the stack.
4) Repeat the above procedure till the end of input is encountered.
Example : Evaluate the postfix expression: 6 5 2 3 + 8 * + 3 + * [Jan2019]
Symbol Remarks Op1 Op2 Value Stack
6 R2: Push 6 6
5 R2: Push 5 65
2 R2: Push 2 652
3 R2: Push 3 6523
+ R3 Op2=Pop, Op1=Pop and Push result 2 3 5 655
8 R2: Push 8 6558
* R3 Op2=Pop, Op1=Pop and Push result 5 8 40 6 5 40
+ R3 Op2=Pop, Op1=Pop and Push result 5 40 45 6 45
3 R2: Push 3 6 45 3
+ R3 Op2=Pop, Op1=Pop and Push result 45 3 48 6 48
* R3 Op2=Pop, Op1=Pop and Push result 6 48 288 288

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 14

2.3.5 RECURSION
Recursion is the process of repeating items in a self-similar way. In programming languages, if a
program allows you to call a function inside the same function, then it is called a recursive call of
the function.
• A recursive function is a function that calls itself during its execution.
• But while using recursion, programmers need to be careful to define an exit condition
from the function; otherwise it will go into an infinite loop.
• Recursive functions are very useful to solve many mathematical problems, such as
calculating the factorial of a number, generating Fibonacci series, etc.
Example Program 1: Calculates the factorial of a given number.

#include<stdio.h>
int main()
{
int n;
printf("Enter a positive integer: ");
scanf("%d",&n);
printf("Factorial of %d = %ld", n, fact(n));
return 0;
}

long int fact(int n) {

if (n>=1)
return n*fact(n-1);
else
return 1;
}
Example Program 2: Calculates the GCD using recursion.
𝑎 𝑖𝑓 𝑏 == 0
𝐺𝐶𝐷(𝑎, 𝑏) = {
𝐺𝐶𝐷(𝑏, 𝑎%𝑏) 𝑖𝑓𝑏 > 0
#include <stdio.h>
int main() {
int n1, n2;
printf("Enter two positive integers: ");
scanf("%d %d", &n1, &n2);
printf("G.C.D of %d and %d is %d.", n1, n2, gcd(n1, n2));
return 0;
}
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 15

Example Program 2: Generate Fibonacci series using recursion.

#include<stdio.h>
#include<conio.h>
int fibonacci(int);
void main(){
int n, i;
printf("Enter the number of element you want in series :\n");
scanf("%d",&n);
printf("fibonacci series is : \n");
for(i=0;i<n;i++) {
printf("%d ",fibonacci(i));
}
}
int fibonacci(int i){
if(i==0) return 0;
else if(i==1) return 1;
else return (fibonacci(i-1)+fibonacci(i-2));
}

Example Program 3: Binary Search using recursion.

#include <stdio.h>
int recursiveBinarySearch(int arr[], int start, int end, int ele){
if (end >= start){
int mid = start + (end - start )/2;
if (arr[mid] == ele)
return mid;
if (arr[mid] > element)
return recursiveBinarySearch(arr, start, mid-1, ele);
return recursiveBinarySearch(arr, mid+1, end, ele);
}
return -1;
}
int main(void){
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 9;
int found_index = recursiveBinarySearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf("Element not found in the array ");
}
else {
printf("Element found at index : %d",found_index);
}
return 0;
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 16

TOWER OF HANOI PROBLEM

Tower of Hanoi, is a mathematical puzzle which consists of three tower (pegs) and more than
one rings; as depicted in below figure.

These rings are of different sizes and

stacked upon in an ascending order, i.e.
the smaller one sits over the larger one.
There are other variations of the puzzle
where the number of disks increase, but
the tower count remains the same.

Rules : The mission is to move all the disks to some another tower without violating the sequence
of arrangement. A few rules to be followed for Tower of Hanoi are −

• Only one disk can be moved among the towers at any given time.
• Only the "top" disk can be removed.
• No large disk can sit over a small disk.
Tower of Hanoi puzzle with n disks can be solved in minimum 2n − 1 steps. This presentation
shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.

Algorithm: To write an algorithm for Tower of Hanoi, first we need to learn how to solve this
problem with lesser amount of disks, say → 1 or 2. We mark three towers with
name, source, destination and aux (only to help moving the disks). If we have only one disk,
then it can easily be moved from source to destination peg.

Step 1 − Move n-1 disks from source to aux

Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

PROGRAM Scan to see Animation

#include<stdio.h>
#include<conio.h>
#include <stdio.h>
void towers(int, char, char, char);
int main()
{
int num;
printf("Enter the number of disks : ");
scanf("%d", &num);
printf("The sequence of moves in the Tower of Hanoi are :\n");
towers(num, 'A', 'C', 'B');
return 0;
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 17

void towers(int num, char source, char dest, char aux)

{
if(num == 1)
{
printf("\n Move disk 1 from %c to %c", source, dest);
return;
}
towers(num - 1, source, aux,dest);
printf("\n Move disk %d from %c to %c", num, source, dest);
towers(num - 1, aux, dest, source);
}

CONVERSION OF INFIX TO PREFIX

A prefix notation is another form of expression but it does not require other information such as
precedence and associativity, whereas an infix notation requires information of precedence and
associativity. It is also known as polish notation. In prefix notation, an operator comes before the
operands. The syntax of prefix notation is given below:
<operator> <operand> <operand>

For example, if the infix expression is A+B, then the prefix expression corresponding to this infix
expression is +AB.
We consider precedence of six binary arithmetic operations: +, -, *, / and % or ^ (power).
Operators precedence Operators precedence
^ &  4
* / % 3
+ - 2
# ( 1

Procedure to convert from infix expression to prefix expression is as follows:

1. Reverse the infix expression Push ‘#’ to stack. Scan the infix expression from left to right.
2. If the scanned symbol is an operand, then place directly in the prefix expression.
3. If the scanned symbol is left parenthesis, push it onto the stack.
4. If the symbol scanned is a right parenthesis, then go on popping all the items from the stack
and place them in the prefix expression till we get the matching left parenthesis.
5. If the scanned symbol is an operator, then go on removing all the operators from the stack and
place them in the prefix expression, if and only if the precedence of the operator which is on the
top of the stack is greater than (or greater than or equal) to the precedence of the scanned
operator and push the scanned operator onto the stack otherwise,
6. At the END Pop all remining elements in the stack and store in prefix, reverse prefix and display.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 18

Example: Infix Expression: ( A + B ) * C – D + F

Symbol Remarks Stack Prefix String
R1: Reverse Infix Expression #
F + D – C * ( B + A ) and scan
from left to right
F R2: Store in Prefix # F
+ R3: Push + # + F
D R2: Store in Prefix # + F D
- R5: Pop + and Push - # - F D +
C R2: Store in Prefix # - F D + C
* R5: Push * # - * F D + C
( R3: Push ( # - * ( F D + C
B R2: Store in Prefix # - * ( F D + C B
+ R5: Push + # - * ( + F D + C B
A R2: Store in Prefix # - * ( + F D + C B A
) R4: Pop until ( and store in Prefix # - * F D + C B A +
END R6: Pop all items, store in Prefix, reverse # F D + C B A + * -
prefix string.
FINAL Prefix is - * + A B C + D F

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 19

2.4 QUEUE
Queue is an ordered-list in which insertions &
deletions take place at different ends. The end at
which new elements are added is called the rear
&the end from which old elements are deleted is
called the front. Since first element inserted into
a queue is first element removed, queues are
known as FIFO lists.
Queue is an abstract data structure, somewhat similar to Stack. In contrast to Queue, queue is
opened at both ends. One end is always used to insert data (enqueue) and the other is used to
remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored
first will be accessed first.(as shown in following figure).

2.4.1 Application of Queues

Queue, as the name suggests is used whenever

we need to have any group of objects in an
order in which the first one coming in, also
gets out first while the others wait for there
turn, like in the following scenarios:
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.

2.4.2 QUEUE REPRESENTATION USING ARRAY

• Queues may be represented by one-way lists or

linear arrays.
• Queues will be maintained by a linear array
QUEUE and two pointer variables:
FRONT-containing the location of the front element of the queue
REAR-containing the location of the rear element of the queue.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 20

• The condition FRONT = NULL or -1 will indicate that the queue is empty.
• Queues appear as a group of elements stored at contiguous locations in memory. Each
successive insert operation adds an element at the rear end of the queue while each
delete operation removes an element from the front end of the queue.
• The location of the front and rear ends are marked by two distinct pointers called front
and rear. Figure 5.3 shows the logical representation of queues in memory.

2.4.3 QUEUE OPERATIONS

Queue operations may involve initializing or defining the queue, utilizing it and then completing
erasing it from memory. Here we shall try to understand basic operations associated with queues−
• insert() − add (store) an item to the queue.
• remove() − remove (access) an item from the queue.
Few more functions are required to make above mentioned queue operation efficient. These are −
• peek() − get the element at front of the queue without removing it.
• isfull() − checks if queue is full.
• isempty() − checks if queue is empty.
In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or
storing) data in queue we take help of rear pointer.

➢ peek() Like Queues, this function helps to see the data at the front of the queue. Code for
the peek() function −

int peek()
{
return queue[front];
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 21

➢ isfull() : As we are using single dimension array to implement queue, we just check for the
rear pointer to reach at MAXSIZE to determine that queue is full. In case we maintain
queue in a circular linked-list, the algorithm will differ. Implementation of isfull() function
in C programming language −
bool isfull()
{
if(rear == MAXSIZE - 1)
return true;
else
return false;
}

➢ isempty() : Here's the C programming code −

bool isempty()
{
if(front < 0 || front > rear)
return true;
else
return false;
}

Insert Operation
As queue maintains two data pointers, front and rear, its operations are comparatively more
difficult to implement than Queue.(as shown in following figure)

The following steps should be taken to enqueue (insert) data into a queue −
• Step 1 − Check if queue is full.
• Step 2 − If queue is full, produce overflow error and exit.
• Step 3 − If queue is not full, increment rear pointer to point next empty space.
• Step 4 − Add data element to the queue location, where rear is pointing.
• Step 5 − return success.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 22

Implementation of enqueue() in C programming language −

void enqueue(int data)
{
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
}

Dequeue (Delete) Operation

Accessing data from queue is a process of two tasks − access the data where front is pointing and
remove the data after access. (As shown in figure 13).The following steps are taken to perform
delete operation −
• Step 1 − Check if queue is empty.
• Step 2 − If queue is empty, produce underflow error and exit.
• Step 3 − If queue is not empty, access data where front is pointing.
• Step 4 − Increment front pointer to point next available data element.
• Step 5 − return success.

Figure 13: Queue Dequeue

Implementation of dequeue() in C programming language −

int dequeue()
{
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
IMPLEMENTATION OF QUEUE
#include <stdio.h> // implementation of Queue
#define SIZE 5
int front=-1, rear=-1; /*Initializing the front & rear pointer*/
void main()
{
int Q[SIZE]; /*Declaring a 10 element queue array*/

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 23

int choice, num1=0,num2=0;

while(1)
{
printf("\nSelect a choice from the following:");
printf("\n[1] Add an element into the queue");
printf("\n[2] Remove an element from the queue");
printf("\n[3] Display the queue elements");
printf("\n[*] Exit\n");
printf("\n\tYour choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n\tEnter the element to be added to queue:");
scanf("%d",&num1);
insert(Q, num1); /*Adding an element*/
display(Q);
break;
case 2: if(front==-1 && rear==-1)
{ printf("\nQueue is empty");
break;
}
num2=del(Q); /*Removing an element*/
printf("\n\t%d is the deleting element",num2);
display(Q);
break;
case 3: display(Q); /*Displaying queue elements*/
break;
default: return;
} // end of switch
}// end of while
} // end of main()

void insert(int queue[], int element) /*Insert function*/

{
if(rear == SIZE-1 ) /*Checking whether the queue is full*/
{
printf("Queue is full, insert not possible");
return;
}
if(front==-1) /*Adding element in an empty queue*/
{
front = rear = 0;
queue[front] = element;
return;
}
queue[++rear] = element; /*Incrementing rear and Inserting */
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 24

int del(int queue[]) /*Delete function*/

{
int i;
if(front==-1 && rear==-1) /*Checking whether queue is empty*/
{
printf("\n\tQueue is Empty.\n");
return(-1);
}
if(front==rear) /*if queue has only one element */
{
i=queue[front];
front=-1;
rear=-1;
return(i);
}
return(queue[front++]); /*Returning the front element*/
}

void display(int queue[]) /*Display function*/

{
int i;
if(front==-1)
{
printf("\n\tQueue is Empty!\n");
return;
}
printf("\n\tThe various queue elements are:\n Front->");
for(i=front;i<=rear;i++)
printf("\t%d",queue[i]); /*Printing queue elements*/
printf("\t<-Rear");
}

2.4.4 Example: Job scheduling

• Queues are frequently used in creation of a job queue by an operating system. If the
operating system does not use priorities, then the jobs are processed in the order they
enter the system.
• Figure illustrates how an operating system process jobs using a sequential
representation for its queue.

Figure: Insertion and deletion from a sequential queue

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 25

2.4.5 Drawback of Queue

When item enters and deleted from the queue, the queue gradually
shifts to the right as shown in figure.
In this above situation, when we try to insert another item, which
shows that the queue is full . This means that the rear index equals
to MAX_QUEUE_SIZE -1. But even if the space is available at the front end, rear insertion cannot
be done.
Overcome of Drawback using different methods

Method 1:
• When an item is deleted from the queue, move the entire
queue to the left so that the first element is again at
queue[0] and front is at -1. It should also recalculate rear
so that it is correctly positioned.

• Shifting an array is very time-consuming when there are

many elements in queue & queueFull has worst case
complexity of O(MAX_QUEUE_SIZE)
One major disadvantage of queue is the limited space. The queue will
only hold as many or even lesser elements as the array's size is fixed.
Unfilled space will not be utilized as the front pointer of the queue
would have moved ahead. However the best way to implement a queue
is by using circular queue or dynamic queue a linked list.

Method 2: Circular Queue

• It is “The queue which wrap around the end of the
array.” The array positions are arranged in a circle.

• In this convention the variable front is changed. front

variable points one position counter clockwise from
the location of the front element in the queue. The convention for rear is unchanged.

Implementation of Circular Queue

#include<stdio.h> // Circular Queue

#define MAX 5

int front=-1;
int rear=-1;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 26

void insert(int CQ[], int element) /*Insert function*/

{
if((front==0 && rear ==MAX-1) || front==rear+1) {
printf("\tQueue is Full. \n");
return;
}
if(front==-1) { /*Adding element in an empty queue*/
front=0;
rear=0;
}
else if(rear==MAX-1)
rear=0; /*Setting rear pointer to start of queue*/
else
rear=rear+1; /*Incrementing rear pointer*/

CQ[rear]=element; /*Inserting the new element*/

}

int del(int CQ[]) /*Delete function*/

{
int i;
if(front==-1) { /*Checking whether the queue is empty*/
printf("\n\tQueue is Empty.\n");
return (-9999);
}
i=CQ[front]; /*Retrieving the element at the front of the queue*/
if(front==rear) {
front=-1;
rear=-1;
return(i);
}
else if(front==MAX-1) {
front=0; /*Setting the front pointer to start of queue*/
return(i);
}
else{
front=front+1; /*Incrementing the front pointer*/
return(i);
}
}

void display(int CQ[]) /*Display function*/

{
int i;
if(front==-1) {
printf("\n\tQueue is Empty!\n");
return;
}
printf("\n\tThe various queue elements are:\n");
i=front;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 27

while(i!=rear)
{
printf("\t%d",CQ[i]); /*Printing queue elements*/
if(i==MAX-1)
i=0;
else
i=i+1;
}
printf("\t%d\n",CQ[i]); /*Printing the last element in the queue*/
}

void main()
{
int choice, Q[MAX], num1=0,num2=0;
while(1)
{
printf("\nSelect a choice from the following:");
printf("\n[1] Add an element into the queue");
printf("\n[2] Remove an element from the queue");
printf("\n[3] Display the queue elements");
printf("\n[*] Exit\n");
printf("\n\tYour choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter the element to be added to the queue: ");
scanf("%d",&num1);
insert(Q, num1); /*Adding an element*/
break;
case 2: if(front==-1) { /*Checking whether the queue is empty*/
printf("\n\tQueue is Empty.\n");
break;
}
num2=del(Q);
printf("\n\t%d element removed from the queue\n\t",num2);
break;
case 3: display(Q); /*Displaying queue elements*/
break;
default: return;
} // end of switch
} // end of while
} // end of main()

Note:
• When queue becomes empty, then front =rear. When the queue becomes full and
front =rear. It is difficult to distinguish between an empty and a full queue.

• To avoid the resulting confusion, increase the capacity of a queue just before it
becomes full.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 28

2.4.6 CIRCULAR QUEUES USING DYNAMIC ARRAYS

• A dynamically allocated array is used to hold the queue elements. Let capacity be the
number of positions in the array queue.
• To add an element to a full queue, first increase the size of this array using a function
realloc. As with dynamically allocated stacks, array doubling is used.

Consider the full queue of figure (a). This figure shows a queue with seven elements in an
array whose capacity is 8. A circular queue is flatten out the array as in Figure (b).

Figure (c) shows the array after array doubling by relloc

To get a proper circular queue configuration, slide the elements in the right segment (i.e.,
elements A and B) to the right end of the array as in figure (d).

To obtain the configuration as shown in figure (e), follow the steps

1) Create a new array newQueue of twice the capacity.

2) Copy the second segment (i.e., the elements queue [front +1] through queue [capacity-1]) to
positions in newQueue beginning at 0.
3) Copy the first segment (i.e., the elements queue [0] through queue [rear]) to positions in
newQueue beginning at capacity – front – 1.

2.5. DEQUEUES OR DEQUE

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 29

A deque (double ended queue) is a linear list in which elements can be added or removed at
either end but not in the middle.
Representation
• Deque is maintained by a circular array DEQUE with pointers LEFT and RIGHT, which
point to the two ends of the deque.

• Figure shows deque with 4 elements maintained in an array with N = 8 memory locations.
• The condition LEFT = NULL will be used to indicate that a deque is empty.

There are two variations of a deque

1. Input-restricted deque is a deque which allows insertions at only one end of the list but
allows deletions at both ends of the list

2. Output-restricted deque is a deque which allows deletions at only one end of the list but
allows insertions at both ends of the list.

2.6 PRIORITY QUEUES

A priority queue is a collection of elements such that each element has been assigned a priority and
such that the order in which elements are deleted and processed comes from the following rules:
(1) An element of higher priority is processed before any element of lower priority.

(2) Two elements with the same priority are processed according to the order in which
they were added to the queue.
A prototype of a priority queue is a timesharing system: programs of high priority are processed
first, and programs with the same priority form a standard queue.
2.6.1 Representation of a Priority Queue

One way to maintain a priority queue in memory is by means of a one-way list, as follows:
1. Each node in the list will contain three items of information: an information field INFO, a
priority number PRN and a link number LINK.

2. A node X precedes a node Y in the list

a. When X has higher priority than Y
b. When both have the same priority but X was added to the list before Y. This means that
the order in the one-way list corresponds to the order of the priority queue.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 30

Example:
• Below Figure shows the way the priority queue may appear in memory using linear arrays
INFO, PRN and LINK with 7 elements.

• The diagram does not tell us whether BBB was added to the list before or after DDD. On
the other hand, the diagram does tell us that BBB was inserted before CCC, because BBB
and CCC have the same priority number and BBB appears before CCC in the list.

Algorithm to add an element to priority queue

Adding an element to priority queue is much more complicated than deleting an element from the
queue, because we need to find the correct place to insert the element.
Algorithm: This algorithm adds an ITEM with priority number N to a priority queue which is
maintained in memory as a one-way list.
1. Traverse the one-way list until finding a node X whose priority number exceeds N. Insert
ITEM in front of node X.

2. If no such node is found, insert ITEM as the last element of the list.

The main difficulty in the algorithm comes from the fact that ITEM is inserted before node X.
This means that, while traversing the list, one must also keep track of the address of the node
preceding the node being accessed.
Example:
Consider the priority queue in Fig (a). Suppose an item XXX with priority number 2 is to be
inserted into the queue. We traverse the list, comparing priority numbers.

Fig(a) : before insert operation

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 31

Fig(b) : after the insert operation

Observe that DDD is the first element in the list whose priority number exceeds that of XXX.
Hence XXX is inserted in the list in front of DDD, as pictured in Fig(b). Observe that XXX comes
after BBB and CCC, which have the same priority as XXX. Suppose now that an element is to be
deleted from the queue. It will be AAA, the first element in the List. Assuming no other insertions,
the next element to be deleted will be BBB, then CCC, then XXX, and so on.

Algorithm to deletes and processes the first element in a priority queue

Algorithm: This algorithm deletes and processes the first element in a priority queue which
appears in memory as a one-way list.
1. Set ITEM:= INFO[START] [This saves the data in the first node.]
2. Delete first node from the list.
3. Process ITEM.
4. Exit.

2.6.2 Array Representation of a Priority Queue

• Another way to maintain a priority queue in memory is to use a separate queue for each
level of priority (or for each priority number).

• Each such queue will appear in its own circular array and must have its own pair of
pointers, FRONT and REAR.

• If each queue is allocated the same amount of space, a two-dimensional array QUEUE
can be used instead of the linear arrays.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 BCS304 - Module 1: Stack 32

Observe that FRONT[K] and REAR[K] contain, respectively, the front and rear elements of row
K of QUEUE, the row that maintains the queue of elements with priority number K.
The following are outlines or algorithms for deleting and inserting elements in a priority queue
Algorithm: This algorithm deletes and processes the first element in a priority queue maintained
by a two-dimensional array QUEUE.
1. [Find the first non-empty queue.] Find the smallest K such that FRONT[K] ≠ NULL.
2. Delete and process the front element in row K of QUEUE.
3. Exit.

Algorithm: This algorithm adds an ITEM with priority number M to a priority queue maintained
by a two-dimensional array QUEUE.
1. Insert ITEM as the rear element in row M of QUEUE.
2. Exit.

2.7 MULTIPLE STACKS AND QUEUES

In multiple stacks, we examine only sequential mappings of stacks into an array. The array is
one dimensional which is memory[MEMORY_SIZE]. Assume n stacks are needed, and then
divide the available memory into n segments. The array is divided in proportion if the expected
sizes of the various stacks are known. Otherwise, divide the memory into equal segments.
Assume that i refers to the stack number of one of the n stacks. To establish this stack, create
indices for both the bottom and top positions of this stack. boundary[i] points to the position
immediately to the left of the bottom element of stack i, top[i] points to the top element. Stack
i is empty iff boundary[i]=top[i].

The declarations are:

#define MEMORY_SIZE 100 /* size of memory */
#define MAX_STACKS 10 /* max number of stacks plus 1 */ element
memory[MEMORY_SIZE]; /* global memory declaration */ int top
[MAX_STACKS];
int boundary [MAX_STACKS] ;
int n; /*number of stacks entered by the user */
To divide the array into roughly equal segments
top[0] = boundary[0] = -1;
for (j= 1;j<n; j++)
top[j] = boundary[j] = (MEMORY_SIZE / n) * j;
boundary[n] = MEMORY_SIZE - 1;

Figure: Initial configuration for n stacks in memory [m].

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
BCS304 - Module 1: Stack 33

In the figure, n is the number of stacks entered by the user, n < MAX_STACKS, and
m =MEMORY_SIZE. Stack i grow from boundary[i] + 1 to boundary [i + 1] before it is full.
A boundary for the last stack is needed, so set boundary [n] to MEMORY_SIZE-1.
Implementation of the add operation
void push(int i, element item)
{ /* add an item to the ith stack */
if (top[i] == boundary[i+l])
stackFull(i);
memory[++top[i]] = item;
}

Program: Add an item to the ith stack

Implementation of the delete operation
element pop(int i)
{ /* remove top element from the ith stack */
if (top[i] == boundary[i])
return stackEmpty(i);
return memory[top[i]--];
}
Program: Delete an item from the ith stack
The top[i] == boundary[i+1] condition in push implies only that a particular stack ran out of
memory, not that the entire memory is full. But still there may be a lot of unused space between
other stacks in array memory as shown in Figure. Therefore, create an error recovery function
called stackFull , which determines if there is any free space in memory. If there is space
available, it should shift the stacks so that space is allocated to the full stack.
Method to design stackFull
• Determine the least, j, i < j < n, such that there is free space between stacks j and j+1.
That is, top[j ] < boundary[j+l]. If there is a j, then move stacks i+l,i+2, .., j one
position to the right (treating memory[O] as leftmost and memory[MEMORY_SIZE -
1] as rightmost). This creates a space between stacks i and i+1.
• If there is no j as in (1), then look to the left of stack i. Find the largest j such that 0 ≤
j≤ i and there is space between stacks j and j+ 1 ie, top[j] < boundary[j+l]. If there is a
j, then move stacks j+l, j+2, ... , i one space to the left. This also creates space between
stacks i and i+1.
• If there is no j satisfying either condition (1) or condition (2), then all
MEMORY_SIZE spaces of memory are utilized and there is no free space. In this
case stackFull terminates with an error message.
******

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]