A Case Study – Data

Structures

This case study shows the implementation of concepts of data struc-

tures-Stacks and Queue.
A data structure is an arrangement of data either in the computer's mem-
ory or on the disk storage. Some common examples of data structure include
arrays, linked lists, queues, stacks, binary trees, and hash tables. Data struc-
tures are widely applied in areas as follows:
• Compiler design
• Operating system
• Statistical analysis package
• Data base management system
• Numerical analysis
• Simulation
• Artificial intelligence
• Graphics
There are a variety of data structures like arrays, linked lists, stacks, queues, trees, and graphs.

A.1 STACKS
In a computer’s memory, stacks can be represented as a linear array. Every stack has a varia-
ble TOP associated with it. TOP is used to store the address of the topmost element of the stack.
It is this position from where the element will be added or deleted. There is another variable
MAX, which will be used to store the maximum number of elements that the stack can store.
If TOP = NULL, then it indicates that the stack is empty and if TOP = MAX, then the stack is full.
The stack in Fig. A.1 shows that TOP = 4, so insertions and deletions will be done at
this position. Here, the stack can store utmost 10 elements where the indices range from
0–9. In the stack, five more elements can be stored.

A AB ABC ABCD ABCDE

0 1 2 3 TOP = 4
5 6 7 8 9
Figure A.1 Stack

© Oxford University Press, 2015. All rights reserved.

2 Thareja: Object Oriented Programming with C++

A stack has three basic operations—push, pop, and peep. The push operation adds an ele-
ment to the top of the stack. The popoperation removes the element from the top of the stack.
Finally, the peep operation returns the value of the topmost element of the stack.
However, before inserting an element in the stack, we must check for overflow condition.
An overflow will occur when we will try to insert an element into a stack that is already full.
Similarly, before deleting an element from the stack, we must check for underflow con-
dition. An underflow condition occurs when we try to delete an element from a stack that is
already empty. If TOP = -1, it indicates that there is no element in the stack.
Advantage—Lastin, firstout access (LIFO)
Disadvantage—Slow access to other elements

Example 1 Stack operations

#include<iostream.h>
#include<conio.h>
template<class T>
class Stack
{ private:
T *data;
int top;
int size;
public:
Stack(int n)
{ top = -1;
size = n;
data = new T[size];
}
void push(T elem)
{ try
{ if(top<size-1)
{ top++;
data[top] = elem;
}
else
throw "STACK OVERFLOW";
}
catch(char *msg)
{ cout<<"\n"<<msg;
}
}
T pop()
{ try
{ if(top==-1)
throw "STACK UNDERFLOW";
else
return data[top--];
}
catch(char *msg)
{ cout<<"\n"<<msg;
}

© Oxford University Press, 2015. All rights reserved.

 Case Study – Data Structures 3

}
void display()
{ for(inti=0;i<=top;i++)
cout<<"\t"<<data[i];
}
};
void main()
{ inti,n;
cout<<"\n Enter the number of
elements : ";
cin>>n;
Stack <int>S(n);
for(i=0;i<n;i++)
S.push(i);
cout<<"\n\n Adding an element when stack
is full.....";
S.push(i);
cout<<"\n Elements of
the Stack are : ";
S.display();
for(i=0;i<n;i++)
cout<<"\n Value Popped =
"<<S.pop();
cout<<"\n\n Deleting an element when
stack is empty.....";
S.pop();
cout<<"\n Elements of
the Stack are : ";
S.display();
getch();
}

OUTPUT
Enter the number of elements : 5
Elements of the Stack are : 0 1 2 3 4
Adding an element when stack
is full.....";
Stack Overflow
Value Popped = 4
Value Popped = 3
Value Popped = 2
Value Popped = 1
Value Popped = 0
Deleting an element when
stack is empty.....";
Stack Underflow

© Oxford University Press, 2015. All rights reserved.

4 Thareja: Object Oriented Programming with C++

A.2 QUEUE
A queue is a FIFO or first in first out data structure in which the element that was inserted first
is the first one to be taken out. The elements in a queue are added at one end called the rear
and removed from the other one end called front. Like stacks, queues can be implemented
either using arrays or linked lists.

12 9 7 18 14 36

0 1 2 3 4 5 6 7 8 9
Figure A.2 Queue
Every queue will have front and rear variables that will point to the position from where
deletions and insertions can be done, respectively. Consider a queue given in Fig. A.2.
Here, front = 0 and rear = 5. If we want to add one more value in the list say, if we
want to add another element with value 45, then rear would be incremented by 1 and the
value would be stored at the position pointed by rear. The queue after addition would be
as shown in Fig. A.3.

12 9 7 18 14 36 45

0 1 2 3 4 5 6 7 8 9
Figure A.3 Queue after insertion of a new
element

Here, front = 0 and rear = 6. Every time a new element has to be added, we will repeat
the same procedure.
Now, if we want to delete an element from the queue, then the value of front will be incremented.
Deletions are done from only this end of the queue. The queue after deletion will be as shown in
Fig. A.4.

9 7 18 14 36 45

0 FRONT = 1 2 3 4 5 REAR = 6 7 8 9
Figure A.4 Queue after deletion of an element

However, before inserting an element in the queue, we must check for overflow con-
ditions. An overflow will occur when we will try to insert an element into a queue that is
already full, when Rear = MAX — 1, where MAX is the size of the queue that is, MAX specifies
the maximum number of elements in the queue. Note we have written MAX — 1, because
the index starts from 0.
Similarly, before deleting an element from the queue, we must check for underflow con-
dition. An underflow condition occurs when we try to delete an element from a queue that
is already empty. If front = -1 and rear = -1, this means there is no element in the queue.
Advantage—provides first-in, first-out data access
Disadvantage—Slow access to other items
© Oxford University Press, 2015. All rights reserved.
 Case Study – Data Structures 5

Example 2 Operations on Queue

#include<iostream.h>
#include<conio.h>
template<class T>
class Queue
{ private:
T *data;
int front;
int rear;
int size;
public:
Queue(int n)
{ front = rear = -1;
size = n;
data = new T[size];
}
void insert(T elem)
{ try
{ if(front == -1 && rear == -1)
{ front = rear = 0;
data[rear++] = elem;
}
else if(rear==size)
throw "QUEUE OVERFLOW";
else
data[rear++] = elem;
}
catch(char * msg)
{ cout<<"\n"<<msg;
}
}
T remove()
{ try
{ if(front==-1 || front == rear)
throw "QUEUE UNDERFLOW";
else
return data[front++];
}
catch(char * msg)
{ cout<<"\n"<<msg;
}

}
void display()
{ for(inti=front;
i<rear;i++)
cout<<"\t"

© Oxford University Press, 2015. All rights reserved.

6 Thareja: Object Oriented Programming with C++

<<data[i];
}
};
void main()
{ inti,n;
cout<<"\n Enter the number
of elements : ";
cin>>n;
Queue <char>Q(n);
for(i=0;i<n;i++)
Q.insert((char)i+65);
cout<<"\n Elements of
the Queue are : ";
Q.display();
cout<<"\n\n Adding an element when
the Queue is full .........";
Q.insert((char)i+65);
for(i=0;i<n;i++)
cout<<"\n Value Removed = "<<Q.remove();
cout<<"\n Elements of
the Queue are : ";
cout<<"\n\n Deleting an element
when the Queue is empty .........";
Q.remove();
Q.display();
getch();
}

OUTPUT
Enter the number of elements : 5
Elements of the Queue are :A B C D E
Adding an element when
the Queue is full .........";
Queue Overflow
Value Removed = A
Value Removed = B
Value Removed = C
Value Removed = D
Value Removed = E
Deleting an element when
the Queue is empty .........
Queue Underflow

© Oxford University Press, 2015. All rights reserved.