Unit - 2
Stack & Queue
The stack is created using the array in array implementation. Arrays are used to accomplish all of the operations on the stack. Let's look at how each operation can be accomplished utilizing an array data structure on the stack.
Adding an element onto the stack (push operation)
A push operation occurs when an element is added to the top of a stack. Two steps are involved in a push operation.
- Increase the value of the variable Top to allow it to refer to the next memory address.
- Add an element to the top of the incremented list. Adding a new element to the top of the stack is referred to as this.
When we try to put an element into a totally loaded stack, the stack overflows. As a result, our main function must always avoid stack overflow.
Algorithm
Begin
If top = n then stack full
Top = top + 1
Stack (top) : = item;
End
Implementation in C language
Void push (int val,int n) //n is size of the stack
{
If (top == n )
Printf("\n Overflow");
Else
{
Top = top +1;
Stack[top] = val;
}
}
Deletion of an element from a stack (Pop operation)
The pop action removes an element from the top of the stack. When an item is removed from the stack, the value of the variable top is increased by one. The stack's topmost element is saved in a separate variable, and then the top is decremented by one. As a result, the operation returns the removed value that was previously saved in another variable.
When we try to delete an element from an already empty stack, we get an underflow condition.
Algorithm
Begin
If top = 0 then stack empty;
Item := stack(top);
Top = top - 1;
End;
Implementation in C language
Int pop ()
{
If(top == -1)
{
Printf("Underflow");
Return 0;
}
Else
{
Return stack[top - - ];
}
}
Visiting each element of the stack (Peek operation)
Returning the element at the top of the stack without removing it is known as a peek operation. If we try to return the top piece from an already empty stack, we may encounter an underflow problem.
Algorithm
PEEK (STACK, TOP)
Begin
If top = -1 then stack empty
Item = stack[top]
Return item
End
Implementation in C language
Int peek()
{
If (top == -1)
{
Printf("Underflow");
Return 0;
}
Else
{
Return stack [top];
}
}
Representation of queue using array
Using linear arrays, we can easily describe a queue. In the case of every queue, there are two variables to consider: front and back. In a queue, the front and back variables indicate the location from which insertions and deletions are made. The initial value of front and queue is -1, which indicates that the queue is empty. The next figure shows an array representation of a queue with 5 elements and their respective front and rear values.
Fig: Queue
The line of characters that make up the English word "HELLO" is depicted in the diagram above. Because no deletions have been made in the queue to date, the value of front remains -1. When an insertion is performed in the queue, however, the value of rear increases by one. After entering one element into the queue depicted in the above picture, the queue will appear as follows. The value of the rear will increase to 5, while the value of the front will remain unchanged.
Fig: Queue after inserting element
The value of front will grow from -1 to 0 if an element is deleted. The queue, on the other hand, will resemble the following.
Fig: Queue after deleting element
Algorithm to insert any element in a queue
Compare rear to max - 1 to see if the queue is already full. If this is the case, an overflow error will be returned.
If the item is to be inserted as the first element in the list, set the front and back values to 0 and insert the item at the back end.
Otherwise, keep increasing the value of rear and inserting each element with rear as the index one by one.
Algorithm
Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: Set QUEUE[REAR] = NUM
Step 4: EXIT
C function
Void insert (int queue[], int max, int front, int rear, int item)
{
If (rear + 1 == max)
{
Printf("overflow");
}
Else
{
If(front == -1 && rear == -1)
{
Front = 0;
Rear = 0;
}
Else
{
Rear = rear + 1;
}
Queue[rear]=item;
}
}
Algorithm to delete an element from the queue
Write an underflow message and leave if the value of front is -1 or greater than the value of rear.
Otherwise, keep increasing the front's value and returning the item at the front of the queue each time.
Algorithm
Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
Step 2: EXIT
C function
Int delete (int queue[], int max, int front, int rear)
{
Int y;
If (front == -1 || front > rear)
{
Printf("underflow");
}
Else
{
y = queue[front];
If(front == rear)
{
Front = rear = -1;
Else
Front = front + 1;
}
Return y;
}
}
The following are the applications of the stack:
● Balancing of symbols: Stack is used for balancing a symbol. For example, we have the following program:
- Int main()
- {
- Cout<<"Hello";
- Coût<<"java point";
- }
As we know, each program has an opening and closing braces; when the opening braces come, we push the braces in a stack, and when the closing braces appear, we pop the opening braces from the stack. Therefore, the net value comes out to be zero. If any symbol is left in the stack, it means that some syntax occurs in a program.
● String reversal: Stack is also used for reversing a string. For example, we want to reverse a "java point" string, so we can achieve this with the help of a stack.
First, we push all the characters of the string in a stack until we reach the null character. After pushing all the characters, we start taking out the character one by one until we reach the bottom of the stack.
● UNDO/REDO: It can also be used for performing UNDO/REDO operations. For example, we have an editor in which we write 'a', then 'b', and then 'c'; therefore, the text written in an editor is abc. So, there are three states, a, ab, and abc, which are stored in a stack. There would be two stacks in which one stack shows UNDO state, and the other shows REDO state.
If we want to perform a UNDO operation, and want to achieve an 'ab' state, then we implement a pop operation.
● Recursion: The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained.
● DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.
● Backtracking: Suppose we have to create a path to solve a maze problem. If we are moving in a particular path, and we realize that we come on the wrong way. In order to come at the beginning of the path to create a new path, we have to use the stack data structure.
● Expression conversion: Stack can also be used for expression conversion. This is one of the most important applications of stack. The list of the expression conversion is given below:
● Infix to prefix
● Infix to postfix
● Prefix to infix
● Prefix to postfix
● Postfix to infix
● Memory management: The stack manages the memory. The memory is assigned in the contiguous memory blocks. The memory is known as stack memory as all the variables are assigned in a function called stack memory. The memory size assigned to the program is known to the compiler. When the function is created, all its variables are assigned in the stack memory. When the function completes its execution, all the variables assigned in the stack are released.
The expressions are an infix and a postfix. Constants, variables, and symbols make up an expression. Operators and parentheses are examples of symbols. All of these elements must be structured according to a set of rules so that the set of rules may be used to evaluate all of these expressions.
Rules for the conversion from infix to postfix expression
● As the operands arrive, print them.
● Push the incoming operator onto the stack if the stack is empty or has a left parenthesis on top.
● Push the incoming symbol to the stack if it is '('.
● Pop the stack and print the operators until the left parenthesis is discovered if the entering symbol is ')'.
● If the incoming symbol has a greater priority than the top of the stack, it should be pushed to the top.
● Pop and print the top of the stack if the incoming symbol has a lower priority than the top of the stack. Then compare the incoming operator to the new stack's top.
● Use the associativity rules if the incoming operator has the same precedence as the top of the stack. If the associativity is left to right, pop and print the top of the stack before pushing the inbound operator. Push the incoming operator if the associativity is from right to left.
● Pop and print all of the stack's operators at the end of the expression.
Example
Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q
Input Expression | Stack | Postfix Expression |
K |
| K |
+ | + |
|
L | + | K L |
- | - | K L+ |
M | - | K L+ M |
* | - * | K L+ M |
N | - * | K L + M N |
+ | + | K L + M N* K L + M N* - |
( | + ( | K L + M N *- |
O | + ( | K L + M N * - O |
^ | + ( ^ | K L + M N* - O |
P | + ( ^ | K L + M N* - O P |
) | + | K L + M N* - O P ^ |
* | + * | K L + M N* - O P ^ |
W | + * | K L + M N* - O P ^ W |
/ | + / | K L + M N* - O P ^ W * |
U | + / | K L + M N* - O P ^W*U |
/ | + / | K L + M N* - O P ^W*U/ |
V | + / | KL + MN*-OP^W*U/V |
* | + * | KL+MN*-OP^W*U/V/ |
T | + * | KL+MN*-OP^W*U/V/T |
+ | + | KL+MN*-OP^W*U/V/T* KL+MN*-OP^W*U/V/T*+ |
Q | + | KL+MN*-OP^W*U/V/T*Q |
|
| KL+MN*-OP^W*U/V/T*+Q+ |
The final postfix expression of infix expression(K + L - M*N + (O^P) * W/U/V * T + Q) is KL+MN*-OP^W*U/V/T*+Q+.
Convert infix to prefix expression
Rules for the conversion of infix to prefix expression:
● First, reverse the infix expression given in the problem.
● Scan the expression from left to right.
● Whenever the operands arrive, print them.
● If the operator arrives and the stack is empty, simply place the operator on top of the stack.
● Push the incoming operator onto the stack if the incoming operator has a greater priority than the TOP of the stack.
● Push the incoming operator onto the stack if the incoming operator has the same precedence as a TOP of the stack.
● Pop and print the top of the stack if the incoming operator has a lower priority than the TOP of the stack. Test the incoming operator against the top of the stack once again, then pop it off the stack until it finds an operator with a lower or equal precedence.
● If the incoming operator and the top of the stack have the same precedence and the incoming operator is, pop the top of the stack until the condition is true. Push the operator if the condition isn't true.
● Pop and print all the operators from the top of the stack when we reach the end of the expression.
● Push it into the stack if the operator is ')'.
● If the operator is '(,' then it will pop all the operators from the stack until it finds an opening bracket.
● Push the operator onto the stack if the top of the stack is ')'.
● Reverse the output at the end.
Example
K + L - M * N + (O^P) * W/U/V * T + Q
If we want to transform an infix expression to a prefix expression, we must first reverse the expression.
The inverse expression is as follows:
Q + T * V/U/W * ) P^O(+ N*M - L + K
We've established a table with three columns: input expression, stack, and prefix expression, in order to get the prefix expression. Any symbol that we come across is simply added to the prefix expression. If we come across the operator, we'll add it to the stack.
Input expression | Stack | Prefix expression |
Q |
| Q |
+ | + | Q |
T | + | QT |
* | +* | QT |
V | +* | QTV |
/ | +*/ | QTV |
U | +*/ | QTVU |
/ | +*// | QTVU |
W | +*// | QTVUW |
* | +*//* | QTVUW |
) | +*//*) | QTVUW |
P | +*//*) | QTVUWP |
^ | +*//*)^ | QTVUWP |
O | +*//*)^ | QTVUWPO |
( | +*//* | QTVUWPO^ |
+ | ++ | QTVUWPO^*//* |
N | ++ | QTVUWPO^*//*N |
* | ++* | QTVUWPO^*//*N |
M | ++* | QTVUWPO^*//*NM |
- | ++- | QTVUWPO^*//*NM* |
L | ++- | QTVUWPO^*//*NM*L |
+ | ++-+ | QTVUWPO^*//*NM*L |
K | ++-+ | QTVUWPO^*//*NM*LK |
|
| QTVUWPO^*//*NM*LK+-++ |
The compiler prefers to evaluate an expression in its postfix form in Infix To Postfix Conversion Using Stack. The advantages of the postfix form include the deletion of parentheses, which indicate evaluation priority, as well as the elimination of the requirement to follow hierarchy, precedence, and associativity rules when evaluating the expression.
Because Postfix expressions have no parenthesis and may be evaluated as two operands and an operator at a time, the compiler and computer can handle them more easily.
A Postfix Expression's evaluation rule is as follows:
- While reading the expression from left to right, push the element in the stack if it is an operand.
- Pop the two operands from the stack, if the element is an operator and then evaluate it.
- Push back the result of the evaluation. Repeat it till the end of the expression.
Algorithm
1) Add ) to postfix expression.
2) Read postfix expression Left to Right until ) encountered
3) If operand is encountered, push it onto Stack
[End If]
4) If operator is encountered, Pop two elements
i) A -> Top element
Ii) B-> Next to Top element
Iii) Evaluate B operator A
Push B operator A onto Stack
5) Set result = pop
6) END
Example
Expression: 456*+
Result: 34
Key takeaway
The compiler prefers to evaluate an expression in its postfix form in Infix To Postfix Conversion Using Stack.
The advantages of the postfix form include the deletion of parentheses, which indicate evaluation priority, as well as the elimination of the requirement to follow hierarchy, precedence, and associativity rules when evaluating the expression.
A linear queue is a data structure that prioritises serving the request that arrived first. It is made up of data items that are connected in a linear order. It has two pointers, front and back, where insertion and deletion are done from the front end.
Operations on Linear Queue
On a linear queue, there are two operations that can be performed:
● Enqueue: The enqueue operation adds a new element from the back end to the front end.
● Dequeue: This operation is used to remove an existing element from the queue's front end.
Enqueue
Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
Step 1 − Check if the queue is full.
Step 2 − If the queue is full, produce overflow error and exit.
Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
Step 4 − Add data element to the queue location, where the rear is pointing.
Step 5 − return success.
Insert Operation
Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen situations.
Algorithm for enqueue operation
Procedure enqueue(data)
If queue is full
Return overflow
Endif
Rear ← rear + 1
Queue[rear] ← data
Return true
End procedure
Implementation of enqueue () in C programming language −
Example
Int enqueue (int data)
If (isfull ())
Return 0;
Rear = rear + 1;
Queue[rear] = data;
Return 1;
End procedure
Dequeue
Accessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access. The following steps are taken to perform dequeue operation −
Step 1 − Check if the queue is empty.
Step 2 − If the queue is empty, produce underflow error and exit.
Step 3 − If the queue is not empty, access the data where front is pointing.
Step 4 − Increment front pointer to point to the next available data element.
Step 5 − Return success.
Remove Operation
Algorithm for dequeue operation
Procedure dequeue
If queue is empty
Return underflow
End if
Data = queue[front]
Front ← front + 1
Return true
End procedure
Implementation of dequeue () in C programming language −
Example
Int dequeue () {
If (isempty ())
Return 0;
Int data = queue[front];
Front = front + 1;
Return data;
}
Key takeaway
A linear queue is a data structure that prioritises serving the request that arrived first. It is made up of data items that are connected in a linear order. It has two pointers, front and back, where insertion and deletion are done from the front end.
Why was the concept of the circular queue introduced?
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 the 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.
Fig: Circular queue
As we can see in the above image, the rear is at the last position of the Queue and the front is pointing somewhere rather than the 0th position. In the above array, there are only two elements and the other three positions are empty. 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. 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. 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.
What is a Circular Queue?
A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle except that the last position is connected to the first position in a circular queue that forms a circle. It is also known as a Ring Buffer.
Operations on Circular Queue
The following are the operations that can be performed on a circular queue:
● Front: It is used to get the front element from the Queue.
● Rear: It is used to get the rear element from the Queue.
● enQueue(value): This function is used to insert the new value in the Queue. The new element is always inserted from the rear end.
● deQueue(): This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end.
Applications of Circular Queue
The circular Queue can be used in the following scenarios:
● Memory management: The circular queue provides memory management. As we have already seen in the linear queue, the memory is not managed very efficiently. But in case of a circular queue, the memory is managed efficiently by placing the elements in a location which is unused.
● CPU Scheduling: The operating system also uses the circular queue to insert the processes and then execute them.
● Traffic system: In a computer-control traffic system, traffic lights are one of the best examples of the circular queue. Each traffic light gets ON one by one after every interval of time. Like red light gets ON for one minute then yellow light for one minute and then green light. After the green light, the red light gets ON.
Key takeaway
A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle except that the last position is connected to the first position in a circular queue that forms a circle. It is also known as a Ring Buffer.
Priority Queue
What is a 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 from least to the greatest. Therefore, the 1 number would be having the highest priority while 22 will be having the lowest priority.
Characteristics of a Priority queue
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.
Let's understand the priority queue through an example.
We have a priority queue that contains the following values:
1, 3, 4, 8, 14, 22
All the values are arranged in ascending order. Now, we will observe how the priority queue will look after performing the following operations:
● poll(): This function will remove the highest priority element from the priority queue. In the above priority queue, the '1' element has the highest priority, so it will be removed from the priority queue.
● add(2): This function will insert the '2' element in a priority queue. As 2 is the smallest element among all the numbers so it will obtain the highest priority.
● poll(): It will remove the '2' element from the priority queue as it has the highest priority queue.
● add(5): It will insert 5 elements after 4 as 5 is larger than 4 and lesser than 8, so it will obtain the third highest priority in a priority queue.
Types of Priority Queue
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.
Representation of priority queue
Now, we will see how to represent the priority queue through a one-way list.
We will create the priority queue by using the list given below in which INFO list contains the data elements, PRN list contains the priority numbers of each data element available in the INFO list, and LINK basically contains the address of the next node.
Let's create the priority queue step by step.
In the case of priority queue, lower priority number is considered the higher priority, i.e., lower priority number = higher priority.
Step 1: In the list, lower priority number is 1, whose data value is 333, so it will be inserted in the list as shown in the below diagram:
Step 2: After inserting 333, priority number 2 is having a higher priority, and data values associated with this priority are 222 and 111. So, this data will be inserted based on the FIFO principle; therefore 222 will be added first and then 111.
Step 3: After inserting the elements of priority 2, the next higher priority number is 4 and data elements associated with 4 priority numbers are 444, 555, 777. In this case, elements would be inserted based on the FIFO principle; therefore, 444 will be added first, then 555, and then 777.
Step 4: After inserting the elements of priority 4, the next higher priority number is 5, and the value associated with priority 5 is 666, so it will be inserted at the end of the queue.
Implementation of Priority Queue
The priority queue can be implemented in four ways that include arrays, linked list, heap data structure and binary search tree. The heap data structure is the most efficient way of implementing the priority queue, so we will implement the priority queue using a heap data structure in this topic. Now, first we understand the reason why heap is the most efficient way among all the other data structures.
Key takeaway
In the queue, the insertion takes place from one end while the deletion takes place from another end.
The input-restricted queue means that some restrictions are applied to the insertion.
The output-restricted queue means that some restrictions are applied to the deletion operation.
References:
- Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J. Augenstein, “Data Structures Using C and C++”, PHI Learning Private Limited, Delhi India
- Horowitz and Sahani, “Fundamentals of Data Structures”, Galgotia Publications Pvt Ltd Delhi India.
- Lipschutz, “Data Structures” Schaum’s Outline Series, Tata McGraw-hill Education (India) Pvt. Ltd.
- Thareja, “Data Structure Using C” Oxford Higher Education.
- AK Sharma, “Data Structure Using C”, Pearson Education India.
