lOMoARcPSD|287 285 20

UNIT II - DS Notes

UNIT II STACKS and QUEUES

Stack ADT – Operations – Applications – Evaluating arithmetic

expressions- Conversion of Infix to postfix expression – Queue ADT –
Operations – Circular Queue – Priority Queue – deQueue – Applications
of queues
 lOMoARcPSD|287 285 20

STACK

A stack is an Abstract Data Type (ADT), that is popularly used in most programming languages.
It is named stack because it has the similar operations as the real-world stacks, for example – a
pack of cards or a pile of plates, etc.

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has
one end at any given time, we can only access the top element of a stack, whereas the Queue has
two ends (front and rear). It contains only one pointer top pointer pointing to the topmost
element of the stack. Whenever an element is added in the stack, it is added on the top of the
stack, and the element can be deleted only from the stack. 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.
Some key points related to stack
 It is called as stack because it behaves like a real-world stack, piles of books, etc.
 A Stack is an abstract data type with a pre-defined capacity, which means that it can store
the elements of a limited size.
 It is a data structure that follows some order to insert and delete the elements, and that
order can be LIFO or FILO.

Stack Representation
The following diagram depicts a stack and its operations −

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can
either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to
implement stack using arrays, which makes it a fixed size stack implementation.
 lOMoARcPSD|287 285 20

Basic Operations on Stacks

Stack operations usually are performed for initialization, usage and, de-initialization of the stack
ADT.The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(),
isEmpty(). These are all built-in operations to carry out data manipulation and to check the status
of the stack.Stack uses pointers that always point to the topmost element within the stack, hence
called as the top pointer.

Working of Stack

Stack works on the LIFO pattern. As we can observe in the below figure there are five memory
blocks in the stack; therefore, the size of the stack is 5.
Suppose we want to store the elements in a stack and let's assume that stack is empty. We have
taken the stack of size 5 as shown below in which we are pushing the elements one by one until
the stack becomes full.

Since our stack is full as the size of the stack is 5. In the above cases, we can observe that it goes
from the top to the bottom when we were entering the new element in the stack. The stack gets
filled up from the bottom to the top. When we perform the delete operation on the stack, there is
only one way for entry and exit as the other end is closed. It follows the LIFO pattern, which
means that the value entered first will be removed last. In the above case, the value 5 is entered
first, so it will be removed only after the deletion of all the other elements.

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.'
 peek(): It returns the element at the given position.
 count(): It returns the total number of elements available in a stack.
 change(): It changes the element at the given position.
 display(): It prints all the elements available in the stack.
 lOMoARcPSD|287 285 20

Insertion: push()

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.
 The time complexity for Push operation is O(1). The method for Push will look like this.

Deletion: pop()

pop() is a data manipulation operation which removes elements from the stack.
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.
 The time complexity for Pop operation is O(1).
 lOMoARcPSD|287 285 20

peek()

The peek() is an operation retrieves the topmost element within the stack, without deleting it.
This operation is used to check the status of the stack with the help of the top pointer.

Algorithm

1. START
2. return the element at the top of the stack
3. END

Algorithm
 If the S
 tack is empty, terminate the method as it is Stack underflow.
 If the Stack is not empty, return the element pointed by the top.
 The time complexity for Peek operation is O(1).

isFull()

isFull() operation checks whether the stack is full. This operation is used to check the status of
the stack with the help of top pointer.

Algorithm

1. START
2. If the size of the stack is equal to the top position of the stack, the stack is full. Return 1.
3. Otherwise, return 0.
4. END

isEmpty()

The isEmpty() operation verifies whether the stack is empty. This operation is used to check the
status of the stack with the help of top pointer.

Algorithm

1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END
 lOMoARcPSD|287 285 20

LIFO Principle of Stack

In programming terms, putting an item on top of the stack is called push and removing an item is
called pop.

Stack Push and Pop Operations

In the above image, although item 3 was kept last, it was removed first. This is exactly how
the LIFO (Last In First Out) Principle works.
We can implement a stack in any programming language like C, C++, Java, Python or C#, but
the specification is pretty much the same.

Basic Operations of Stack

There are some basic operations that allow us to perform different actions on a stack.
1. Push: Add an element to the top of a stack
2. Pop: Remove an element from the top of a stack
3. IsEmpty: Check if the stack is empty
4. IsFull: Check if the stack is full
5. Peek: Get the value of the top element without removing it

Working of Stack Data Structure

The operations work as follows:

1. A pointer called TOP is used to keep track of the top element in the stack.
2. When initializing the stack, we set its value to -1 so that we can check if the stack is
empty by comparing TOP == -1.
3. On pushing an element, we increase the value of TOP and place the new element in the
position pointed to by TOP.
4. On popping an element, we return the element pointed to by TOP and reduce its value.
5. Before pushing, we check if the stack is already full
6. Before popping, we check if the stack is already empty
 lOMoARcPSD|287 285 20

Stack Time Complexity

For the array-based implementation of a stack, the push and pop operations take constant time,
i.e. O(1).

Applications of Stack Data Structure

Although stack is a simple data structure to implement, it is very powerful. The most common
uses of a stack are:
1. To reverse a word - Put all the letters in a stack and pop them out. Because of the LIFO
order of stack, you will get the letters in reverse order.
2. In compilers - Compilers use the stack to calculate the value of expressions like 2 + 4 / 5
* (7 - 9) by converting the expression to prefix or postfix form.
3. In browsers - The back button in a browser saves all the URLs you have visited
previously in a stack. Each time you visit a new page, it is added on top of the stack.
When you press the back button, the current URL is removed from the stack, and the
previous URL is accessed.
4. Stack can be used to implement back/forward button in the browser.Undo feature in the
text editors are also implemented using Stack.
5. It is also used to implement recursion.
6. Call and return mechanism for a method uses Stack.
7. It is also used to implement backtracking.
8. Balancing of symbols: Stack is used for balancing a symbol.
For example, we have the following program:
int main()
{
cout<<"Hello";
cout<<"javaTpoint";
}
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.
9. String reversal: Stack is also used for reversing a string. For example, we want to
reverse a "javaTpoint" 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.
10. 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 UNDO operation, and want to achieve 'ab' state, then we
implement pop operation.
11. 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.
12. DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the
stack data structure.
13. Backtracking: Suppose we have to create a path to solve a maze problem. If we are
 lOMoARcPSD|287 285 20

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.
14. 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
15. 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 call 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 completed its execution, all the variables assigned in
the stack are released.

EXPRESSION PARSING

The way to write arithmetic expression is known as a notation. An arithmetic expression can be
written in three different but equivalent notations, i.e., without changing the essence or output of
an expression. These notations are −
 Infix Notation
 Prefix (Polish) Notation
 Postfix (Reverse-Polish) Notation

Infix Notation

We write expression in infix notation, e.g. a - b + c, where operators are used in-between
operands. It is easy for us humans to read, write, and speak in infix notation but the same does
not go well with computing devices. An algorithm to process infix notation could be difficult and
costly in terms of time and space consumption.

Prefix Notation

In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For
example, +ab. This is equivalent to its infix notation a + b. Prefix notation is also known
as Polish Notation.

Postfix Notation

This notation style is known as Reversed Polish Notation. In this notation style, the operator
is postfixed to the operands i.e., the operator is written after the operands. For example, ab+. This
is equivalent to its infix notation a + b.
 lOMoARcPSD|287 285 20

The following table briefly tries to show the difference in all three notations −
S.No. Infix Notation Prefix Notation Postfix Notation
1 a+b +ab ab+
2 (a + b) ∗ c ∗+abc ab+c∗
3 a ∗ (b + c) ∗a+bc abc+∗
4 a/b+c/d +/ab/cd ab/cd/+
5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗
6 ((a + b) ∗ c) - d - ∗+abcd ab+c∗d-

Parsing Expressions

As we have discussed, it is not a very efficient way to design an algorithm or program to parse
infix notations. Instead, these infix notations are first converted into either postfix or prefix
notations and then computed.
To parse any arithmetic expression, we need to take care of operator precedence and
associativity also.

Precedence

When an operand is in between two different operators, which operator will take the operand
first, is decided by the precedence of an operator over others. For example −

As multiplication operation has precedence over addition, b * c will be evaluated first. A table of
operator precedence is provided later.
Associativity
Associativity describes the rule where operators with the same precedence appear in an
expression. For example, in expression a + b − c, both + and – have the same precedence, then
which part of the expression will be evaluated first, is determined by associativity of those
operators. Here, both + and − are left associative, so the expression will be evaluated as (a + b) −
c.
Precedence and associativity determines the order of evaluation of an expression. Following is an
operator precedence and associativity table (highest to lowest) –

S.No. Operator Precedence Associativity

1 Exponentiation ^ Highest Right Associative

2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative

3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative

The above table shows the default behavior of operators. At any point of time in expression
evaluation, the order can be altered by using parenthesis. For example −
In a + b*c, the expression part b*c will be evaluated first, with multiplication as precedence over
addition. We here use parenthesis for a + b to be evaluated first, like (a + b)*c.
 lOMoARcPSD|287 285 20

Postfix Evaluation Algorithm

We shall now look at the algorithm on how to evaluate postfix notation −

Step 1 − scan the expression from left to right
Step 2 − if it is an operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed
Step 6 − pop the stack and perform operation

CONVERT INFIX TO POSTFIX NOTATION

Before understanding the conversion from infix to postfix notation, we should know about the
infix and postfix notations separately.
An infix and postfix are the expressions. An expression consists of constants, variables, and
symbols. Symbols can be operators or parenthesis. All these components must be arranged
according to a set of rules so that all these expressions can be evaluated using the set of rules.

Examples of expressions are:

 5+6
 A- B
 (P * 5)
All the above expressions have a common structure, i.e., we have an operator between the two
operands. An Operand is an object or a value on which the operation is to be performed. In the
above expressions, 5, 6 are the operands while '+', '-', and '*' are the operators.

What is infix notation?

When the operator is written in between the operands, then it is known as infix notation. Operand
does not have to be always a constant or a variable; it can also be an expression itself.

For example:

(p + q) * (r + s)
In the above expression, both the expressions of the multiplication operator are the operands,
i.e., (p + q), and (r + s) are the operands.
In the above expression, there are three operators. The operands for the first plus operator are p
and q, the operands for the second plus operator are r and s. While performing the operations on
the expression, we need to follow some set of rules to evaluate the result. In the above
expression, addition operation would be performed on the two expressions, i.e., p+q and r+s, and
then the multiplication operation would be performed.

Syntax of infix notation is given below:

<operand> <operator> <operand>

If there is only one operator in the expression, we do not require applying any rule. For example,
5 + 2; in this expression, addition operation can be performed between the two operands (5 and
2), and the result of the operation would be 7.
If there are multiple operators in the expression, then some rule needs to be followed to evaluate
the expression.
 lOMoARcPSD|287 285 20

If the expression is:

4+6*2
If the plus operator is evaluated first, then the expression would look like:
10 * 2 = 20
If the multiplication operator is evaluated first, then the expression would look like:
4 + 12 = 16
The above problem can be resolved by following the operator precedence rules. In the algebraic
expression, the order of the operator precedence is given in the below table:

Operators Symbols
Parenthesis ( ), {}, [ ]
Exponents ^
Multiplication and Division *, /
Addition and Subtraction +,-
The first preference is given to the parenthesis; then next preference is given to the exponents. In
the case of multiple exponent operators, then the operation will be applied from right to left.

For example:
2^2^3 = 2 ^ 8
= 256

After exponent, multiplication, and division operators are evaluated. If both the operators are
present in the expression, then the operation will be applied from left to right.
The next preference is given to addition and subtraction. If both the operators are available in the
expression, then we go from left to right.
The operators that have the same precedence termed as operator associativity. If we go from left
to right, then it is known as left-associative. If we go from right to left, then it is known as right-
associative.

Problem with infix notation

To evaluate the infix expression, we should know about the operator precedence rules, and if the
operators have the same precedence, then we should follow the associativity rules. The use of
parenthesis is very important in infix notation to control the order in which the operation to be
performed. Parenthesis improves the readability of the expression. An infix expression is the
most common way of writing expression, but it is not easy to parse and evaluate the infix
expression without ambiguity. So, mathematicians and logicians studied this problem and
discovered two other ways of writing expressions which are prefix and postfix. Both expressions
do not require any parenthesis and can be parsed without ambiguity. It does not require operator
precedence and associativity rules.

Postfix Expression

The postfix expression is an expression in which the operator is written after the operands. For
example, the postfix expression of infix notation ( 2+3) can be written as 23+.
Some key points regarding the postfix expression are:
 In postfix expression, operations are performed in the order in which they have written
from left to right.
 It does not any require any parenthesis.
 We do not need to apply operator precedence rules and associativity rules.
 lOMoARcPSD|287 285 20

Algorithm to evaluate the postfix expression

 Scan the expression from left to right until we encounter any operator.
 Perform the operation
 Replace the expression with its computed value.
 Repeat the steps from 1 to 3 until no more operators exist.
 Let's understand the above algorithm through an

example. Infix expression: 2 + 3 * 4

We will start scanning from the left most of the expression. The multiplication operator is an
operator that appears first while scanning from left to right. Now, the expression would be:

Expression = 2 + 34*
= 2 + 12

Again, we will scan from left to right, and the expression would be:
Expression = 2 12 +
= 14

Evaluation of postfix expression using stack

 Scan the expression from left to right.

 If we encounter any operand in the expression, then we push the operand in the stack.
 When we encounter any operator in the expression, then we pop the corresponding
operands from the stack.
 When we finish with the scanning of the expression, the final value remains in the stack.

Let's understand the evaluation of postfix expression using stack.

Example 1: Postfix expression: 2 3 4 * +
Input Stack
234*+ empty Push 2
34*+ 2 Push 3
4*+ 32 Push 4
*+ 432 Pop 4 and 3, and perform 4*3 = 12. Push 12 into the stack.
+ 12 2 Pop 12 and 2 from the stack, and perform 12+2 = 14. Push 14 into the
stack.
The result of the above expression is 14.
Example 2: Postfix expression: 3 4 * 2 5 * +
Input Stack
3 4 * 2 5 * + empty Push 3
4*25*+ 3 Push 4
*2 5 * + 43 Pop 3 and 4 from the stack and perform 3*4 = 12. Push 12 into
the stack.
25*+ 12 Push 2
5*+ 2 12 Push 5
*+ 5 2 12 Pop 5 and 2 from the stack and perform 5*2 = 10. Push 10 into
the stack.
+ 10 12 Pop 10 and 12 from the stack and perform 10+12 = 22. Push 22

into the stack.

 lOMoARcPSD|287 285 20

The result of the above expression is 22.

Algorithm to evaluate postfix expression

1. Read a character
2. If the character is a digit, convert the character into int and push the integer into the stack.
3. If the character is an operator,
 Pop the elements from the stack twice obtaining two operands.
 Perform the operation
 Push the result into the stack.

Conversion of infix to postfix

Here, we will use the stack data structure for the conversion of infix expression to prefix
expression. Whenever an operator will encounter, we push operator into the stack. If we
encounter an operand, then we append the operand to the expression.

Below are the steps to implement the above idea:

1. Scan the infix expression from left to right.
2. If the scanned character is an operand, put it in the postfix expression.
3. Otherwise, do the following
 If the precedence and associativity of the scanned operator are greater than the
precedence and associativity of the operator in the stack [or the stack is empty or the
stack contains a ‘(‘ ], then push it in the stack. [‘^‘ operator is right associative and other
operators like ‘+‘,’–‘,’*‘ and ‘/‘ are left-associative].
 Check especially for a condition when the operator at the top of the stack and
the scanned operator both are ‘^‘. In this condition, the precedence of the
scanned operator is higher due to its right associativity. So it will be pushed
into the operator stack.
 In all the other cases when the top of the operator stack is the same as the
scanned operator, then pop the operator from the stack because of left
associativity due to which the scanned operator has less precedence.
 Else, Pop all the operators from the stack which are greater than or equal to in
precedence than that of the scanned operator.
 After doing that Push the scanned operator to the stack. (If you encounter
parenthesis while popping then stop there and push the scanned operator
in the stack.)
4. If the scanned character is a ‘(‘, push it to the stack.
5. If the scanned character is a ‘)’, pop the stack and output it until a ‘(‘ is encountered, and
discard both the parenthesis.
6. Repeat steps 2-5 until the infix expression is scanned.
7. Once the scanning is over, Pop the stack and add the operators in the postfix expression
until it is not empty.
8. Finally, print the postfix expression.

Illustration:

Follow the below illustration for a better understanding

Consider the infix expression exp = “a+b*c+d”
and the infix expression is scanned using the iterator i, which is initialized as i = 0.
1st Step: Here i = 0 and exp[i] = ‘a’ i.e., an operand. So add this in the postfix expression.
Therefore, postfix = “a”.
 lOMoARcPSD|287 285 20

2nd Step: Here i = 1 and exp[i] = ‘+’ i.e., an operator. Push this into the stack. postfix =
“a” and stack = {+}.

3rd Step: Now i = 2 and exp[i] = ‘b’ i.e., an operand. So add this in the postfix
expression. postfix = “ab” and stack = {+}.

4th Step: Now i = 3 and exp[i] = ‘*’ i.e., an operator. Push this into the stack. postfix =
“ab” and stack = {+, *}.

Push ‘*’ in the stack

5th Step: Now i = 4 and exp[i] = ‘c’ i.e., an operand. Add this in the postfix expression.
postfix = “abc” and stack = {+, *}.
 lOMoARcPSD|287 285 20

Add ‘c’ in the postfix

6th Step: Now i = 5 and exp[i] = ‘+’ i.e., an operator. The topmost element of the stack has
higher precedence. So pop until the stack becomes empty or the top element has less precedence.
‘*’ is popped and added in postfix. So postfix = “abc*” and stack = {+}.

Pop ‘*’ and add in postfix

Now top element is ‘+‘ that also doesn’t have less precedence. Pop it. postfix = “abc*+”.

Pop ‘+’ and add it in postfix

Now stack is empty. So push ‘+’ in the stack. stack = {+}.

Push ‘+’ in the stack

7th Step: Now i = 6 and exp[i] = ‘d’ i.e., an operand. Add this in the postfix expression.
postfix = “abc*+d”.
 lOMoARcPSD|287 285 20

Final Step: Now no element is left. So empty the stack and add it in the postfix expression.
postfix = “abc*+d+”.

Let's understand through an example.

Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q
Input Expression Stack Postfix Expression
K K
+ +
L + KL
- - K L+
M - K L+ M
* -* K L+ M
N -* KL+MN
+ + K L + M N*
K L + M N* -
( +( K L + M N *-
O +( KL+MN*-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
 lOMoARcPSD|287 285 20

+ + 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+.

QUEUE DATA STRUCTURE

A Queue is also a linear data structure where insertions and deletions are performed from two
different ends. A new element is added from the rear of Queue and deletion of existing element
occurs from the front. Since we can access elements from both ends and the element inserted
first will be the one to be deleted first, hence Queue is called First in First Out data structure
(FIFO).

FIFO Principle of Queue:

 A Queue is like a line waiting to purchase tickets, where the first person in line is the first
person served. (i.e. First come first serve).
 Position of the entry in a queue ready to be served, that is, the first entry that will be
removed from the queue, is called the front of the queue(sometimes, head of the queue),
similarly, the position of the last entry in the queue, that is, the one most recently added, is
called the rear (or the tail) of the queue. See the below figure. 

Characteristics of Queue:
 Queue can handle multiple data.
 We can access both ends.
 They are fast and flexible.

Queue Representation:

Like stacks, Queues can also be represented in an array: In this representation, the Queue is
implemented using the array. Variables used in this case are
 Queue: the name of the array storing queue elements.
 Front: the index where the first element is stored in the array representing the queue.
 Rear: the index where the last element is stored in an array representing the queue.
 lOMoARcPSD|287 285 20

Basic Operations of Queue

A queue is an object (an abstract data structure - ADT) that allows the following operations:
Enqueue: Add an element to the end of the queue
Dequeue: Remove an element from the front of the queue
IsEmpty: Check if the queue is empty
IsFull: Check if the queue is full
Peek: Get the value of the front of the queue without removing it
Working of Queue
Queue operations work as follows:
 two pointers FRONT and REAR
 FRONT track the first element of the queue
 REAR track the last element of the queue
 initially, set value of FRONT and REAR to -1
Enqueue Operation

 check if the queue is full

 for the first element, set the value of FRONT to 0
 increase the REAR index by 1
 add the new element in the position pointed to by REAR
Dequeue Operation
 check if the queue is empty
 return the value pointed by FRONT 
 increase the FRONT index by 1

 for the last element, reset the values of FRONT and REAR to -1
 lOMoARcPSD|287 285 20

Limitations of Queue
As you can see in the image below, after a bit of enqueuing and dequeuing, the size of the queue
has been reduced.

And we can only add indexes 0 and 1 only when the queue is reset (when all the elements have
been dequeued).
After REAR reaches the last index, if we can store extra elements in the empty spaces (0 and 1),
we can make use of the empty spaces. This is implemented by a modified queue called
the circular queue.

Complexity Analysis
The complexity of enqueue and dequeue operations in a queue using an array is O(1). If you
use pop(N) in python code, then the complexity might be O(n) depending on the position of the
item to be popped.
 lOMoARcPSD|287 285 20

Applications of Queue
 CPU scheduling, Disk Scheduling
 When data is transferred asynchronously between two processes.The queue is used for
synchronization. For example: IO Buffers, pipes, file IO, etc
 Handling of interrupts in real-time systems.
 Call Center phone systems use Queues to hold people calling them in order.

Types of Queues
In this tutorial, you will learn different types of queues with along with illustration.
A queue is a useful data structure in programming. It is similar to the ticket queue outside a
cinema hall, where the first person entering the queue is the first person who gets the ticket.
There are four different types of queues:

1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Double Ended Queue

Simple Queue
In a simple queue, insertion takes place at the rear and removal occurs at the front. It strictly
follows the FIFO (First in First out) rule.

Simple Queue Representation

Circular Queue
In a circular queue, the last element points to the first element making a circular link.

The main advantage of a circular queue over a simple queue is better memory utilization. If the
last position is full and the first position is empty, we can insert an element in the first position.
This action is not possible in a simple queue.
A circular queue is the extended version of a regular queue where the last element is connected
to the first element. Thus forming a circle-like structure.

Circular Queue Representation

The circular queue solves the major limitation of the normal queue. In a normal queue, after a bit
of insertion and deletion, there will be non-usable empty space.
 lOMoARcPSD|287 285 20

How Circular Queue Works

Circular Queue works by the process of circular increment i.e. when we try to increment the
pointer and we reach the end of the queue, we start from the beginning of the queue.
Here, the circular increment is performed by modulo division with the queue size. That is,

if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)

Circular Queue Operations

The circular queue work as follows:
 two pointers FRONT and REAR
 FRONT track the first element of the queue
 REAR track the last elements of the queue
 initially, set value of FRONT and REAR to -1

1. Enqueue Operation
 check if the queue is full
 for the first element, set value of FRONT to 0
 circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be
at the start of the queue)
 add the new element in the position pointed to by REAR

2. Dequeue Operation
 check if the queue is empty
 return the value pointed by FRONT
 circularly increase the FRONT index by 1
 for the last element, reset the values of FRONT and REAR to -1

However, the check for full queue has a new additional case:
Case 1: FRONT = 0 && REAR == SIZE - 1
Case 2: FRONT = REAR + 1
The second case happens when REAR starts from 0 due to circular increment and when its value
is just 1 less than FRONT, the queue is full.
lOMoARcPSD|287 285 20
 lOMoARcPSD|287 285 20

Circular Queue Complexity Analysis

The complexity of the enqueue and dequeue operations of a circular queue is O(1) for (array
implementations).
Applications of Circular Queue
 CPU scheduling
 Memory management
 Traffic Management

Priority Queue
A priority queue is a special type of queue in which each element is associated with a priority
and is served according to its priority. If elements with the same priority occur, they are served
according to their order in the queue.

Priority Queue Representation

Insertion occurs based on the arrival of the values and removal occurs based on priority.
A priority queue is a special type of queue in which each element is associated with a priority
value. And, elements are served on the basis of their priority. That is, higher priority elements
are served first.
However, if elements with the same priority occur, they are served according to their order in the
queue.

Assigning Priority Value

Generally, the value of the element itself is considered for assigning the priority. For example,

The element with the highest value is considered the highest priority element. However, in other
cases, we can assume the element with the lowest value as the highest priority element.

Difference between Priority Queue and Normal Queue

In a queue, the first-in-first-out rule is implemented whereas, in a priority queue, the values are
removed on the basis of priority. The element with the highest priority is removed first.
Hence, we will be using the heap data structure to implement the priority queue in this tutorial. A
max-heap is implemented in the following operations. A comparative analysis of different
implementations of priority queue is given below.
 lOMoARcPSD|287 285 20

Operations peek insert delete

Linked List O(1) O(n) O(1)
Binary Heap O(1) O(log n) O(log n)
Binary Search Tree O(1) O(log n) O(log n)

Priority Queue Operations

Basic operations of a priority queue are inserting, removing, and peeking elements.
Before studying the priority queue, please refer to the heap data structure for a better
understanding of binary heap as it is used to implement the priority queue in this article.
1. Inserting an Element into the Priority Queue
Inserting an element into a priority queue (max-heap) is done by the following steps.
Insert the new element at the end of the tree.
Implementation of Priority Queue
Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary
search tree. Among these data structures, heap data structure provides an efficient
implementation of priority queues.

 Insert the new element at the end of the tree

Insert an element at the end of the queue

 Heapify the tree.

Heapify after insertion

Algorithm for insertion of an element into priority queue (max-heap)

If there is no node,
create a newNode.
else (a node is already present)
insert the newNode at the end (last node from left to right.)
heapify the array

For Min Heap, the above algorithm is modified so that parentNode is always smaller
than newNode.
2. Deleting an Element from the Priority Queue
Deleting an element from a priority queue (max-heap) is done as follows:
 Select the element to be deleted
 lOMoARcPSD|287 285 20

Select the element to be deleted

 Swap it with the last element.

Swap with the last leaf node element

 Remove the last element

Remove the last element leaf

 Heapify the tree

Heapify the priority queue

 lOMoARcPSD|287 285 20

Algorithm for deletion of an element

in the priority queue (max-heap)

If nodeToBeDeleted is the leafNode

remove the node
Else swap nodeToBeDeleted with the lastLeafNode
remove noteToBeDeleted
heapify the array

For Min Heap, the above algorithm is modified so that the both childNodes are smaller
than currentNode.
3. Peeking from the Priority Queue (Find max/min)
Peek operation returns the maximum element from Max Heap or minimum element from Min
Heap without deleting the node.
For both Max heap and Min Heap
return rootNode
4. Extract-Max/Min from the Priority Queue
Extract-Max returns the node with maximum value after removing it from a Max Heap whereas
Extract-Min returns the node with minimum value after removing it from Min Heap.
Priority Queue Applications
Some of the applications of a priority queue are:
 Dijkstra's algorithm
 for implementing stack
 for load balancing and interrupt handling in an operating system
 for data compression in Huffman code

Deque (Double Ended Queue):

Deque or Double Ended Queue is a type of queue in which insertion and removal of elements
can either be performed from the front or the rear. Thus, it does not follow FIFO rule (First In
First Out).

Deque Representation
Types of Deque
1. Input Restricted Deque
In this deque, input is restricted at a single end but allows deletion at both the ends.
2. Output Restricted Deque
In this deque, output is restricted at a single end but allows insertion at both the
ends.
 lOMoARcPSD|287 285 20

Operations on a Deque
Below is the circular array implementation of deque. In a circular array, if the array is full, we
start from the beginning.
But in a linear array implementation, if the array is full, no more elements can be inserted. In
each of the operations below, if the array is full, "overflow message" is thrown.
Before performing the following operations, these steps are followed.
1. Take an array (deque) of size n.
2. Set two pointers at the first position and set front = -1 and rear = 0.

Initialize an array and pointers for deque

1. Insert at the Front
 This operation adds an element at the front.

Check the position of front.

 If front < 1, reinitialize front = n-1 (last index).

Shift front to the end

 Else, decrease front by 1.
 lOMoARcPSD|287 285 20

 Add the new key 5 into array[front].

Insert the element at Front

2. Insert at the Rear

This operation adds an element to the rear.
 Check if the array is full.

Check if deque is full

 If the deque is full, reinitialize rear = 0.
 Else, increase rear by 1.

Increase the rear

 Add the new key 5 into array[rear].

Insert the element at rear

3. Delete from the Front
The operation deletes an element from the front.

 Check if the deque is empty.

 lOMoARcPSD|287 285 20

 If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
 If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1.
 Else if front is at the end (i.e. front = n - 1), set go to the front front = 0.
 Else, front = front + 1.

Increase the front

4. Delete from the Rear

This operation deletes an element from the rear.
 Check if the deque is empty.

Check if deque is empty

 If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow
condition).
 If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1, else
follow the steps below.
 If rear is at the front (i.e. rear = 0), set go to the front rear = n - 1.
 Else, rear = rear - 1.

Decrease the rear

5. Check Empty
This operation checks if the deque is empty. If front = -1, the deque is empty.
6. Check Full
This operation checks if the deque is full. If front = 0 and rear = n - 1 OR front = rear + 1, the
deque is full.

Time Complexity
The time complexity of all the above operations is constant i.e. O(1).

Applications of Deque Data Structure

 In undo operations on software.
 To store history in browsers.
 For implementing both stacks and queues.