DATA STRUCTURE USING C++ BCA 313 UNIT II

DATA STRUCTURE USING C++

BCA 313

Unit II Syllabus
Stack: Array Representation and Implementation of stack, Operations on Stack: Push & Pop,
Linked Representation of Stack and Operations Associated with Stack, Applications of stack:
Conversion of Infix to Prefix and Postfix Expressions, Evaluation of postfix expression using
Stack. Queue: Array and linked representation and implementation of queues, Operations on
Queue: Create, Add, Delete, and Circular queue.

STACK
A Stack is a Linear Data Structure. It is an ordered list in which addition of new data
item and deletion of already existing data item is done from only one end, known as top of
the stack(TOS). As all the deletion and insertion in a Stack is done from the top of the Stack,
the last added element will be the first to be removed from the stack. So that stack is also
called Last In First Out (LIFO) list.

For example

Operation On the Stack :

The basic operation can be performed on stack are as follows :

1|Page
 DATA STRUCTURE USING C++ BCA 313 UNIT II

1. PUSH Operation

The process of adding a new element to the top of the stack is called PUSH
Operation, after PUSH operation the top is incremented by one. In case the stack is
full and no new element can be inserted It is called Stack full condition. This
condition is called Stack Overflow.

2. POP Operation

The process of removing an element from the top of the stack is called POP operation,
after every POP operation the top is decremented by ONE. If there is no element on
the stack and POP operation is performed then this will Result into Stack Underflow.

ARRAY REPRESENTATION OF STACKS

Stacks will be maintained by a linear array STACK; a pointer variable TOP, which contains
the location of the top element of the stack; and a variable MAXSTK which gives the
maximum number of elements that can be held by the stack. The condition TOP=0 or
TOP=NULL will indicate that the stack is empty.

Figure shows an array representation of a stack. Since TOP=3, the stacks has three elements,
XXX, YYY and ZZZ; and since MAXSTK=8, there is room for 5 more items in the stack.

Algorithm for PUSH Operation :

Procedure : PUSH(STACK, TOP, MAXSTK, ITEM)

This procedure pushes an ITEM onto a stack.
1. [Stack already filled?]
If TOP=MAXSTK, then: Print: OVERFLOW, and Return.
2. Set TOP:=TOP + 1 [Increases TOP by 1.]
3. Set STACK[TOP] := ITEM. [Inserts ITEM in new TOP position.]
4. Return.

Algorithm for POP Operation :

Procedure : POP(STACK, TOP, ITEM)

This procedure deletes the top element of STACK and assigns it to the variable ITEM.
1. [Stack has an item to be removed?]

2|Page
 DATA STRUCTURE USING C++ BCA 313 UNIT II

If (TOP = 0), then: Print: UNDERFLOW, and Return.

2. Set ITEM := STACK[TOP]. [Assigns TOP element to ITEM.]
3. Set TOP := TOP-1. [Decreases TOP by 1]
4. Return.

STACK IMPLEMENTATION USING ARRAY

#include<iostream>
#define maxsize 5
using namespace std;
void push();
void pop();
void display();
int stack[maxsize],top=-1;
int main()
{
int choice;
while(1)
{
cout<<"\n 1. PUSH";
cout<<"\n 2. POP";
cout<<"\n 3. DISPLAY";
cout<<"\n 0. EXIT";
cout<<"\n\n\t\tENTER YOUR CHOICE : ";
cin>>choice;
switch(choice)
{
case 1:
push();
display();
break;
case 2:
pop();
display();
break;
case 3:
display();
break;
case 0:
exit(0);
default:
cout<<"\n\n\t\tYOU ENTERED WRONG CHOICE";
}
}
return 0;
}
void push()
{
int item;
if(top==maxsize-1)

3|Page
 DATA STRUCTURE USING C++ BCA 313 UNIT II

{
cout<<"\n\n\t\tTHE STACK IS FULL";
return;
}
else
{
cout<<"\n\n\t\tENTER THE ELEMENT TO BE INSERTED : ";
cin>>item;
top=top+1;
stack[top]=item;
}
}
void pop()
{
int item;
if(top==-1)
{
cout<<"\n\n\t\tTHE STACK IS EMPTY";
return;
}
else
{
item=stack[top];
top=top-1;
cout<<"\n\n\t\tTHE DELETED ITEM IS "<<item;
}
}
void display()
{
int i;
if(top==-1)
{
cout<<"\n\n\t\tTHE STACK DOES NOT CONTAIN ANY ELEMENT";
return;
}
else
{
cout<<"\n\n\t\tTHE STACK IS \n";
for(i=top;i>=0;i--)
{
cout<<"\n\t\t"<<stack[i];
}
}
}
POLISH NOTATION

The process of writing the operator of an expression either before their operands or after
them is called the Polish Notation. The fundamental property of the polish notation is that
the order in which the operation are to be performed is completely determined by the position

4|Page
 DATA STRUCTURE USING C++ BCA 313 UNIT II

of the operators and operands in the expression. We does not need have parenthesis when
writing expression in the polish notation.

The polish notation can be classified into three categories :

1. Infix
When the operator exist between two operands then the expression is called infix
expression. Ex. a + b * c
2. Prefix
When the Operators are written before their operands then the resulting expression is
called the prefix polish notation. Ex. + a * b c
3. Postfix
When the operators com e after their operands the resulting expression is called
Reverse Polish Notation or postfix polish notation. Ex. abc*+

We have five basic operator s with three levels of precedence

Highest : Exponentiation ( or ^)

Next Highest : Multiplication (*) and Division (/)

Lowest : Addition (+) and Subtraction (-)

We also assume that in any parenthesis free expression, The operation on same level are
performed from left to right. Ex. a+b-c

Transforming Infix Expressions into Postfix Expressions

Algorithm POLISH(Q,P)
Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent
postfix expression P
1. Push "(" onto STACK, and add ")" to the end of Q.
2. Scan Q from left to right and repeat Steps 3 to 6 for each element of Q until the STACK is empty
3. If an operand is encountered, add it to P.
4. If a left parenthesis is encountered, push it onto STACK.
5. If an operator (x) is encountered, then:
a) Repeatedly pop from STACK and add to P each operator (on the top of STACK)
which has the same precedence as or higher precedence than (x)
b) Add (x) to STACK.
[End of If structure.]
6. If a right parenthesis is encountered, then:
a) Repeatedly pop from STACK and add to P each operator (on top of STACK) until
a left parenthesis is encountered.
b) Remove the left parenthesis. [Do not add the left parenthesis to P.]
[End of If structure.]
[End of Step 2 loop.]
7. Exit.

Example
Let we see the example. Consider the following arithmetic infix expression
Q: A + (B * C - (D / E ↑ F) * G) * H

5|Page
 DATA STRUCTURE USING C++ BCA 313 UNIT II

We transform Q using algorithm above into its equivalent postfix expression P. First we
push "(" onto STACK, and then we add ")" to the end of Q to obtain:
Q: A + ( B * C - ( D / E ↑ F ) * G ) * H )
We may observe that the Figure shows the status of STACK and of the string P as each
element of Q is scanned.

Evaluation of a Postfix Expression

Suppose P is an arithmetic expression written in postfix notation. The following algorithm
uses a STACK to hold operands, evaluates P

Algorithm : This algorithm finds the VALUE of an arithmetic expression P written in postfix
notation.
1. Add a right parenthesis ")"at the end of P. [This acts as a sentinel].
2. Scan P from left to right and repeat Steps 3 and 4 for each element of until the sentinel
")" is encountered.
3. If an operand is encountered, put it on STACK.
4. If an operator (x) is encountered, then:
a) Remove the two top elements of STACK, where A is the top
element and B is the next-to-top element.
b) Evaluate B (x) A.
c) Place the result of (b) back on STACK
[End of If structure.]
[End of Step 2 loop.]
5. Set VALUE equal to the top element on STACK.

6|Page
 DATA STRUCTURE USING C++ BCA 313 UNIT II

6. Exit.

Example

Consider the following arithmetic expression P written in postfix notation:

P: 5, 6, 2, +, *, 12, 4, /, -
(Commas are used to separate the elements of P so that 5, 6, 2 is not interpreted as the
number 562.) The equivalent infix expression Q follows:
Q: 5 * (6 + 2) - 12 / 4
We evaluate P using algorithm. First we add a sentinel right parenthesis at the end of P to
obtain
P : 5, 6, 2, +, *, 12, 4, /, -, )
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
Figure shows the contents of STACK as each element of P is scanned. The final number in
STACK, 37, which is assigned to VALUE when the sentinel “)” is scanned, is the value of P.

QUEUE

A queue is a linear structure in which element may be inserted at one end called the rear, and
the deleted at the other end called the front. In Figure pictures of a queue of people waiting at
a bus stop. Queues are also called first-in first-out (FIFO) lists. An important example of a
queue in computer science occurs in a timesharing system, in which programs with the same
priority form a queue while waiting to be executed. Similar to stack operations, operations
that are define a queue.

7|Page
 DATA STRUCTURE USING C++ BCA 313 UNIT II

REPRESENTATION OF QUEUES
Queues may be represented in the computer in various ways, usually by means of 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; and REAR,
containing the location of the rear element of the queue. The condition FRONT = NULL will
indicate that the queue is empty.
Figure, indicates the way elements will be deleted from the queue and the way new elements
will be added to the queue.

Array Representation of a Queue

Observe that whenever an element is deleted from the queue, the value of FRONT is
increased by 1; this can be implemented by the assignment

FRONT := FRONT + 1

Similarly, whenever an element is added to the queue, the value of REAR is increased by 1;
this can be implemented by the assignment

REAR := REAR + 1

8|Page
 DATA STRUCTURE USING C++ BCA 313 UNIT II

Assume QUEUE is circular, that is, that QUEUE[1] comes after QUEUE[N] in the array.
With this assumption, we insert ITEM into the queue by assigning ITEM to QUEUE[1].
Specifically, instead of increasing REAR to N+1, we reset REAR=1 and then assign,

QUEUE[REAR]:= ITEM

Similarly, if FRONT=N and an element of QUEUE is deleted, we reset FRONT=1 instead of

increasing FRONT to N+1. Suppose that our queue contains only one element, i.e., suppose
that
FRONT = REAR = NULL

and suppose that the element is deleted. Then we assign FRONT: = NULL and REAR:= NULL
to indicate that the queue is empty. The operation of adding an item onto a stack and the
operation of removing (popping) and item from a stack are implemented by the following
procedures, called QINSERT and QDELET respectively.

ALGORITHM FOR SIMPLE QUEUE INSERT

Algorithm : INSERT (QUEUE, N, FRONT, REAR, ITEM)

This procedure inserts an element ITEM into a queue.
1. [Queue already filled?]
If REAR = N, then:
Write: OVERFLOW, and Return.
2. [Find new value of REAR.]
If FRONT = NULL, then: [Queue initially empty.]
Set FRONT:=1 and REAR:=1.
Else:
Set REAR := REAR + 1.
[End of If structure.]
3. Set QUEUE[REAR] := ITEM. [This inserts new element.]
4. Return.

ALGORITHM FOR SIMPLE QUEUE DELETE

Algorithm : QDELETE (QUEUE, N, FRONT, REAR, ITEM)

This procedure deletes an element from a queue and assigns it to the variable item.
1. [Queue already empty?]
If FRONT := NULL, then: Write: UNDERFLOW, and Return.
2. Set ITEM := QUEUE[FRONT].
3. [Find new value of FRONT.]
If FRONT = REAR, then: [Queue has only one element to start.]
Set FRONT := NULL and REAR := NULL.
Else:
Set FRONT := FRONT+1.
[End of If structure.]
4. Return

IMPLEMENTATION OF LINEAR QUEUE

#include<iostream>
#define maxsize 5
using namespace std;

9|Page
 DATA STRUCTURE USING C++ BCA 313 UNIT II

void insertq();
void deleteq();
void displayq();
int queue[maxsize],front=-1,rear=-1;
int main()
{
int choice;
while(1)
{
cout<<"\n 1. INSERT";
cout<<"\n 2. DELETE";
cout<<"\n 3. DISPLAY";
cout<<"\n 0. EXIT";
cout<<"\n\n\t\tENTER YOUR CHOICE : ";
cin>>choice;
switch(choice)
{
case 1:
insertq();
displayq();
break;
case 2:
deleteq();
displayq();
break;
case 3:
displayq();
break;
case 0:
exit(0);
default:
cout<<"\n\n\t\tYOU ENTERED WRONG CHOICE";
}
}
return 0;
}
void insertq()
{
int item;
if(rear==maxsize-1)
{
cout<<"\n\n\t\tTHE QUEUE IS FULL";
return;
}
else
{
cout<<"\n\n\t\tENTER THE ELEMENT TO BE INSERTED : ";
cin>>item;
if(front==-1)
{

10 | P a g e
 DATA STRUCTURE USING C++ BCA 313 UNIT II

front=0;
rear=0;
}
else
{
rear=rear+1;
}
queue[rear]=item;
}
}
void deleteq()
{
int item;
if(front==-1)
{
cout<<"\n\n\t\tTHE QUEUE IS EMPTY";
return;
}
else
{
item=queue[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
front=front+1;
}
cout<<"\n\n\t\tTHE DELETED ITEM IS "<<item;
}
}
void displayq()
{
int i;
if(front==-1)
{
cout<<"\n\n\t\tTHE QUEUE DOES NOT CONTAIN ANY ELEMENT";
return;
}
else
{
cout<<"\n\n\t\tTHE QUEUE IS \n";
for(i=front;i<=rear;i++)
{
cout<<"\n\t\t"<<queue[i];
}
}
}

11 | P a g e
 DATA STRUCTURE USING C++ BCA 313 UNIT II

CIRCULAR QUEUE :
A circular queue is one in which the insertion of a new element is done at the first
location of the queue if the last location of the queue is full. In other words if we have a
queue of n element then after inserting an element last location of the array the next
element will be inserted at first location of the array.

A circular queue overcomes the problem of unutilized space in the linear queue
implemented as array. A circular queue also has a FRONT and REAR to keep track of
the elements to be deleted and inserted.

ALGORITHM FOR CIRCULAR QUEUE INSERT

Algorithm : INSERT (QUEUE, N, FRONT, REAR, ITEM)

This procedure inserts an element ITEM into a queue.
1. [Queue already filled?]
If FRONT = 1 and REAR = N, or if FRONT = REAR+1, then:
Write: OVERFLOW, and Return.
2. [Find new value of REAR.]
If FRONT = NULL, then: [Queue initially empty.]
Set FRONT:=1 and REAR:=1.
Else if REAR = N, then:
Set REAR:=1.
Else:
Set REAR := REAR + 1.
[End of If structure.]
3. Set QUEUE[REAR] := ITEM. [This inserts new element.]
4. Return.

ALGORITHM FOR CIRCULAR QUEUE DELETE

Algorithm : QDELETE (QUEUE, N, FRONT, REAR, ITEM)

This procedure deletes an element from a queue and assigns it to the variable item.
1. [Queue already empty?]
If FRONT := NULL, then: Write: UNDERFLOW, and Return.
2. Set ITEM := QUEUE[FRONT].
3. [Find new value of FRONT.]
If FRONT = REAR, then: [Queue has only one element to start.]
Set FRONT := NULL and REAR := NULL.
Else if FRONT = N, then:
Set FRONT := 1.
Else:

12 | P a g e
 DATA STRUCTURE USING C++ BCA 313 UNIT II

Set FRONT := FRONT+1.

[End of If structure.]
4. Return

IMPLEMENTATION OF CIRCULAR QUEUE

#include<iostream>
#define maxsize 5
using namespace std;
void insertq();
void deleteq();
void displayq();
int queue[maxsize],front=-1,rear=-1;
int main()
{
int choice;
while(1)
{
cout<<"\n 1. INSERT";
cout<<"\n 2. DELETE";
cout<<"\n 3. DISPLAY";
cout<<"\n 0. EXIT";
cout<<"\n\n\t\tENTER YOUR CHOICE : ";
cin>>choice;
switch(choice)
{
case 1:
insertq();
displayq();
break;
case 2:
deleteq();
displayq();
break;
case 3:
displayq();
break;
case 0:
exit(0);
default:
cout<<"\n\n\t\tYOU ENTERED WRONG CHOICE";
}
}
return 0;
}
void insertq()
{
int item;
if((front==0)&&(rear==maxsize-1)||(front==rear+1))
{

13 | P a g e
 DATA STRUCTURE USING C++ BCA 313 UNIT II

cout<<"\n\n\t\tTHE QUEUE IS FULL";

return;
}
else
{
cout<<"\n\n\t\tENTER THE ELEMENT TO BE INSERTED : ";
cin>>item;
if(front==-1)
{
front=0;
rear=0;
}
else
{
if(rear==maxsize-1)
{
rear=0;
}
else
{
rear=rear+1;
}
}
queue[rear]=item;
}
}
void deleteq()
{
int item;
if(front==-1)
{
printf("\n\n\t\tTHE QUEUE IS EMPTY");
return;
}
else
{
item=queue[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
if(front==maxsize-1)
{
front=0;
}
else
{

14 | P a g e
 DATA STRUCTURE USING C++ BCA 313 UNIT II

front=front+1;
}
}
cout<<"\n\n\t\tTHE DELETED ITEM IS "<<item;
}
}
void displayq()
{
int i;
if(front==-1)
{
cout<<"\n\n\t\tTHE QUEUE DOES NOT CONTAIN ANY ELEMENT";
return;
}
else
{
cout<<"\n\n\t\tTHE QUEUE IS \n";
if(front<=rear)
{
for(i=front;i<=rear;i++)
{
cout<<"\n\t\t"<<queue[i];
}
}
else
{
for(i=front;i<=maxsize-1;i++)
{
cout<<"\n\t\t"<<queue[i];
}
for(i=0;i<=rear;i++)
{
cout<<"\n\t\t"<<queue[i];
}
}
}
}

DEQUES
A deque (pronounced either "deck" or "dequeue") is a linear list in which elements can be
added or removed at either end but not in the middle. The term deque refers to the name
double-ended queue.

Insertion Deletion
10 20 30 40 50 60
Deletion Insertion
Dq[1] DQ[2] DQ[3] DQ[4] DQ[5] DQ[6]

15 | P a g e
 DATA STRUCTURE USING C++ BCA 313 UNIT II

There are two variations of a deque - namely, an input-restricted deque and an output
restricted deque - which are intermediate between a deque and a queue. An 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; and an output-restricted deque is a deque, which allows deletions at only
one end of the list buy allows insertions at both ends of the list.

Figure shows two deques, each 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.

Deletion
Deletion 10 20 30 40 50 60
Insertion
Dq[1] DQ[2] DQ[3] DQ[4] DQ[5] DQ[6]

Input Restricted Deque

Insertion
10 20 30 40 50 60 Insertion
Deletion
Dq[1] DQ[2] DQ[3] DQ[4] DQ[5] DQ[6]

Output Restricted Deque

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.

Many application involving queues require priority queues rather than the simple FIFO
strategy. For elements of same priority, the FIFO order is used. For example, in a multiuser
system, there will be several programs competing for use of the central processor at one time.
The programs have a priority value associated to them and are held in a priority queue. The
program with the highest priority is given first use of the central processor.

Scheduling of jobs within a time-sharing system is another application of queues. In such

system many users may request processing at a time and computer time divided among these
requests. The simplest approach sets up one queue that store all requests for processing.
Computer processes the request at the front of the queue and finished it before starting on the
next. Same approach is also used when several users want to use the same output device, say
a printer.

16 | P a g e
 DATA STRUCTURE USING C++ BCA 313 UNIT II

In a time sharing system, another common approach used is to process a job only for a
specified maximum length of time. If the program is fully processed within that time, then the
computer goes on to the next process. If the program is not completely processed within the
specified time, the intermediate values are stored and the remaining part of the program is put
back on the queue. This approach is useful in handling a mix of long and short jobs.

17 | P a g e