UNIT 2

STACKS

A Stack is linear data structure. A stack is a list of elements in which an element may be

inserted or deleted only at one end, called the top of the stack. Stack principle is LIFO (last

in, first out). Which element inserted last on to the stack that element deleted first from the

stack. As the items can be added or removed only from the top i.e. the last item to be added to
a stack is the first item to be removed.

Operations on stack:

The two basic operations associated with stacks are:

1. Push

2. Pop

While performing push and pop operations the following test must be conducted on the

stack.

a) Stack is empty or not b) stack is full or not

1. Push: Push operation is used to add new elements in to the stack. At the time of addition

first check the stack is full or not. If the stack is full it generates an error message "stack
overflow".

2. Pop: Pop operation is used to delete elements from the stack. At the time of deletion first

check the stack is empty or not. If the stack is empty it generates an error message "stack

underflow".

All insertions and deletions take place at the same end, so the last element added to

the stack will be the first element removed from the stack. When a stack is created, the

stack base remains fixed while the stack top changes as elements are added and removed.

The most accessible element is the top and the least accessible element is the bottom of the

stack.
Stack Representation in Data Structures

Working of Stack in Data Structures

Now, assume that you have a stack of books.

You can only see the top, i.e., the top-most book, namely 40, which is kept top of the stack.

If you want to insert a new book first, namely 50, you must update the top and then insert a
new text.

And if you want to access any other book other than the topmost book that is 40, you first
remove the topmost book from the stack, and then the top will point to the next topmost book.
After working on the representation of stacks in data structures, you will see some basic
operations performed on the stacks in data structures.

Basic Operations on Stack in Data Structures

There following are some operations that are implemented on the stack.

Push Operation

Push operation involves inserting new elements in the stack. Since you have only one end to
insert a unique element on top of the stack, it inserts the new element at the top of the stack.
Pop Operation

Pop operation refers to removing the element from the stack again since you have only one end
to do all top of the stack. So removing an element from the top of the stack is termed pop
operation.

Array implementation of Stack

In array implementation, the stack is formed by using the array. All the operations regarding
the stack are performed using arrays. Lets see how each operation can be implemented on the
stack using array data structure.

Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push operation. Push operation
involves following two steps.

1. Increment the variable Top so that it can now refere to the next memory location.
2. Add element at the position of incremented top. This is referred to as adding new
element at the top of the stack.
 Stack is overflown when we try to insert an element into a completely filled stack therefore,
our main function must always avoid stack overflow condition.

Algorithm:

1. begin
2. if top = n then stack full
3. top = top + 1
4. stack (top) : = item;
5. end
Deletion of an element from a stack (Pop operation)

Deletion of an element from the top of the stack is called pop operation. The value of the
variable top will be incremented by 1 whenever an item is deleted from the stack. The top most
element of the stack is stored in an another variable and then the top is decremented by 1. the
operation returns the deleted value that was stored in another variable as the result.

The underflow condition occurs when we try to delete an element from an already empty stack

Algorithm :

1. begin
2. if top = 0 then stack empty;
3. item := stack(top);
4. top = top - 1;
5. end;

Visiting each element of the stack (Peek operation)

Peek operation involves returning the element which is present at the top of the stack without
deleting it. Underflow condition can occur if we try to return the top element in an already
empty stack.

Algorithm :

PEEK (STACK, TOP)

1. Begin
2. if top = -1 then stack empty
3. item = stack[top]
4. return item
5. End

Implementation of Stack in Data Structures

You can perform the implementation of stacks in data structures using two data structures that
are an array and a linked list.

 Array: In array implementation, the stack is formed using an array. All the operations are
performed using arrays. You will see how all operations can be implemented on the stack
in data structures using an array data structure.

 Linked-List: Every new element is inserted as a top element in the linked list
implementation of stacks in data structures. That means every newly inserted element is
pointed to the top. Whenever you want to remove an element from the stack, remove the
node indicated by the top, by moving the top to its previous node in the list.
Application of Stack in Data Structures

Here are the top 7 applications of the stack in data structure:

 Expression Evaluation and Conversion

 Backtracking

 Function Call

 Parentheses Checking

 String Reversal

 Syntax Parsing

 Memory Management

Now you will understand all the applications one at a time.

[Link] Evaluation and conversion

Infix Expressions
Infix expressions are mathematical expressions where the operator is placed
between its operands. This is the most common mathematical notation used by
humans. For example, the expression “2 + 3” is an infix expression, where the
operator “+” is placed between the operands “2” and “3”.
Infix notation is easy to read and understand for humans, but it can be difficult for
computers to evaluate efficiently. This is because the order of operations must be
taken into account, and parentheses can be used to override the default order of
operations.
Common way of writing Infix expressions:
 Infix notation is the notation that we are most familiar with. For example, the
expression “2 + 3” is written in infix notation.
 In infix notation, operators are placed between the operands they operate on.
For example, in the expression “2 + 3”, the addition operator “+” is placed
between the operands “2” and “3”.
 Parentheses are used in infix notation to specify the order in which operations
should be performed. For example, in the expression “(2 + 3) * 4”, the
parentheses indicate that the addition operation should be performed before the
multiplication operation.
Operator precedence rules:
Infix expressions follow operator precedence rules, which determine the order in
which operators are evaluated. For example, multiplication and division have
higher precedence than addition and subtraction. This means that in the expression
“2 + 3 * 4”, the multiplication operation will be performed before the addition
operation.
Here’s the table summarizing the operator precedence rules for common
mathematical operators:

Operator Precedence

Parentheses () Highest

Exponents ^ High

Multiplication * Medium
Operator Precedence

Division / Medium

Addition + Low

Subtraction – Low

Evaluating Infix Expressions

Evaluating infix expressions requires additional processing to handle the order of
operations and parentheses. First convert the infix expression to postfix notation.
This can be done using a stack or a recursive algorithm. Then evaluate the postfix
expression.
refix Expressions (Polish Notation)
Prefix expressions are also known as Polish notation, are a mathematical notation
where the operator precedes its operands. This differs from the more common infix
notation, where the operator is placed between its operands.
In prefix notation, the operator is written first, followed by its operands. For
example, the infix expression “a + b” would be written as “+ a b” in prefix notation.
Postfix Expressions (Reverse Polish Notation)
Postfix expressions are also known as Reverse Polish Notation (RPN), are a
mathematical notation where the operator follows its operands. This differs from
the more common infix notation, where the operator is placed between its
operands.
In postfix notation, operands are written first, followed by the operator. For
example, the infix expression “5 + 2” would be written as “5 2 +” in postfix
notation.

2. Backtracking

Backtracking is a recursive algorithm mechanism that is used to solve optimization problems.

To solve the optimization problem with backtracking, you have multiple solutions; it does not
matter if it is correct. While finding all the possible solutions in backtracking, you store the
previously calculated problems in the stack and use that solution to resolve the following issues.

The N-queen problem is an example of backtracking, a recursive algorithm where the stack is
used to solve this problem.

3. Function Call

Whenever you call one function from another function in programming, the reference of calling
function stores in the stack. When the function call is terminated, the program control moves
back to the function call with the help of references stored in the stack.

4. Parentheses Checking

Stack in data structures is used to check if the parentheses like ( ), { } are valid or not in
programing while matching opening and closing brackets are balanced or not.

So it stores all these parentheses in the stack and controls the flow of the program.

For e.g ((a + b) * (c + d)) is valid but {{a+b})) *(b+d}] is not valid.

5. String Reversal

Another exciting application of stack is string reversal. Each character of a string gets stored
in the stack.

The string's first character is held at the bottom of the stack, and the last character of the string
is held at the top of the stack, resulting in a reversed string after performing the pop operation.

6. Syntax Parsing

Since many programming languages are context-free languages, the stack is used for syntax
parsing by many compilers.
7. Memory Management

Memory management is an essential feature of the operating system, so the stack is heavily
used to manage memory.

Queue
Queue is the data structure that is similar to the queue in the real world. A queue is a data
structure in which whatever comes first will go out first, and it follows the FIFO (First-In-First-
Out) policy. Queue can also be defined as the list or collection in which the insertion is done
from one end known as the rear end or the tail of the queue, whereas the deletion is done from
another end known as the front end or the head of the queue.

The real-world example of a queue is the ticket queue outside a cinema hall, where the person
who enters first in the queue gets the ticket first, and the last person enters in the queue gets the
ticket at last. Similar approach is followed in the queue in data structure.

Applications of Queue
Due to the fact that queue performs actions on first in first out basis which is quite fair for the
ordering of actions. There are various applications of queues discussed as below.

1. Queues are widely used as waiting lists for a single shared resource like printer, disk,
CPU.
2. Queues are used in asynchronous transfer of data (where data is not being transferred
at the same rate between two processes) for eg. pipes, file IO, sockets.
3. Queues are used as buffers in most of the applications like MP3 media player, CD
player, etc.
4. Queue are used to maintain the play list in media players in order to add and remove
the songs from the play-list.
5. Queues are used in operating systems for handling interrupts.
Types of Queue

o Simple Queue or Linear Queue

o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)

Let's discuss each of the type of queue.

Simple Queue or Linear Queue

In Linear Queue, an insertion takes place from one end while the deletion occurs from another
end. The end at which the insertion takes place is known as the rear end, and the end at which
the deletion takes place is known as front end. It strictly follows the FIFO rule.

The major drawback of using a linear Queue is that insertion is done only from the rear end. If
the first three elements are deleted from the Queue, we cannot insert more elements even
though the space is available in a Linear Queue. In this case, the linear Queue shows the
overflow condition as the rear is pointing to the last element of the Queue.

Circular Queue
In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue
except that the last element of the queue is connected to the first element. It is also known as
Ring Buffer, as all the ends are connected to another end. The representation of circular queue
is shown in the below image -

The drawback that occurs in a linear queue is overcome by using the circular queue. If the
empty space is available in a circular queue, the new element can be added in an empty space
by simply incrementing the value of rear. The main advantage of using the circular queue is
better memory utilization.

Priority Queue
It is a special type of queue in which the elements are arranged based on the priority. It is a
special type of queue data structure in which every element has a priority associated with it.
Suppose some elements occur with the same priority, they will be arranged according to the
FIFO principle. The representation of priority queue is shown in the below image -

Insertion in priority queue takes place based on the arrival, while deletion in the priority queue
occurs based on the priority. Priority queue is mainly used to implement the CPU scheduling
algorithms.

There are two types of priority queue that are discussed as follows -

o Ascending priority queue - In ascending priority queue, elements can be inserted in

arbitrary order, but only smallest can be deleted first. Suppose an array with elements
7, 5, and 3 in the same order, so, insertion can be done with the same sequence, but the
order of deleting the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements can be inserted in
arbitrary order, but only the largest element can be deleted first. Suppose an array with
elements 7, 3, and 5 in the same order, so, insertion can be done with the same sequence,
but the order of deleting the elements is 7, 5, 3.
Deque (or, Double Ended Queue)
In Deque or Double Ended Queue, insertion and deletion can be done from both ends of the
queue either from the front or rear. It means that we can insert and delete elements from both
front and rear ends of the queue. Deque can be used as a palindrome checker means that if we
read the string from both ends, then the string would be the same.

Deque can be used both as stack and queue as it allows the insertion and deletion operations
on both ends. Deque can be considered as stack because stack follows the LIFO (Last In First
Out) principle in which insertion and deletion both can be performed only from one end. And
in deque, it is possible to perform both insertion and deletion from one end, and Deque does
not follow the FIFO principle.

The representation of the deque is shown in the below image -

There are two types of deque that are discussed as follows -

o Input restricted deque - As the name implies, in input restricted queue, insertion
operation can be performed at only one end, while deletion can be performed from both
ends.

o Output restricted deque - As the name implies, in output restricted queue, deletion
operation can be performed at only one end, while insertion can be performed from
 both ends.

Now, let's see the operations performed on the queue.

Operations performed on queue

The fundamental operations that can be performed on queue are listed as follows -

o Enqueue: The Enqueue operation is used to insert the element at the rear end of the queue. It
returns void.
o Dequeue: It performs the deletion from the front-end of the queue. It also returns the element
which has been removed from the front-end. It returns an integer value.
o Peek: This is the third operation that returns the element, which is pointed by the front pointer
in the queue but does not delete it.
o Queue overflow (isfull): It shows the overflow condition when the queue is completely full.
o Queue underflow (isempty): It shows the underflow condition when the Queue is empty, i.e.,
no elements are in the Queue.

Array representation of Queue

We can easily represent queue by using linear arrays. There are two variables i.e. front and
rear, that are implemented in the case of every queue. Front and rear variables point to the
position from where insertions and deletions are performed in a queue. Initially, the value of
front and queue is -1 which represents an empty queue. Array representation of a queue
containing 5 elements along with the respective values of front and rear, is shown in the
following figure.
The above figure shows the queue of characters forming the English word "HELLO". Since,
No deletion is performed in the queue till now, therefore the value of front remains -1 .
However, the value of rear increases by one every time an insertion is performed in the queue.
After inserting an element into the queue shown in the above figure, the queue will look
something like following. The value of rear will become 5 while the value of front remains
same.

After deleting an element, the value of front will increase from -1 to 0. however, the queue will
look something like following.
Algorithm to insert any element in a queue
Check if the queue is already full by comparing rear to max - 1. if so, then return an overflow
error.

If the item is to be inserted as the first element in the list, in that case set the value of front and
rear to 0 and insert the element at the rear end.

Otherwise keep increasing the value of rear and insert each element one by one having rear as
the index

Algorithm
o Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
o Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
o Step 3: Set QUEUE[REAR] = NUM
o Step 4: EXIT

Algorithm to delete an element from the queue

If, the value of front is -1 or value of front is greater than rear , write an underflow message
and exit.

Otherwise, keep increasing the value of front and return the item stored at the front end of the
queue at each time.
Algorithm
o Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
o Step 2: EXIT