UNIT II

LINEAR DATA STRUCTURES – STACKS, QUEUES

Stack ADT – Evaluating arithmetic expressions- other applications- Queue ADT – circular
queueImplementation – Double ended Queues – applications of queues

PART A
1. Define Stack
A Stack is an ordered list in which all insertions (Push operation) and deletion (Pop
operation) are made at one end, called the top. The topmost element is pointed by top. The top is
initialized to -1 when the stack is created that is when the stack is empty. In a stack S = (a1,an),
a1 is the bottom most element and element a is on top of element ai-1. Stack is also referred as
Last in First out (LIFO) list.

2. What are the various Operations performed on the Stack?

The various operations that are performed on the stack are

CREATE(S) – Creates S as an empty stack.

PUSH(S,X) – Adds the element X to the top of the stack.

POP(S) – Deletes the top most elements from the stack.

TOP(S) – returns the value of top element from the stack.

ISEMTPTY(S) – returns true if Stack is empty else false.

ISFULL(S) - returns true if Stack is full else false.

3.Write the postfix form for the expression -A+B-C+D?

A-B+C-D+
4.What are the postfix and prefix forms of the expression?

A+B*(C-D)/(P-R)

Postfix form: ABCD-*PR-/+

Prefix form: +A/*B-CD-PR

5.Explain the usage of stack in recursive algorithm implementation?

In recursive algorithms, stack data structures is used to store the return address when a
recursive call is encountered and also to store the values of all the parameters essential to the
current state of the function.
 6.Define Queue.

A Queue is an ordered list in which all insertions take place at one end called the rear, while
all deletions take place at the other end called the front. Rear is initialized to -1 and front is
initialized to 0. Queue is also referred as First In First Out (FIFO) list.

7.What are the various operations performed on the Queue?

The various operations performed on the queue are

CREATE(Q) – Creates Q as an empty Queue.
Enqueue(Q,X) – Adds the element X to the Queue.
Dequeue(Q) – Deletes a element from the Queue.
ISEMTPTY(Q) – returns true if Queue is empty else false.
ISFULL(Q) - returns true if Queue is full else false.

8.How do you test for an empty Queue?

The condition for testing an empty queue is rear=front-1. In linked list implementation of
queue the condition for an empty queue is the header node link field is NULL.

9.Write down the function to insert an element into a queue, in which the queue is
implemented as an array.
Q - Queue
X - element to added to the queue Q
IsFull(Q) - Checks and true if Queue Q is full
Q->Size - Number of elements in the queue Q
Q->Rear –Points to last element of the queue Q
Q->Array - array used to store queue elements

Void enqueue (int X, Queue Q) {

If (IsFull(Q))
Error (“Full queue”);
else
{
Q->Size++;
Q->Rear = Q->Rear+1; Q->Array[ Q>Rear ]=X;
}}

10. Define Dequeue.

Deque stands for Double ended queue. It is a linear list in which insertions and deletion are made from
either end of the queue structure.

11.Define Circular Queue.

Another representation of a queue, which prevents an excessive use of memory by arranging
elements/ nodes Q1,Q2,…Qn in a circular fashion. That is, it is the queue, which wraps around upon reaching
the end of the queue
 12. List any four applications of stack.
 Parsing context free languages
 Evaluating arithmetic expressions
 Function call
 Traversing trees and graph
 Tower of Hanoi

PART B

1. Explain how stack is implemented in array?

Stack

Stack is abstract data type and linear data structure.

Concept of Stack

A Stack is data structure in which addition of new element or deletion of existing element always takes
place at a same end. This end is known as the top of the stack. That means that it is possible to remove
elements from a stack in reverse order from the insertion of elements into the stack.

One other way of describing the stack is as a last in, first out (LIFO) abstract data type and linear data structure.

Operations on Stack

The stack is basically performed two operations PUSH and POP. Push and pop are the operations that
are provided for insertion of an element into the stack and the removal of an element from the stack,
respectively.

PUSH: - PUSH operation performed for the adding item to the stack.

POP: - POP operation performed for removing an item from a stack.

Types of Implementation in Stack

1. Static Implementation (Array implementation of Stack)

2. Dynamic Implementation (Lined List Implementation of Stack)

Static Implementation of StackRoutine to push an element onto the stack

void push(int X,stack S)
{
if(Top==Arraysize-1)
Error(“Stack is full. Insertion is not possible”);
Else {
Top=Top+1; S[Top]=X;
}}
Routine to check whether a stack is full
int Isfull(Stack S)
{
if(Top==Arraysize-1)

return(1);
}

Routine to check whether stack is empty

int Isempty(Stack S)
{
if(Top==-1)

return(1);
}

pop routine
void pop(Stack S)
{
if(Top==-1)
Errro(“Empty stack! Deletion not possible”);
else
{
X=s[Top];Top=Top-1;

}
}
Routine to return top Element of the stack
int TopElement(Stack S)
{
if(Top==-1)
{
Error(“Empty stack!!No elements”);return 0;
}
else
return S[Top];
}
 2. Explain how stack is implemented using Linked list?

Linked list implementation of Stack

Routine to check whether the stack is empty

int Isempty(Stack S)
{
if(S->next==NULL) EMPTY STACK
return(1);
}
push routine /*Inserts element at front of the list

header

20 10 N
push routine /*Inserts element at front of the list

void push(int x, Stack S)

{
Position newnode,Top; newnode=malloc(sizeof(Struct node));newnode->data=X;
newnode->next=Top;
S->next=newnode;
Top=newnode;
}
pop routine /*Deletes the element at front of list
void pop(Stack S)
{
Position temp,Top;
Top=S->next;
if(S->next==NULL)
Error(“empty stack! Pop not possible”);
else
{
temp=Top;
S->next=Top->next;free(temp);
Top=s->next;

}
}
 temp

40 20 10 N

30

TOP

HEADER

TOP

Return Top Element

int Topelement(Stack S)
{
if(S->next==NULL)
{
error(“Stack is empty”);return 0;
else
return S->next->data;
}
 3. 'C' Implementation of stack using array
/* static implementation of stack*/
#include<stdio.h>
#include<conio.h>
#define size 5
int stack[size]; int top;
void push()
{
int n;
printf("\n Enter item in stack");scanf("%d",&n);
if(top==size-1)
{
printf("\nStack is Full");
}
else
{
top=top+1; stack[top]=n;

}
}
void pop()
{
int item; if(top==-1)
{
printf("\n Stack is empty");
}
else
{
item=stack[top];
printf("\n item popped is=%d", item);top--;

}
}
void display()
{
int i;
printf("\n item in stack are");for(i=top; i>=0; i--)
printf("\n %d", stack[i]);
}
void main()
{
char ch,ch1;
ch ='y';
ch1='y';top=-1;clrscr();
while(ch!='n')
{
push();
printf("\n Do you want to push any item in stack y/n");ch=getch();
}
display(); while(ch1!='n')
{
printf("\n Do you want to delete any item in stack y/n");ch1=getch();
pop();
}
display();getch();
}
 4. 'C' Implementation of stack using Linked list

/* Dynamic implementation of stack*/

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
int item;
struct node *next;
};
struct node *top;void push()
{
int n;
struct node *nw;
nw=(struct node*)malloc(sizeof(struct node));
printf("\n Enter item in stack:");
scanf("%d",&n);
nw->item=n;
nw->next=0;
if(top==0)
{
top=nw;
}
else
{
nw->next=top; top=nw;

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

Output
 5. Write an algorithm to evaluate a postfix expression and explain it with example

Algorithm for Infix to Postfix Conversion

1. scan infix expression from left to right
2. if an operand is encountered add to P
3. if an operator is found
i) repeatedly pop the operator from stack which are having higher precedence than the operator found
ii) add the new operator to stack
4. if a right parenthesis found
i) repeatedly pop the stack and add the poped operators to the expression until a left parenthesis is
found.
ii) remove the left parenthesis
5. stop

Example: The Given Infix expression is ((A+B)/ C)

Symbols Scanned Stack Postfix form P

( (

( ((

A (( A

+ ((+ A

B ((+ AB

) (( AB+

/ (( / AB+

C (( / AB+C

) (( AB+C/
 6. Explain function calls in detail?
FUNCTION CALLS

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

Main() Push()
Balance()

Call
balance()
Call push()

RECURSIVE FUNCTION TO FIND FACTORIAL

Int fact(int n)

int S;

if(n==1)

return(1);

else

S=n*fact(n-1);

return(S)

}
 7. Write an algorithm to balance the symbols?

BALANCING THE SYMBOLS

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

Read one character at a time until it encounters the delimiter `#'.

Step 1: - If the character is an opening symbol, push it onto the stack.
Step 2: - If the character is a closing symbol, and if the stack is empty report an error as missing opening
symbol.
Step 3: - If it is a closing symbol and if it has corresponding opening symbol in the stack, POPit from the stack.
Otherwise, report an error as mismatched symbols.
Step 4: - At the end of file, if the stack is not empty, report an error as Missing closing symbol. Otherwise,
report as balanced symbols.
 8. Develop an algorithm to implement Queue ADT. Give relevant examples and diagrammatic
representations?
Queue

Queue is a kind of abstract data type where items are inserted one end (rear end) known as enqueue
operation and deleted from the other end (front end) known as dequeue operation. This makes the queue a
First-In-First-Out (FIFO) data structure. The queue performs the function of a buffer.

Implementation of Queue

1. Implementation using Array (Static Queue)

2. Implementation using Linked List (Dynamic Queue)

Operation on Queues

Operation Description

initialize() Initializes a queue by adding the value of rear and font to -1.

enqueue() Insert an element at the rear end of the queue.

dequeue() Deletes the front element and return the same.

empty() It returns true(1) if the queue is empty and return false(0) if the queue is not empty.

full() It returns true(1) if the queue is full and return false(0) if the queue is not full.
Operation on queue - Array

0 1 2 3 4 5 6 Max = 7

Rear = -1
Front = -1

0 1 2 3 4 5 6
7

Rear = Front = 0
After Insertion

0 1 2 3 4 5 6
7 8 9 10 11

Front = 0 Rear = 4

After Insertion 0 1 2 3 4 5 6

10
Front = 3 Rear=3
After Deletion

0 1 2 3 4 5 6
10 11 12

After Insertion
Front = 0 Rear = 5
ROUTINE TO INSERT AN ELEMENT IN A QUEUE

void Enqueue (int X)

{
if (rear == max _ Arraysize-1)
print (" Queue overflow");
else
{
Rear = Rear + 1;
Queue [Rear] = X;
}
}

ROUTINE FOR DEQUEUE

void delete ( )
{
if (Front < 0)
print (" Queue Underflow");
else
{
X = Queue [Front];
if (Front = = Rear)
{
Front = 0;
Rear = -1;
}
else
Front = Front + 1 ;
}}
Application of queues

Queues are mostly used in operating systems.

 Waiting for a particular event to occur.

 Scheduling of processes.

9. IMPLEMENTATION OF QUEUE USING LINKED LIST

Enqueue operation is performed at the end of the list and Dequeue operation is performedat the front of the list.

QUEUE ADT

10 20 NULL

DECLARATION FOR LINKED LIST IMPLEMENTATION OF QUEUE ADT

Struct Node;
typedef Struct Node * Queue;
int IsEmpty (Queue Q);
Queue CreateQueue (void);
void MakeEmpty (Queue Q);
void Enqueue (int X, Queue Q);
void Dequeue (Queue Q);
Struct Node
{
int Element;
Struct Node *Next;
}* Front = NULL, *Rear = NULL;
Routine to check whether queue is empty
int IsEmpty (Queue Q) // returns boolean value /

{ // if Q is empty

if (QNext = = NULL) // else returns 0

return (1);

ROUTINE TO CHECK AN EMPTY QUEUE

Struct CreateQueue ( )
{
Queue Q;
Q = Malloc (Sizeof (Struct Node));
if (Q = = NULL)
Error ("Out of Space");
MakeEmpty (Q);
return Q;
}
void MakeEmpty (Queue Q)
{
if (Q = = NULL)
Error ("Create Queue First");

else
while (! IsEmpty (Q)
Dequeue (Q);
i)

10 20 NULL

Dequeue

ii) 20 NULL

iii)

Empty Queue

ROUTINE TO ENQUEUE AN ELEMENT IN QUEUE

void Enqueue (int X)

{
Struct node *newnode;
newnode = Malloc (sizeof (Struct node));
if (Rear = = NULL)
{
newnode data = X;
newnodeNext = NULL;
Front = newnode;
Rear = newnode;
}
else
{
newnode data = X;
newnode Next = NULL;
Rear next = newnode;
Rear = newnode;
}}
ROUTINE TO DEQUEUE AN ELEMENT FROM THE QUEUE
void Dequeue ( )
{
Struct node *temp;
if (Front = = NULL)
Error("Queue is underflow");
else
{
temp = Front;
if (Front = = Rear)
{
Front = NULL;
Rear = NULL;
}
else
Front = Front Next;
Print (tempdata);
free (temp);
}
}

Example: ENQUEUE 83, 9, 27, 10

Example: DEQUEUE

10 1000 20 3000 30 NULL

Front Rear

Assign the front element as temp and frontnext as front to delete the temp data.

20 3000 30 NULL

Front Rear

Assign the front element as temp and frontnext as front to delete the temp data.
30 NULL

Front Rear

If front and rear are equal assign to null and delete the corresponding front elementFront=rear=NULL
 10. Explain how the circular queue and priority is represented?
Circular Queue

Circular queue is an abstract data type that contains a collection of data which allows addition of data at
the end of the queue and removal of data at the beginning of the queue. Circular queueshave a fixed size.

Circular queue follows FIFO principle. Queue items are added at the rear end and the items aredeleted
at front end of the circular queue.

Enqueue Routine in Circular List

Void CEnqueue (int X,Circularqueue CQ)

{
if(Front==(rear+1)%Arraysize)
Error(“Queue is full!!Queue overflow”);else if(front== -1)
{
front=front+1;rear=rear+1; CQ[rear]=x;
}
else
{
rear=(rear+1)%Arraysize;CQ[rear]=X;
}
}
Empty Queue F = -1
R = -1

DEQUEUE ROUTINE IN CIRCULAR LIST

void dequeue (circularqueue CQ)

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

F= -1 R= -1 Empty Queue

Routine for display

void display(circularqueue CQ , int i , int j)

{
if(front==0&&rear==-1)
{
print("Queue is underflow”);exit();
}
if(front>rear)
{
for(i=0;i<=rear;i++)
return CQ[i];
for(j=front;j<=max-1;j++)return CQ[j];
return CQ[rear]; return CQ[front];
}
else
{
for(i=front;i<=rear;i++)
{
return CQ[i];
}
return Q[rear];
return Q[front];
}