UNIT II

What is a stack?

A stack is a sequence of items that are accessible at only one end of the
sequence. It is an ordered group of homogeneous items or elements. Elements
are added to and removed from a specially designated end called the top of the
stack (the most recently added items are at the top of the stack). The last
element to be added is the first to be removed (LIFO: Last In, First Out). In
other words, a stack is a restricted linear list in which all additions and
deletions are made at one end, the top. If we insert a series of data items into
a stack and then remove them, the order of the data is reversed. This reversing
attribute is why stacks are known as last in, first out (LIFO) data
structures. Figure 7.2 shows a computer stack which also indicates that an
insertion at the Top into this restricted list is called Push and deletion also at the
Top is called POP.

As already stated we assume that all elements of a stack are homogenous that is
they are all of the same type. However the elements are unordered and are
placed in the stack in the order in which they are inserted. Multiple Occurrences
of the same elements is permitted as per the characteristics of the stack. The
stack allows unidirectional access (LIFO(Last in First Out) / FILO(First In Last
Out)) through the current Stack Top Pointer (Stack_Pointer).

Stack ADT

The Stack Abstract Data Type (Stack ADT) is a collection of data together
with the operations on that data. We will now formally define the interface of
the collection. The interface of the collection tells us what we need to know in
order to interact with it, i.e. how to use the operations associated with the stack.
The stack can be specified by the user by defining
 Max_Items – Maximum number of items that might be on the stack and
ItemType– Data type of the items on the stack.

ADT stack operations

The next step in defining the Stack ADT is to list the set of operations
associated with the ADT. In this section we will list all the operations generally
associated with stacks. However we have to remember that the actual set of
operations depend on the application for which the Stack ADT will be used and
therefore the operations necessary for that application.

The first operation associated with any ADT is the creation of an empty ADT.
Therefore we will first define the operation of creating an empty Stack. In some
cases we may want to destroy the entire stack and hence that is the next
operation we will define. A very important operation for many applications of
stack is to have an operation to check whether a stack is empty. Then the stack
will normally be associated with operations to add and remove elements from it.
Finally there may be an operation to retrieve the top element from the stack
without removing it. From the ADT perspective a program can use a stack
independently of the stack’s implementation.

Now let us describe in a little more in detail four important operations

associated with the stack. They are:

 bool isEmpty – This is a Boolean operation that checks whether a stack

is empty and signals a true value if the stack is empty.
 push (ItemType newItem) – This is the push operation that adds a new
item newItem of type ItemType to the stack.
 pop () – This is the pop operation where we remove from the Stack, the
item that has been added most recently. In this definition of pop we do not
output the item removed, we just change the contents of the stack.
 top() – This returns the last inserted element without removing it in other
words gets the item that was added to stack most recently.

In addition to the most important operations described above, a set of auxiliary

stack operations are also described below which will be part of the definition of
a Stack ADT depending on the application. These auxiliary operations are
described below:

 size() – This returns the number of elements that is currently available in

the stack
 Create – This operation creates an Empty Stack with Stack Pointer (top)
pointing to null and the number of Stack Elements set to 0
 Check if Full – This is a Boolean operation that will be true when the
number of Elements = maximum number of elements allowed. However this
operation is valid only for array based Implementation.

[Link] of an Empty Stack

This stack operation CreateStack(stackname) creates an empty stack

2. Checking whether Stack is Empty
Returns true if stack is empty else false

int IsEmpty(Stack S)
{
if(Top==-1)
return 1;
}
3. Push Operation
The push operation inserts an item at the top of the stack . Here the push
operation is called with the push(stackName,dataitem)
Push(stack1,40)

Void Push(int X, Stack S)

{
If(IsFull(S)) Error (“Stack is Full”);
Else
{
Top= Top+1;
S[Top] =X;
}
int IsFull(Stack S)
{
if(Top==Arraysize)
return (1);
 }
}
4. POP Operation

The pop operation removes an item from the top of the stack . Here the pop
operation is called with the stack (stackName) from which deletion is to be
done. The element dataItem is returned and is the item that has been removed.

Void Pop(Stack S)
{
if(IsEmpty(S)) Error(“Stack is Empty”);
Else
{
X=S[Top];
Top= Top-1;
}
}
5. Top Operation
It gives the details of the stackTop. In this case the input given is the same as
Pop that is stackTop however this operation retrieves the element at the top
without deleting it.

int TopElement(Stack S)
{
if(!IsEmpty(S))
return S[Top];
else
Error(“Empty Stack”);
return 0; }
Applications of Stacks

Stack is one ADT that is widely used in many areas of computing. There are
some direct applications of stacks.
 These include keeping track of Page-visited history in a Web browser
 Undoing the sequence of operations in a text editor,
 keeping track of the chain of method calls in the Java Virtual Machine
or C++ runtime environment, etc..
  Stacks are useful for any kind of problem involving Last-in-First-Out
or LIFO data. One such example is in Backtracking which is a
common situation in puzzles and games.
 Another application of stacks is in Word Processors, editors where
stacks are used to check expressions or strings of text for matching
parentheses / brackets e.g. if (a == b) { c= (d + e) * f;}
 Stacks are also used with Markup languages (e.g. HTML, XML):
which have formatting information (tags) that need matching

Arithmetic Expression Evaluation

The stack organization is very effective in evaluating arithmetic expressions.
Expressions are usually represented in what is known as Infix notation, in
which each operator is written between two operands (i.e., A + B). With this
notation, we must distinguish between ( A + B )*C and A + ( B * C ) by using
either parentheses or some operator-precedence convention. Thus, the order of
operators and operands in an arithmetic expression does not uniquely determine
the order in which the operations are to be performed.
1. Polish notation (prefix notation) –
It refers to the notation in which the operator is placed before its two operands.
Here no parentheses are required, i.e.,
+AB
2. Reverse Polish notation(postfix notation) –
It refers to the analogous notation in which the operator is placed after its two
operands. Again, no parentheses is required in Reverse Polish notation, i.e.,
AB+
Stack-organized computers are better suited for post-fix notation than the
traditional infix notation. Thus, the infix notation must be converted to the
postfix notation. The conversion from infix notation to postfix notation must
take into consideration the operational hierarchy.
There are 3 levels of precedence for 5 binary operators as given below:
Highest: Exponentiation (^)
Next highest: Multiplication (*) and division (/)
Lowest: Addition (+) and Subtraction (-)
For example –
Infix notation: (A-B)*[C/(D+E)+F]
Post-fix notation: AB- CDE +/F +*
Here, we first perform the arithmetic inside the parentheses (A-B) and (D+E).
The division of C/(D+E) must be done prior to the addition with F. After that
multiply the two terms inside the parentheses and bracket.
 Now we need to calculate the value of these arithmetic operations by using a
stack.
The procedure for getting the result is:
1. Convert the expression in Reverse Polish notation( post-fix notation).
2. Push the operands into the stack in the order they appear.
3. When any operator encounters then pop two topmost operands for
executing the operation.
4. After execution push the result obtained into the stack.
5. After the complete execution of expression, the final result remains on the
top of the stack.
For example –
Infix notation: (2+4) * (4+6)
Post-fix notation: 2 4 + 4 6 + *
Result: 60
The stack operations for this expression evaluation is shown below:

EXAMPLES FOR INFIX TO PREFIX AND POSTFIX

A+B*C+D ++A*BCD ABC*+D+

A + B) * (C + D) *+AB+CD AB+CD+*
A*B+C*D +*AB*CD AB*CD*+
A+B+C+D +++ABCD AB+C+D+

Conversion of Infix expression to Postfix expression


.
Infix expression: The expression of the form “a operator b” (a + b) i.e., when
an operator is in-between every pair of operands.
Postfix expression: The expression of the form “a b operator” (ab+) i.e., When
every pair of operands is followed by an operator.
Examples:
Input: A + B * C + D
Output: ABC*+D+
Input: ((A + B) – C * (D / E)) + F
Output: AB+CDE/*-F+
Why postfix representation of the expression?
The compiler scans the expression either from left to right or from right to
left.
Consider the expression: a + b * c + d
 The compiler first scans the expression to evaluate the expression b * c,
then again scans the expression to add a to it.
 The result is then added to d after another scan.
The repeated scanning makes it very inefficient. Infix expressions are easily
readable and solvable by humans whereas the computer cannot differentiate
the operators and parenthesis easily so, it is better to convert the expression to
postfix(or prefix) form before evaluation.
The corresponding expression in postfix form is abc*+d+. The postfix
expressions can be evaluated easily using a stack.

How to convert an Infix expression to a Postfix expression?

To convert infix expression to postfix expression, use the stack data structure.
Scan the infix expression from left to right. Whenever we get an operand, add
it to the postfix expression and if we get an operator or parenthesis add it to
the stack by maintaining their precedence.
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.

Queue ADT

What is a Queue?
Queue is a linear data structure in which the insertion and deletion operations
are performed at two different ends. In a queue data structure, adding and
removing elements are performed at two different positions. The insertion is
performed at one end and deletion is performed at another end. In a queue data
structure, the insertion operation is performed at a position which is known as
'rear' and the deletion operation is performed at a position which is known as
'front'. In queue data structure, the insertion and deletion operations are
performed based on FIFO (First In First Out) principle.

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

1. Array Representation of Queue:

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

2. Linked List Representation of Queue:

A queue can also be represented using following entities:

 Linked-lists, Pointers, and Structures.

TYPES OF QUEUE

1. Input Restricted Queue: This is a simple queue. In this type of queue,

the input can be taken from only one end but deletion can be done from any
of the ends.
2. Output Restricted Queue: This is also a simple queue. In this type of
queue, the input can be taken from both ends but deletion can be done from
only one end.
3. Circular Queue: This is a special type of queue where the last position
is connected back to the first position. Here also the operations are
performed in FIFO order.
4. Double-Ended Queue (Dequeue): In a double-ended queue the
insertion and deletion operations, both can be performed from both ends.
5. Priority Queue: A priority queue is a special queue where the elements
are accessed based on the priority assigned to them. To know more refer

Basic Operations for Queue in Data Structure:

Some of the basic operations for Queue in Data Structure are:
1. Enqueue() – Adds (or stores) an element to the end of the queue..
2. Dequeue() – Removal of elements from the queue.
3. Peek() or front()- Acquires the data element available at the front node
of the queue without deleting it.
4. rear() – This operation returns the element at the rear end without
removing it.
5. isFull() – Validates if the queue is full.
6. isNull() – Checks if the queue is empty.
1. Enqueue():
Enqueue() operation in Queue adds (or stores) an element to the end of the
queue.
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, return overflow error and exit.
 Step 3: If the queue is not full, increment the rear pointer to point to the
next empty space.
 Step 4: Add the data element to the queue location, where the rear is
pointing.
 Step 5: return success.

2. Dequeue():
Removes (or access) the first element from the queue.
The following steps are taken to perform the dequeue operation:
 Step 1: Check if the queue is empty.
 Step 2: If the queue is empty, return the underflow error and exit.
 Step 3: If the queue is not empty, access the data where the front is
pointing.
 Step 4: Increment the front pointer to point to the next available data
element.
 Step 5: The Return success.
3. front():
This operation returns the element at the front end without removing it.
4. rear():
This operation returns the element at the rear end without removing it.
5. isEmpty():
This operation returns a boolean value that indicates whether the queue is
empty or not
6. isFull():
This operation returns a boolean value that indicates whether the queue is full
or not.

Circular Queue:
A Circular Queue is an extended version of a normal queue where the last
element of the queue is connected to the first element of the queue forming a
circle.
The operations are performed based on FIFO (First In First Out) principle. It is
also called ‘Ring Buffer’.

Operations on Circular Queue:

 Front: Get the front item from the queue.
 Rear: Get the last item from the queue.
 enQueue(value) This function is used to insert an element into the
circular queue. In a circular queue, the new element is always inserted at
the rear position.
 Check whether the queue is full – [i.e., the rear end is in just
before the front end in a circular manner].
 If it is full then display Queue is full.
 If the queue is not full then, insert an element at the end
of the queue.
 deQueue() This function is used to delete an element from the circular
queue. In a circular queue, the element is always deleted from the front
position.
 Check whether the queue is Empty.
 If it is empty then display Queue is empty.
 If the queue is not empty, then get the last element and
remove it from the queue.
How to Implement a Circular Queue?
A circular queue can be implemented using two data structures:
 Array
 Linked List
Here we have shown the implementation of a circular queue using an array
data structure.
Implement Circular Queue using Array:
1. Initialize an array queue of size n, where n is the maximum number of
elements that the queue can hold.
2. Initialize two variables front and rear to -1.
3. Enqueue: To enqueue an element x into the queue, do the following:
 Increment rear by 1.
 If rear is equal to n, set rear to 0.
 If front is -1, set front to 0.
 Set queue[rear] to x.
4. Dequeue: To dequeue an element from the queue, do the following:
 Check if the queue is empty by checking if front is -1.
 If it is, return an error message indicating that the queue is
empty.
 Set x to queue[front].
 If front is equal to rear, set front and rear to -1.
 Otherwise, increment front by 1 and if front is equal to n,
set front to 0.
 Return x.
Applications of Circular Queue:
1. Memory Management: The unused memory locations in the case of
ordinary queues can be utilized in circular queues.
2. Traffic system: In computer controlled traffic system, circular queues
are used to switch on the traffic lights one by one repeatedly as per the time
set.
3. CPU Scheduling: Operating systems often maintain a queue of
processes that are ready to execute or that are waiting for a particular event
to occur.
What is a Deque (or double-ended queue)

The deque stands for Double Ended Queue. Deque is a linear data structure
where the insertion and deletion operations are performed from both ends. We
can say that deque is a generalized version of the queue.

Though the insertion and deletion in a deque can be performed on both ends, it
does not follow the FIFO rule. The representation of a deque is given as follows
-

Types of deque

There are two types of deque -

o Input restricted queue

o Output restricted queue

Input restricted Queue

In input restricted queue, insertion operation can be performed at only one end,
while deletion can be performed from both ends.

Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end,
while insertion can be performed from both ends.
Operations performed on deque

There are the following operations that can be applied on a deque -

o Insertion at front
o Insertion at rear
o Deletion at front
o Deletion at rear

We can also perform peek operations in the deque along with the operations
listed above. Through peek operation, we can get the deque's front and rear
elements of the deque. So, in addition to the above operations, following
operations are also supported in deque -

o Get the front item from the deque

o Get the rear item from the deque
o Check whether the deque is full or not
o Checks whether the deque is empty or not

Now, let's understand the operation performed on deque using an example.

Insertion at the front end

In this operation, the element is inserted from the front end of the queue. Before
implementing the operation, we first have to check whether the queue is full or
not. If the queue is not full, then the element can be inserted from the front end
by using the below conditions -

o If the queue is empty, both rear and front are initialized with 0. Now, both
will point to the first element.
o Otherwise, check the position of the front if the front is less than 1 (front
< 1), then reinitialize it by front = n - 1, i.e., the last index of the array.
Insertion at the rear end

In this operation, the element is inserted from the rear end of the queue. Before
implementing the operation, we first have to check again whether the queue is
full or not. If the queue is not full, then the element can be inserted from the rear
end by using the below conditions -

o If the queue is empty, both rear and front are initialized with 0. Now, both
will point to the first element.
o Otherwise, increment the rear by 1. If the rear is at last index (or size - 1),
then instead of increasing it by 1, we have to make it equal to 0.

Deletion at the front end

In this operation, the element is deleted from the front end of the queue. Before
implementing the operation, we first have to check whether the queue is empty
or not.
If the queue is empty, i.e., front = -1, it is the underflow condition, and we
cannot perform the deletion. If the queue is not full, then the element can be
inserted from the front end by using the below conditions -

If the deque has only one element, set rear = -1 and front = -1.

Else if front is at end (that means front = size - 1), set front = 0.

Else increment the front by 1, (i.e., front = front + 1).

Deletion at the rear end

In this operation, the element is deleted from the rear end of the queue. Before
implementing the operation, we first have to check whether the queue is empty
or not.
If the queue is empty, i.e., front = -1, it is the underflow condition, and we
cannot perform the deletion.
If the deque has only one element, set rear = -1 and front = -1.
If rear = 0 (rear is at front), then set rear = n - 1.
Else, decrement the rear by 1 (or, rear = rear -1).

Check empty

This operation is performed to check whether the deque is empty or not. If

front = -1, it means that the deque is empty.

Check full
This operation is performed to check whether the deque is full or not.

If front = rear + 1, or front = 0 and rear = n - 1 it means that the deque is full.

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

Applications of deque
o Deque can be used as both stack and queue, as it supports both
operations.
o Deque can be used as a palindrome checker means that if we read the
string from both ends, the string would be the same.

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.
Characteristics of a Priority queue

A priority queue is an extension of a queue that contains the following

characteristics:

o Every element in a priority queue has some priority associated with it.
o An element with the higher priority will be deleted before the deletion of
the lesser priority.
o If two elements in a priority queue have the same priority, they will be
arranged using the FIFO principle.

Types of Priority Queue

There are two types of priority queue:

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

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

Operations of a Priority Queue:

A typical priority queue supports the following operations:
1) Insertion in a Priority Queue
When a new element is inserted in a priority queue, it moves to the empty slot
from top to bottom and left to right. However, if the element is not in the
correct place then it will be compared with the parent node. If the element is
not in the correct order, the elements are swapped. The swapping process
continues until all the elements are placed in the correct position.
2) Deletion in a Priority Queue
As you know that in a max heap, the maximum element is the root node. And
it will remove the element which has maximum priority first. Thus, you
remove the root node from the queue. This removal creates an empty slot,
which will be further filled with new insertion. Then, it compares the newly
inserted element with all the elements inside the queue to maintain the heap
invariant.
3) Peek in a Priority Queue
This operation helps to return the maximum element from Max Heap or the
minimum element from Min Heap without deleting the node from the priority
queue.
APPLICATIONS OF QUEUE :
1. Task Scheduling: Queues can be used to schedule tasks based on
priority or the order in which they were received.
2. Resource Allocation: Queues can be used to manage and allocate
resources, such as printers or CPU processing time.
3. Batch Processing: Queues can be used to handle batch processing jobs,
such as data analysis or image rendering.
4. Message Buffering: Queues can be used to buffer messages in
communication systems, such as message queues in messaging systems or
buffers in computer networks.
5. Event Handling: Queues can be used to handle events in event-driven
systems, such as GUI applications or simulation systems.
6. Traffic Management: Queues can be used to manage traffic flow in
transportation systems, such as airport control systems or road networks.
7. Operating systems: Operating systems often use queues to manage
processes and resources. For example, a process scheduler might use a
queue to manage the order in which processes are executed.
8. Network protocols: Network protocols like TCP and UDP use queues
to manage packets that are transmitted over the network. Queues can help
to ensure that packets are delivered in the correct order and at the
appropriate rate.
9. Printer queues :In printing systems, queues are used to manage the
order in which print jobs are processed. Jobs are added to the queue as they
are submitted, and the printer processes them in the order they were
received.
10. Web servers: Web servers use queues to manage incoming requests
from clients. Requests are added to the queue as they are received, and they
are processed by the server in the order they were received.
11. Breadth-first search algorithm: The breadth-first search algorithm
uses a queue to explore nodes in a graph level-by-level. The algorithm
starts at a given node, adds its neighbors to the queue, and then processes
each neighbor in turn.