Ch.
13 Data Structure (Stack & Queue)
13.1 Data Structure: The logical representation of data in the memory is called Data
structure.
Data
Structure
Primitive Data structure Non-Primitive Data structure
Integer Linear Data structure Non-Linear Data structure
Float Array Graphs
Character Stack Tree
Boolean Queue
Linked List
13.2 Stack : In Computer Science, a Stack, also known as LIFO(Last In First Out) or
FILO(First In Last Out) structure , is a linear data structure that allows insertion(Push) and
deletion(Pop) of an element only from one end i.e. TOP. It serves following operations:
Push, which adds an element to the collection, and
Pop, which removes the most recently added element that was not yet removed.
T
IMPLEMENTATION OF STACK IN JAVA USING ARRAY
CASE 1: When some elements are present in the Stack.
TOP
[0] [1] [2] [3] [4]
6 5 3
CASE 2: When the Stack is empty.
TOP == -1
TOP
-1 [0] [1] [2] [3] [4]
CASE 3: When the Stack is full.
TOP >= size-1
TOP
[0] [1] [2] [3] [4]
6 5 3 7 8
OPERATIONS ON A STACK
There may be two cases to push/pop an element on a stack, First when the TOP is initialized with -1 and
Second when the TOP is initialized with 0.
TOP = -1 TOP = 0
Push operation
Algorithm/Pseudo Code Algorithm/Pseudo Code
Start Start
Read/Accept value N Read/Accept value N
if TOP < Size-1 then if TOP < Size then
TOP = TOP +1 Stack[TOP] = N
Stack[TOP] = N TOP = TOP +1
else else
print “OVERFLOW” print “OVERFLOW”
End End
Function/Code Function/Code
void push (int v) void push (int v)
{ {
if(top < size-1) if(top < size)
{ {
st[++top]=v; st[top++]=v;
} }
else else
{ {
[Link] (“OVERFLOW”); [Link] (“OVERFLOW”);
} }
} }
Pop operation
Algorithm/Pseudo Code Algorithm/Pseudo Code
Start Start
if TOP != -1 then if TOP != 0 then
RETURN Stack[TOP - -] RETURN Stack[--TOP]
else else
Print “UNDERFLOW” Print “UNDERFLOW”
RETURN RETURN
End End
Function/Code Function/Code
int pop () int pop ()
{ {
if(top != -1) if(top != 0)
{ {
return st[top- -]; return st[--top];
} }
else else
{ {
[Link] (“UNDERFLOW”); [Link] (“UNDERFLOW”);
return -999; return -999;
} }
} }
Question 1: Register is an entity which can hold a maximum of 100 names. The register enables the user to add and remove
names from the top most end only.
Define a class Register with the following details:
Class name : Register
Data members / instance variables:
stud[ ] : array to store the names of the students
cap : stores the maximum capacity of the array
top : to point the index of the top end
Member functions:
Register (int max) :constructor to initialize the data member cap = max, top = −1 and create the string array.
void push(String n) :to add names in the register at the top location if possible, otherwise display the message “OVERFLOW”.
String pop( ) :removes and returns the names from the top most location of the register if any, else returns “$$”
void display( ) : displays all the names in the register.
(a) Specify the class Register giving details of the functions void push(String) and String pop( ). Assume that the other
functions have been defined. The main function and algorithm need NOT be written. [4]
(ISC 2018)
Solution: (a)
class Register
{
String stud[]=new String[100];
int cap,top;
public Register(int max)
{
cap=max;
top=-1;
stud=new String[cap];
}
void push(String n)
{
if(top<cap-1)
{
stud[++top]=n;
}
else
{
[Link]("OVERFLOW");
}
}
String pop()
{
if(top != -1)
{
return stud[top- -];
}
else
{
return "$$";
}
}
Question 2: Strange is an entity which can hold a maximum of 20 integers. The strange restriction is that an integer can only be
added from the top or removed from the top.
Define a class Strange with the following details:
Class name : Strange
Data members / instance variables:
ele[ ] : array to store integer elements
cap : stores the maximum capacity of the array
top : to point the index of the top end
Member functions:
Strange (int capacity) :constructor to initialize the data member cap = capacity and top = 0.
void pushItem (int val) :adds the integer value to the top if possible, otherwise display the message “Strange is full, cannot push
item”.
int popItem ( ) : removes the item from the top of strange and returns it if strange is not empty. Otherwise output a message
“ Strange is empty” and returns -9999.
Specify the class Strange giving details of the functions void pushItem (int val) and int popItem( ). The main function and
algorithm need NOT be written.
Solution:
class Strange
{
Int ele[]=new int[20];
int cap,top;
public Strange(int capacity)
{
cap=capacity;
top=0;
ele=new int[cap];
}
void pushItem(int val)
{
if(top < cap)
{
stud[top++]=val;
}
else
{
[Link](“Strange is full, cannot push item”);
}
}
int popItem()
{
if(top != 0)
{
return ele[- -top];
}
else
{
[Link](“Strange is empty”);
return -9999;
}
}
Queue: The Queue is a FIFO(First In First Out) data structure i.e. the first element added to the queue will
be the first one to be removed.
A Queue is open at both its ends . An element is inserted from one end called rear and deleted from the
other end called as front. The operation of adding an element to the rear of the queue is known
as enqueue, and the operation of removing an element from the front is known as dequeue.
Rear
IMPLEMENTATION OF QUEUE IN JAVA USING ARRAY
Note: In case of Queue in Java, we can reserve first cell of the array to store pointers front and rear i.e.
we start storing values from index no. 1.
CASE 1: When some elements are present in the Queue.
Front Rear
[0] [1] [2] [3] [4]
5 3
CASE 2: When the Queue is empty.
Front = Rear = 0
Front Rear
[0] [1] [2] [3] [4]
CASE 3: When the Queue is full.
Rear >= size-1
Front Rear
[0] [1] [2] [3] [4]
5 3 7 8
Operations on Queue
To insert or delete an element from the Queue, There may be various cases but we will take only one case
in Java i.e. when front and Rear both are initialized with 0 :
When Both Front and Rear are initialized with 0 (Front = Rear = 0)
Front Rear
-1 [0] [1] [2] [3] [4]
Insertion in Queue Deletion in Queue
Function/Code Function/Code
void insert (int v) int delete ()
{ {
if (Rear < size-1) if (Front != Rear)
{
{
return Queue[++Front];
Queue[++Rear]=v;
}
} else
else {
{ [Link](“UNDERFLOW”);
[Link](“OVERFLOW”); return -999;
} }
} }
Question 1
A linear data structure enables the user to add address from rear end and remove address from front.
Define a class Diary with the following details:
Class name : Diary
Data members / instance variables:
Q[ ] : array to store the addresses
size : stores the maximum capacity of the array
start : to point the index of the front end
end : to point the index of the rear end
Member functions:
Diary (int max): constructor to initialize the data member size=max, start=0 and end=0
void pushadd(String n) :to add address in the diary from the rear end if possible, otherwise display
the message “ NO SPACE”
String popadd( ) : removes and returns the address from the front end of the diary if any, else
returns “?????”
void show( ) : displays all the addresses in the diary
(a)Specify the class Diary giving details of the functions void pushadd(String) and String popadd( ). Assume
that the other functions have been [Link] main function and algorithm need NOT be written.
Solution:
import [Link].*;
class Diary
{
String Q[];
int size,start,end;
Diary(int max)
{
size=max;
Q=new String[size];
start=0;
end=0;
}
void pushadd(String n)
{
if(end < size-1)
{
Q[++end]=n;
}
else
{
[Link]("NO SAPCE");
}
}
String popadd()
{
if(start !=end)
{
return Q[++start];
}
else
{
return "$$$$$";
}
}
}
Operations on Double ended Queue
In Double ended queue insertion and deletion can take place from both the ends.
When Both Front and Rear are initialized with 0 (Front = Rear = 0)
Front Rear
-1 [0] [1] [2] [3] [4]
Insertion from Front Insertion from Rear
Function/Code Function/Code
void insert (int v) void insert (int v)
{ {
if (Front != 0) if (Rear < size-1)
{ {
Queue[Front- -]=v; Queue[++Rear]=v;
} }
else else
{ {
[Link](“OVERFLOW”); [Link](“OVERFLOW”);
} }
} }
Deletion from Front Deletion from Rear
Function/Code Function/Code
int delete () int delete ()
{ {
if (Front != Rear) if (Front != Rear)
{ {
return Queue[++Front]; return Queue[Rear- -];
} }
else else
{ {
[Link](“UNDERFLOW”); [Link](“UNDERFLOW”);
return -999; return -999;
} }
} }
Operations on Circular Queue
To insert or delete an element from the Queue, There may be various cases but we will take only one case
in Java i.e. when front and Rear both are initialized with 0 :
When Both Front and Rear are initialized with 0 (Front = Rear = 0)
Insertion in Circular Queue Deletion in Circular Queue
Function/Code Function/Code
void insert (int v) int delete ()
{ {
if ((Rear+1) % size !=Front) if (Front != Rear)
{
{
Front= (Front+1) % size;
Rear= (Rear+1) % size;
return Queue[Front];
Queue[Rear]=v;
}
} else
else {
{ [Link](“UNDERFLOW”);
[Link](“OVERFLOW”); return -999;
} }
} }