UNIT-II STACKS AND QUEUE

Linear and Non-Linear Data Structures:

A data structure is said to be Linear, if its elements forms linear sequence or data is store sequentially in
memory locations.
The example of linear data structure are, array, stack, queue an linked list.

In Non-linear data structure data are not stored sequentially or in linear fashion. The example of Non-linear
data structure are Tree and Graphs. Which represent hierarchical relationship between individual item.

Stack:

The stack is considered as an ordered group of items because element occurs in a sequence according to
how long they have been in the stack The item that have been in the stock, the longest time are at the
bottom and most recent are at the top.
Stack is a very important data structure that is automatically used by some programs such as recursion,
conversion of infix to postfix or infix to prefix expression.

"A stack is a data structure in which elements are added and removed from one end, Last in first out
structures (LIFO)".
In this list (Linear data structure) insertion and deletions are made a one end, called the top of stack.

For example, if your favorite green shirts is underneath of old blue one in the stack of shirts, if you want to
wear this green shirt today, you must remove the first blue shirt (the top element) from the stack, only
then you can take the desired green shin, which will be now on the top of the stack.

Most micro-processor (like one in your computer) use a stack based architecture. When a member
function is called, it return address and arguments pushed into a stack, and when function returns they are
popped off, the stack operations are built into the micro-processor.
(1) Array - Representation of a stack:
The operations on a stack are represented by using vector consisting of number of elements.
A pointer top keeps stack of the top elements, when stack is empty, top has a value 0.

Each time a new element is added at top, top is incremented by one, when a element is deleted from a
top, top is decrement by one.

(2) PUSH and POP Operations on Stack:

The stack as an abstract data type (ADT), the operations that add an element to the top of the stack is
usually called PUSH operations. The operation that take the top element from the top of stack is called
POP operation.

When we begin using stack, it should be empty so another necessary operation is one that creates an
empty stack. (Empty stack of Null elements). This operation is known as create stack. We must also check
that whether a stack contains any elements before we pop it from the stack.

We also perform a operation that destroy a stack for leaving the stack empty, this is know as a destroy
stack operation.

(A) PUSH Operation:

In push operation, we can add element to the top of the stack, so before push operation, user must check
the stack, it should not be a full.
If stack is already full and when we try to add the elements (push operation), then a stack over flow error
occurs. It is called 'Stack Over Flow' condition.

PUSH (S, Top, X)

This procedure (function) inserts an elements x to the top of stack, which is represented by a vector S
containing N elements with Top pointer at top element in the stack.

Algorithm: PUSH (S, Top, X)

Step 1 : [Check for stack over flow]

if Top >= N
then write ("stack over flow")
Exit

Step 2: [increment Top pointer by value one]

Top-Top+1
Step 3: [perform Insertion]
S [Top] X

Step 4: [Finished]
Exit

The first step of this algorithm checks for an overflow condition, if stack is full means Top pointer value
reach at size of stack, then insertion cannot be performed.
In second & Third step, if stack is not full, a top pointer value increment by one and insert a value to top
pointer element.
(B) POP Operation:

In pop operation, we can delete or remove a element from top of the stack. So before pop operation, user
must check the stack, stack should not be a empty.
If a stack is empty, and we can try to pop (delete) an element, then a stack under flow error occurs. It is
called 'Stack Under Flow’ condition.

POP (S. Top)

This procedure (function), delete (remove) an element from the top of the stack, which is represented by a
vector S containing N element with a Top pointer at top elements in the stack.

Algorithm: POP (S, Top)

Step 1: [check for under flow or check whether the stack is empty]
If (Top = 0) OR (Top=-1)
then
write ("Stack under flow")
Exit

Step 2: [Decrement pointer/remove the top information]

Value S [Top]
TopTop-1

Step 3: [Return former top element of the stack]

write (value)

Step 4: [Finished]
Exit

The first step of algorithm checks for an under flow condition, if stack is empty means top pointer value is
zero, so we can not pop the element. a variable value.

In second & Third step, if stack is not empty, then a top element value stored in and then decrement top
pointer by one and then return at former top element of the stack.

(3) Implementation of stack:

#include<stdio.h>
#include<conio.h>
void main()
{
int top=-1,s[5],n,ch,x,i;
clrscr();
printf("enter size of stack");
scanf("%d",&n);
do
{
printf("\n1.push");
printf("\n2.pop");
printf("\n3.display");
printf("\n4.exit");
printf("\nenter choice");
scanf("\n%d",&ch);
switch(ch)
{
case 1:
if(top>=n)
{
printf("overflow");
}
else
{
top=top+1;
printf("enter element");
scanf("%d",&x);
s[top]=x;
}
break;
case 2:
if(top==-1)
{
printf("underflow");
}
else
{
x=s[top];
top=top-1;
printf("\nelement deleted");
}
break;
case 3:
if(top==-1)
{
printf("empty stack");
}
else
{
for(i=top;i>=0;i--)
{
printf("\n%d",s[i]);
}
}
break;
case 4:
break;
default:
printf("invalid choice");
 break;
}

} while(ch!=4);
getch();
}

(4) Application of Stack:

1. Recursion, recursion is an important facility in many programming language, such a ALGOL 60, PASCAL, C
etc.
2. Stack machines, certain computers perform stack operation at the hardware or machine level.
3. Compilation of infix expression into object code.
4. Representation of Polish Notations.

(5) Infix, Prefix and Post fix Forms of Expressions:

Polish Notation:

One of the major use of stack is a Polish notation or polish Expression.

The process of writing the operators of an expression either before their operands or after operands a are
called the Polish Notation. The polish Notation discovered by mathematician name Jan Luksic Weiz

The polish notation are classified into three categories:

(1) Infix (2) Prefix (3) Postfix

When the operators exist between two operands then the expression is called Infix Expression.
Consider the sum of A and B, we apply operator "+" between two operands and write the expression sum
as A+B, this expression is called infix expression.

When the operator are written before their operand then the resulting expression is called prefix polish
notation. The operator precedes the two operands, +AB are prefix Polish Notation of sum.

When operators come after their operands the resulting expression is called the postfix polish notation, it
is also called reverse polish notation, the operator follows the two operands, AB + is called postfix or
reverse polish notation.

Rules for converting Infix notation to the postfix/prefix notation:

(1) The operation with highest precedence are converted first and then after a portion of the expression
has been converted to postfix.
(2) It is to be treated as single operand.
(3) We consider five Binary operation, such are (+) addition, subtraction (-), multiplication (*), division (/)
and exponentiation.
The first four are available in C/C++, the fifth exponentiation will be represented by the operator S or T.
The value of expression A$B or A↑ B is A raise to B power, for example 3 ↑2=9.

(4) Take only two operands at a time to convert in a postfix from like A + B → AB +.

(5) Always, convert the parenthesis first.

(6) Convert postfix exponentiation second if there are more than one exponentiation in sequence then
take order from right to left.

(7) Convert in to postfix as multiplication and division operator, left to right.

(8) Convert in postfix as addition and subtraction left to right.

For example:
(1) Convert in to postfix

(A+B) *C infix form

= (AB +) *C convert addition first because it has parenthesis and parenthesis convert first.
= (AB +) C* convert the multiplication
=AB+C* Postfix form

(2) A+ (B*C) infix form/take first Parenthesis

=A+ (BC*) convert multiplication

= A (BC*)+ covert addition
=ABC*+ Postfix form

In above example, only rules to remember during the conversion process are that operates with highest
precedence are converted first.

◆Evaluating a postfix expression:

Algorithm: Postfix expression

Step 1: opndstk← empty stack

Step 2: [Scan the input string for reading one]

While (not end of input) repeat step 3
Symb←next input character

Step 3: [Check for operand]

if (symb is an operand)
then PUSH (opndstk, symb)
else
opnd2 POP (opndstk) [opnd1 and opnd2 are variables]
opnd1POP (opndstk)
value result of applying symb to opnd 1 & opnd 2
push (opndstk, value)

Step 4: POP (opndstk)

Step 5: [Finished]Exit
Each operator in a postfix string refers to the previous two operands in the string. Each time we read an
operand and we push it into stack. When we reach on operator, its operand will be the top two elements
on the stack. We can then pop these two element, perform the indicate operation on them, and push the
result on the stack. So that it will be available for use as an operand of the next operator.

Algorithm to convert infix expression into postfix polish notation:

Algorithm: [INFIX TO POSTFIX CONVERSION]

Step 1: define the opndstk as an empty stack

Step 2: Scan the infix string as an input string with one by one character reading method.
Step 3: While (not end of input string)
fetch one character from input (repeat) string and store it in to symb variable
check whether this symb is an operator or an operand.
if (symb is an operand)
then
PUSH that symb to postfix string post.
Else
if it is not operand
then check precendence of that fetch symb
if precedence is true
then
PUSH that symb to a postfix string do this step until the while condition can not failed

Step 4: now push the symb to opndstk

Step 5: Exit

(6) Recursive Functions:

Recursion is the name gives to a technique for defining a function in terms of call itself. It is define as, "a
function call itself”, thus chain of process occurs."

Example: The factorial function, can be recursively defined as,

Factorial (N)= 1 if N = 0
Factorial (N)= N FACTORIAL (N-1) , if N >0

Here, FACTORIAL (N) is defined in terms of FACTORIAL (N-1), which is again defined in terms of FACTORIAL
(N-2) and so on until the finally FACTORIAL (0) is reached, the value of FACORIAL (0) is defined as 1.
The value of a function for a particular argument value can be computed in a finite number of steps using
the recursive definition, where at each step of recursion we get never to the solution.

There are two important conditions that must be satisfied by any recursive procedure,

1. Each time a procedure calls itself, it must be "nearer", in some sense solution.

2. There must be a decision criterion for stopping the process or computation.

To find factorial value using Recursion.

The above analysis is performed in 'C' language as below,

#include<stdio.h>
#include<conio.h>
int fact(int);
void main()
{
int i,n,a;
clrscr();
// int fact(int);
printf("enter value of n:");
scanf("%d",&n);
a=fact(n);
printf("\n factorial of given number: %d",a);
getch();
}
int fact(int x)
{
int f=1;
if(x==0)

return(f);
else
f=x*fact(x-1);
return(f);
}
OUTPUT:

enter value of n: 5
factorial of given number: 120

*To Generate the Fibonacci number using recursion.

A Fibonacci series is,

0 1 1 2 3 5 8 13 …..N

If we consider F0= 0 and F1 = 1, then

F2= F1+F0=1+0= 1, similar F3 =F2 +F1 = 1 + 1 = 2, and so on, thus it is clear that each succeeding term is the
sum of two preceding terms, doing this procedure until i becomes less then the value of n.

#include<stdio.h>
void printFibonacci(int n)
{
static int n1=0,n2=1,n3;
if(n>0)
{
n3 = n1 + n2;
 n1 = n2;
n2 = n3;
printf("%d ",n3);
printFibonacci(n-1);
}
}
int main()
{
int n;
printf("Enter the number of elements: ");
scanf("%d",&n);
printf("Fibonacci Series: ");
printf("%d %d ",0,1);
printFibonacci(n-2);//n-2 because 2 numbers are already printed
return 0;
}

Output:

Enter the number of elements:15

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Greatest Common Divisor:

We have to express the greatest common divisor (GCD) function in a recursive form using following steps:

1. if m<<=n and n%m= 0 then ged(n,m) = m (termination step).

2. if n <m then ged(n,m)= gcd(m,n) (recursive definition of greatest common divisor).
3. if n >= m then gcd(n,m) = gcd(m, nm) (recursive definition of greatest common divisor)
Using these 3 rules, the recursive program of greatest common divisor can be written as below,

#include <stdio.h>
main()
{
int n, m, divisor;
printf("Enter the two numbers: ");
scanf("%d %d",&n,&m);
divisor=gcd(n,m);
printf("The Greatest Common factor of %d and %d is %d",n,m,divisor);
return 0;
}
gcd(int n,int m)
{
if(m<=n&& n % m==0)

return m;
if(n<m)

return gcd(m,n);

else

return gcd(m,n%m);

What is Queue?
In computer science a queue is a data structure that is similar to a stack, except that in a queue to first item
inserted is the first to be removed (FIFO).
In stack, the last item is the fir to be removed (LIFO).
A queue works like the Line at the movies, the first person in a queue get their tickets and left out, and new
person are added at end of a queue, the first person position at ticket window is front end and a last
person in queue position is rear end .
So from this example, In a queue always addition occurs at rear end and deletion at front end.
Elements :

Queue: "A data structure in which elements are added to one end (rear) and removed from the other
end (front) in FIFO (first in first out) structure."
(1) Array - Representation of Queue:
A queue has two pointer, front pointer and rear pointer, which are pointing to front and rear element of
the queue.
Deletion :
(2) Operations on Queue:
(a) PUSH
(b) POP
Consider a queue consist of N elements and an element values, which we can insert and delete value from
the queue.
The value Null (=-1) of front pointer indicate that queue is empty, so we can not perform delete operation.
If rear pointer value is increase, which is greater than N (no of elements), rear >= N indicates queue is Full,
So we can not perform insertion operation.
Now we see that, how to insert & delete a value from the queue and see the position of front pointer and
rear pointer.

When we delete or remove the element value from a queue a front pointer value is increment by one,
front front+1.
(ii) Insert a one element in a queue:
When we insert an element at rear end in a queue, a rear pointer value is increment by one, rear = rear +1
(3) Static Implementation of Queues :
There are two basic operations for queues are, insertion (PUSH) and delete (POP).
For writing algorithm, we can define following variables,
S → It is the array having N element
rear → It is the pointer which will points to Last (rear) end of queue.
front→ It is the pointer which will points to first (front) end of queue
..X→ It is the variable which will store the value/item that we want to or from push or pop on queue.
(1) PUSH (Insertion):
In push operation if we push or insert an element in a queue at rear end, rear pointer value increment by
one,
Algorithm: PUSH (S,front,rear,x)
Step 1: [Check for Queue 'Over flow]
if rear >= size
then
write ("Queue is over flow")
Exit
Step 2: [Increment Rear Pointer]
rear  rear + 1
Step 3: [Insert an element at rear of Queue]
S [rear]  x
Step 4: [Set the front pointer]
if front = - 1 then
front  0
Step 5: [Finished]
Exit
The first step of algorithm is to check the overflow condition, if queue is already full means rear >=N
(size),and if we want to insert an element in Queue, it will indicate an overflow errors.
In second step if Queue is not full, we can insert an element in Queue, so rear pointer value .is increment
by one
The third step perform the value of variable x put on to the rear element (Last element) of a queue
(2) POP (Deletion):
In pop operation, if we delete or pop a element in queue at front end, front pointer value increment by
one
Algorithm: POP (S,front,rear,x)
Step 1: [Check for Queue "Under flow']
If( front=-1 OR front = 0)
then
write ("Queue is under flow")
Exit
Step 2: [Remove an element from Queue]
XS [front]
Step 3: [Print the popped element]
Write ("X")
Step 4 : [Check for empty queue]
if front = rear
then
front 0
rear  0
else
front front + 1
Step 5: [Finished]
Exit
The first step in a algorithm is to check the under flow condition, if queue is empty (front=-1) and if we
want to delete an element from a queue, it will indicate an 'under flow' errors.
In fourth step if queue is not empty and we want to delete and element from a queue, so front pointer
value will increment by one.
Implementation of queue By Reservation System.
Simulate the operations of reservation window queue of 5 people using simple queue.

#include<stdio.h>
#include<conio.h>
void main()
{
int FRONT=-1,REAR=-1,q[5],n,ch,x,i;
clrscr();
printf("TAKE ONLY 5 RESERVATION:");
scanf("%d",&n);
do
{
printf("\n1. TAKE RESERVATION ");
printf("\n2. CANCLE RESERVATION");
printf("\n3. DISPLAY RESERVED SEAT");
printf("\n4. EXIT");
printf("\n ENTER YOUR CHOICE::");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(REAR>=n)
{
printf("\n RESERVATION FULL:");

}
else
{

printf("GET THE RESERVATION==>");

scanf("%d",&x);
REAR=REAR+1;
q[REAR]=x;
}
if(FRONT==-1)
{
FRONT=FRONT+1;
}
break;
case 2:
if(FRONT==-1)
{
printf("\n RESERVATION IS EMPTY :");
}
else
{
x=q[FRONT];
printf("\n CANCLE RESERVED SEAT IS::");
}
if(FRONT==REAR)
{
FRONT=-1;
REAR=-1;
}
else
{
FRONT=FRONT+1;
}
break;

case 3:
if(FRONT==-1)
{
printf("\n RESERVATION IS EMPTY :");
}
else
{
for(i=REAR;i>=FRONT;i--)
 {
printf("\n RESERVED SEAT AT q[%d]is %d",i,q[i]);

}
}
break;
case 4:
default:
printf("\n INVALID CHOICE");
break;
}
}
while(ch!=4);
getch();
}

Application of Queue:
(1) Queue is widely used in simulation work.
(2) In Mailbox application when we save the message to communicate between two users or processes in a
system is work according to queue.
(3) A computer processor or NIC card also maintain buffers in the form of queue for incoming resources
requests.
(4) In operating system, process scheduling or disk scheduling algorithms uses queue concept.

CIRCULAR QUEUE:
A circular queue overcomes the problem of unutilized space in linear queues implemented as arrays. A
circular queue also has a Front and Rear to keep the track of the elements to be deleted and inserted and
therefore to maintain the unique characteristic of the queue.

The below assumptions are made :

1. Front will always be pointing to the first element (as in the linear queue).
2. If Front Rear the queue will be empty.
3. Each time a new element is inserted into the queue the Rear is incremented by one.
Rear Rear + 1
4. Each time an element is deleted from the queue the value of Front is incremented by one.
Front Front + 1

Insertion:
Consider the circular queue shown above, the insertion in this queue will be same as with linear queue, we
only have to keep track of Front and Rear with some extra logic.

A Circular Queue is shown in the figure 6.6(a).

If more elements are added to the queue, it looks like shown in figure 6.6(b).
Now the queue will be full. If we now try to add another element to the queue, as the new element is
inserted from the Rear end, the position of the element to be inserted will be calculated by the relation:
Rear = (Rear + 1) % MAXSIZE
Queue [Rear] = value
For the current queue (Fig 6.6(b)) the value of Rear is 4, and value of MAXSIZE is 5hence
Rear- (Rear + 1) % MAXSIZE
Rear = (4 + 1) % 5
= 0.
Note that Front is also pointing to Q[0] (Front = 0) and Rear also comes out to be 0 (i.e, Rear is also pointing
to Q[0]). Since Rear = Front, the Queue Overflow condition is satisfied, and our trial to add new element
will flash the message "Queue Overflow" which avoids us to add new element.
Considering the Fig 6.6(c). Consider the situation when we add an element to the queue. The Rear is
calculated as below:
Rear =(Rear + 1) % 5
Rear =(4+1) % 5 = 0.
The new element will be added to Q[Rear] or Q[0] location of the array and Rear is increased by one (i.e,
Rear Rear +1-0+1) The next element will be added to location Q[1] of the array.
Deletion:
The deletion method for a circular queue also requires some modification as compared to linear queues.

The deletion is explained in Fig 6.7. In the Fig 6.7 the queue is full .Now if we delete one element from the
queue, it will be deleted from the Front end.
After deleting the front element, the front should be modified according to position of Front, i.e., if Front
indicates to the last element of the circular queue then after deleting that element the Front should be
again reset to 0 (Front =0) Otherwise after every deletion the new position which Front should indicate will
be as :
Front (Front + 1) % MAXSIZE

(QINSERT (Queue [MAXSIZE], Item)

Algorithm for adding an element in a circular queue
1. If (Front == (Rear + 1) % MAXSIZE) .
write Queue Overflow and Exit
Else :Take the value
If (Front == -1)
Set Front = Rear = 0
else
Rear= ((Rear + 1) % MAXSIZE)
[Assign value] Queue [Rear] = value.
[End if]

(QDELETE (Queue [MAXSIZE], Item)

Algorithm for deleting an element in a circular queue
1. If (Front = -1)
Write Queue underflow and Exit.
else Item = Queue [Front]
 if (Front == Rear)
Set Front = -1
Set Rear = -1
Else: Front = (Front + 1) % MAXSIZE
[End If Structure]
2. Exit.
CIRCULAR QUEUE TRACING:
DOUBLE ENDED QUEUES (DEQUE):
It is also a homogeneous list of elements in which insertion and deletion operations are performed from
both the ends, i.e., we can insert elements from the rear end or from the front ends. Hence it is called
double-ended queue.
It is commonly referred to as deque
There are two types of deques. These two types are due to the restrictions put to perform either the
insertions or deletions only at one end. They are,
1. Input-restricted deque.
2. Output-restricted deque.
Ffigure shows a deque of 5 elements.

Since both insertion and deletion are performed from either end, it is necessary to design an algorithm to
perform the following four operations:
1. Insertion of an element at the REAR end of the queue.
2. Deletion of an element from the FRONT end of the queue.
3. Insertion of an element at the FRONT end of the queue.
4. Deletion of an element from the REAR end of the queue.

PRIORITY QUEUES :
A priority queue is a collection of elements such that each element has been assigned a priority and 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 priority is processed first, and programs with the same priority form a standard Queue.
There can be two types of implementations of priority queue:
(i) Ascending Priority Queue
(ii) Descending Priority Queue
A collection of items into which items can be inserted arbitrarily and from which only the smallest item can
be removed is called Ascending Priority Queue.
In Descending Priority Queue only the largest item is deleted. The elements of priority Queue need not be
numbers or characters that can be composed directly.
 They may be complex structures that are ordered by one or several fields. Sometimes the field on which
the element of a priority queue is ordered is not even past of the elements themselves.
The priority queue is a data structure in which intrinsic ordering of the elements determines the result of
its basic operations.
An ascending priority queue is a collection of items into which items can be inserted arbitrarily and from
which only the smallest item can be removed. On the other hand a descending priority queue allows only
the largest item to be removed.
Insertion. The insertion in Priority queues is the same as in non-priority queues.
Deletion. Deletion requires a search for the element of highest priority and deletes the element with
highest priority. The following methods can be used for deletion/removal from a given Priority Queue:
1. An empty indicator replaces deleted elements.
2. After each deletion elements can be moved up in the array decrementing the rear.
3. The array in the queue can be maintained as an ordered circular array 3.