Stack:
A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. In other words, “a stack can be defined as a
container in which insertion and deletion can be done from the one end known as the top of the stack.”
Characteristic of Stack:
– Insertion of an element can be done only on top of the stack.
– Deletion of an element can be done only from top of the stack.
Standard Stack Operations
The following are some common operations implemented on the stack:
push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow
condition occurs.
pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no
element exists in the stack, this state is known as an underflow state.
isEmpty(): It determines whether the stack is empty or not.
isFull(): It determines whether the stack is full or not.
display(): It prints all the elements available in the stack.
Memory representation of array:
There are two ways to represent stack in the memory:
1. Sequential Representation (Using Array)
2. Linked Representation (Using Linked List)[will be dealt later]
PUSH operation
The steps involved in the PUSH operation is given below:
Before inserting an element in a stack, we check whether the stack is full.
If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element
will be placed at the new position of the top.
The elements will be inserted until we reach the max size of the stack.
Algorithm: PUSH(S,ITEM)
Assume S[Size] is an array used to represent stack in memory. Let TOP holds index of top most
element, which is initially set to -1. ITEM is the element to be pushed on to the stack.
Step1: Start
Step2: Display “Enter the element to be pushed”
Step3: Read ITEM
Step4: If(TOP==SIZE–1), Then
Step4.1: Display “Overflow”
Step4.2: Exit
[End of If–Step4]
Step5: Set TOP:=TOP+1
Step6: Set S[TOP]:=ITEM
Step7: Stop
POP operation
The steps involved in the POP operation is given below:
Before deleting the element from the stack, we check whether the stack is empty.
If we try to delete the element from the empty stack, then the underflow condition occurs.
If the stack is not empty, we first access the element which is pointed by the top
Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
Algorithm: POP(S)
Assume S[Size] is an array used to represent stack in memory. Let TOP holds index of top most element.
Step1:Start
Step2:Let ITEM
Step3:If(TOP==–1),Then
Step3.1:Display“Underflow”
Step3.2:Exit
[End of If–Step3]
Step4:Set ITEM:=S[TOP]
Step5:Display“Popped element is”,ITEM
Step6:Set TOP:=TOP–1
Step7:Stop
Application of stack:
Convert the following infix expression into prefix expression.
A+B*(C–D^E)/F
Sol:
A+B*(C–D^E)/F
=>A+B*(C–[^DE])/F
=>A+B*[–C^DE]/F
=>A+[*B–C^DE]/F
=>A+[/*B–C^DEF]
=>+A/*B–C^DE
2) Procedure for Conversion of Infix to Postfix:
Identify inner most bracket present in the expression
Identify the operator according to the priority of evaluation.
Represent the operator and corresponding operands in postfix notation.
Continue this process until equivalent postfix expression is achieved
Ex: Convert the following infix expression into postfix expression.
A+B*(C–D^E)/F
Sol:
A+B*(C–D^E)/F
=>A+B*(C–[DE^])/F
=>A+B*[CDE^–]/F
=>A+[BCDE^–*]/F
=>A+[BCDE^–*F/]
=>ABCDE^–*F/+
CONVERSION OF INFIX TO POSTFIX USING STACK
Q. Convert the following infix expression to corresponding postfix expression using stack.
(A * B –( C / D ^ E) + F –G)
QUEUE AND ITS APPLICATIONS
QUEUE
• A queue can be defined as an ordered list which enables insert operations to be performed at one end called REAR and delete
operations to be performed at another end called FRONT.
• Queue is referred to be as First In First Out (FIFO) list.
• For example, people waiting in line for a rail ticket form a queue.
APPLICATIONS OF QUEUE
Due to the fact that queue performs actions on first in first out basis which is quite fair for the ordering of actions. There are
various applications of queues discussed as below.
• Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
• Queues are used in asynchronous transfer of data (where data is not being transferred at the same rate between two processes)
for eg. pipes, file IO, sockets.
• Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.
• Queues are used to maintain the play list in media players in order to add and remove the songs from the play-list.
• Queues are used in operating systems for handling interrupts.
TYPES OF QUEUES
There are four types of queues :
– Linear Queue : In Linear Queue, an insertion takes place from one end while the deletion occurs from another end.
– Circular Queue : In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue except
that the last element of the queue is connected to the first element.
– Double Ended Queue ( Deque) : Both the Linear Queue and Deque are different as the linear queue follows the FIFO
principle whereas, deque does not follow the FIFO principle. In Deque, the insertion and deletion can occur from both
ends.
– Priority Queue : A priority queue is another special type of Queue data structure in which each element has some
priority associated with it. In priority Queue, the insertion takes place based on the arrival while the deletion occurs
based on the priority.
LINEAR QUEUE
MEMORY REPRESENTATION OF LINEAR QUEUE
• A queue can be represented in the memory in two ways:
– Sequential Representation ( Using Array)
– Linked Representation ( Using Linked List) – will be dealt later
• Array Representation of Linear Queue :
• An one-dimensional array is considered to represent linear queue in the memory.
• We will consider two variables FRONT and REAR which will hold the index of front and rear element of linear queue.
• Initially, FRONT := -1 and REAR := -1 indicates that the linear queue is empty (i.e. Linear queue does not have any
elements).
• The value of REAR will be incremented by 1 each time an element is inserted into the queue.
• The value of FRONT will be incremented by 1 each time an element is deleted from the queue.
• Overflow Condition: when REAR == SIZE – 1 (Where SIZE is the size of the array used to represent queue)
• Underflow Condition: when FRONT ==-1 or REAR == – 1 ( When queue is empty)
AN EXAMPLE
Assume Q[6] is an array representing Linear Queue in the memory. List out the elements left in the Queue after performing following
series of insertion and deletion operations:
Insert (10), insert (20), insert (30), delete, insert(40), delete, delete, insert(50), insert (60), delete
AN EXAMPLE
The elements left in the Queue after performing above series of insertion and deletion operations are:50 60
OPERATIONS ON LINEAR QUEUE
INSERTION OPERATION: STEPS
The steps involved in the INSERTION operation are given below:
• Before inserting an element into a Queue, we check whether the Queue is full?
• If we try to insert the element into a Queue, and the Queue is full, then the overflow condition arises.
• When we initialize a Queue, we set the value of FRONT and REAR as -1 to indicate that the Queue is empty initially.
• If the ITEM is to be inserted as the first element in the Queue, in that case set the value of FRONT and REAR to 0 and insert
the element at the rear end.
• If Queue has one or more elements in it, then we will set REAR := REAR + 1 and item is inserted at updated REAR index.
INSERTION OPERATION: ALGORITHM
Algorithm : QINSERT(Q[SIZE],ITEM)
Assume Q[SIZE] is an array representing Queue in memory.
Let FRONT and REAR holds index of front and rear element, which are initially set to -1.
ITEM is the element to be inserted.
Step 1: Start
Step 2: Display “Enter the element to be inserted”
Step 3: Read ITEM
Step 4: If (REAR = = SIZE – 1 ), Then
Step 4.1:Display “Overflow”
Step 4.2: Exit
[End of If – Step 4 ]
Step 5: If (FRONT = = - 1 OR REAR = = - 1 )
Step 5.1: Set FRONT := 0 , REAR := 0
Step 6: Else
Step 6.1: Set REAR := REAR + 1
[ End of If – Step 5 ]
Step 7: Set Q[REAR] := ITEM
Step 8: Stop
DELETETION OPERATION: STEPS
The steps involved in the DELETION operation are given below:
• Before deleting the element from the Queue, we will check whether the Queue is empty or not.
• If we try to delete an element from the empty Queue, then the underflow condition will occur.
• If the there is only one element in the Queue, then after deletion, the Queue will become empty, hence we need to set both FRONT
and REAR to – 1 .
• If the Queue has more than one element, then FRONT value will be updated as FRONT:= FRONT + 1
DELETION OPERATION: ALGORITHM
Algorithm : QDELETION(Q)
Assume Q[Size] is an array representing a Queue in memory.
Let FRONT holds index of front element , REAR holds index of rear element of Queue.
Step 1: Start
Step 2: Let ITEM
Step 3: If (FRONT == – 1 or REAR == - 1 ), Then
Step 3.1:Display “Underflow”
Step 3.2: Exit
[End of If – Step 3 ]
Step 4: Set ITEM := Q[FRONT]
Step 5: Display “Deleted element is ” ,ITEM
Step 6: If ( FRONT = = REAR ), Then
Step 6.1: Set FRONT:= -1 , REAR := - 1
Step 7: Else
Step 7.1 : Set FRONT := FRONT + 1
[End of If – Step 6 ]
Step 8: Stop
CIRCULAR QUEUE:
There was one limitation in the array implementation of Queue.
If the REAR reaches to the end position of the Queue then there might be possibility that some vacant
spaces are left in the beginning which cannot be utilized.
So, to overcome such limitations, the concept of the circular queue was introduced.
ADVANTAGE OF CIRCULAR QUEUE
As we can see in the below diagram :
1. In the array, there are only two elements and other three positions are empty.
2. The REAR is at the last position of the Queue; if we try to insert the element then it will show that there are no empty spaces in
the Queue.
3. There is one solution to avoid such wastage of memory space by shifting both the elements at the left and adjust the front and
rear end accordingly.
4. It is not a practically good approach because shifting all the elements will consume lots of time. The efficient approach to avoid
the wastage of the memory is to use the circular queue data structure.
Example of Circular Queue
Assume CQ[5] is an array representing Circular Queue in the memory. The following shows series of insertion and deletion operations
on it.
INSERT(10), INSERT(20), INSERT(30), INSERT(40), DELETE, INSERT(50), DELETE, INSERT( 60), INSERT(70)
OPERATIONS ON CIRCULAR QUEUE:
INSERTION OPERATION IN CIRCULAR QUEUE: STEPS
The steps involved in the INSERTION operation are given below:
• Before inserting an element into a Circular Queue, we will check whether it is full? For this, either of the following two overflow
conditions can be tested .
– FRONT == 0 AND REAR == SIZE – 1
– FRONT == (REAR +1) % SIZE
• If the ITEM is to be inserted as the first element in the Circular Queue, then we will set the value of FRONT and REAR to 0
and insert the element at the rear end.
• If Circular Queue has one or more elements in it, then we will calculate the REAR value by using the following:
– REAR := (REAR + 1)% SIZE and item is inserted at updated REAR index.
INSERTION OPERATION: ALGORITHM
Algorithm : CQINSERT(CQ[SIZE],ITEM)
Assume CQ[SIZE] is an array representing Circular Queue in memory.
Let FRONT and REAR holds index of front and rear element, which are initially set to -1.
ITEM is the element to be inserted.
Step 1: Start
Step 2: Display “Enter the element to be inserted”
Step 3: Read ITEM
Step 4: If (FRONT == 0 AND REAR == SIZE – 1), Then
Step 4.1:Display “Overflow”
Step 4.2: Exit
[End of If – Step 4]
Step 5: If (FRONT == - 1 OR REAR == - 1)
Step 5.1: Set FRONT := 0 , REAR := 0
Step 6: Else
Step 6.1: Set REAR := (REAR + 1) % SIZE
[ End of If – Step 5 ]
Step 7: Set CQ[REAR] := ITEM
Step 8: Stop
DELETETION OPERATION: STEPS
The steps involved in the DELETION operation are given below:
• Before deleting the element from the Circular Queue, we will check whether it is empty or not.
• If we try to delete an element from the empty Circular Queue, then the underflow condition will occur.
– i.e. When FRONT == -1 OR REAR == - 1
• If there is only one element in the Circular Queue, then after deletion, the Circular Queue will become empty, hence we need to
set both FRONT and REAR to – 1 .
• If the Circular Queue has more than one element, then FRONT value will be updated as FRONT:= (FRONT + 1)%SIZE
DELETION OPERATION: ALGORITHM
Algorithm : CQDELETION(CQ)
Assume CQ[SIZE] is an array representing a Circular Queue in memory.
Let FRONT holds index of front element , REAR holds index of rear element of the Queue.
Step 1: Start
Step 2: Let ITEM
Step 3: If (FRONT == – 1 or REAR == - 1 ), Then
Step 3.1:Display “Underflow”
Step 3.2: Exit
[End of If – Step 3 ]
Step 4: Set ITEM := CQ[FRONT]
Step 5: Display “Deleted element is ” ,ITEM
Step 6: If ( FRONT = = REAR ), Then
Step 6.1: Set FRONT:= -1 , REAR := - 1
Step 7: Else
Step 7.1 : Set FRONT := (FRONT + 1 ) % SIZE
[End of If – Step 6 ]
Step 8: Stop
DOUBLE ENDED QUEUE:
Deque is a linear data structure in which the insertion and deletion operations are performed from both
ends.
We can say that deque is a generalized version of the queue.
1. The following set of operations are possible on DEQUE.
Insertion at REAR end ( Same as Linear Queue )
Deletion from FRONT end ( Same as Liner Queue )
Insertion at FRONT end
Deletion from REAR end
TYPES OF DEQUE
There are two types of DEQUE:
1. Input-Restricted Deque
2. Output-Restricted Deque
Input-Restricted Deque :
It is a deque in which insertion operation is restricted at only one end, but deletion operation is allowed at both ends. So, the
following operations are possible:
Insertion at REAR end or FRONT end
Deletion from FRONT end
Deletion from REAR end
Output-Restricted Deque :
It is a deque in which deletion operation is restricted at only one end, but insertion operation is allowed at both ends. So, the
following operations are possible:
Deletion at REAR end or FRONT end
Insertion at FRONT end
Insertion at REAR end
PRIORITY QUEUE:
• A priority queue is an abstract data type that behaves similarly to the normal queue except that each element has some priority,
i.e., the element with the highest priority would come first in a priority queue.
• The priority of the elements in a priority queue will determine the order in which elements are removed from the priority queue.
• The priority queue supports only comparable elements, which means that the elements are either arranged in an ascending or
descending order.
• For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue with an ordering imposed on the
values is from least to the greatest. Therefore, the 1 number would be having the highest priority while 22 will be having the
lowest priority.
• A priority queue is an extension of a queue that contains the following characteristics:
– Every element in a priority queue has some priority associated with it.
– An element with the higher priority will be deleted before the deletion of the lesser priority.
– If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
TYPES OF PRIORITY QUEUES
There are two types of priority queue:
• Ascending order priority queue: In ascending order priority queue, a lower priority number is given as a higher priority in a
priority. For example, we take the numbers from 1 to 5 arranged in an ascending order like 1,2,3,4,5; therefore, the smallest
number, i.e., 1 is given as the highest priority in a priority queue.
• Descending order priority queue: In descending order priority queue, a higher priority number is given as a higher priority in a
priority. For example, we take the numbers from 1 to 5 arranged in descending order like 5, 4, 3, 2, 1; therefore, the largest number,
i.e., 5 is given as the highest priority in a priority queue.
APPLICATIONS OF PRIORITY QUEUE
The following are the applications of the priority queue:
It is used in the Dijkstra's shortest path algorithm.
It is used in prim's algorithm
It is used in data compression techniques like Huffman code.
It is used in heap sort.
It is also used in operating system like priority scheduling, load balancing and interrupt handling.