Module 3-Stack

Stack
• A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out
(FILO) manner.
• In stack, a new element is added at one end and an element is removed from that end only. The insert
and delete operations are often called push and pop.
Stack operations

• empty() – Returns whether the stack is empty – Time Complexity: O(1)

• size() – Returns the size of the stack – Time Complexity: O(1)
• top() / peek() – Returns a reference to the topmost element of the stack – Time Complexity:
O(1)
• push(a) – Inserts the element ‘a’ at the top of the stack – Time Complexity: O(1)
• pop() – Deletes the topmost element of the stack – Time Complexity: O(1)
Complexity analysis of different stack operations:

• 1) push():
• This operation pushes an element on top of the stack and the top pointer points to the newly
pushed element.
• It takes one parameter and pushes it onto the stack.
• C:\Users\HP\Desktop\ICREP\materials\ds\mod3\[Link]

• Complexity Analysis:

• Time Complexity: O(1), In the push function a single element is inserted at the last position.
This takes a single memory allocation operation which is done in constant time.
• Auxiliary Space: O(1), As no extra space is being used.
• 1. Push Operation:
• Time Complexity: O(1) (Constant Time)
• Explanation: Adding an element to the top of the stack (push) usually involves a single
operation, like updating a pointer and assigning the value.
• This takes a fixed amount of time regardless of how many elements are already in the stack.

• Exception (Array-based stack): If the stack is implemented using a fixed-size array and it
becomes full, a new, larger array might need to be allocated and all elements copied.
• This "resizing" operation would have a time complexity of O(N) in the worst case, where N is the
number of elements.
• However, this is amortized to O(1) over many operations if the resizing strategy is efficient (e.g.,
doubling the array size).
stack using linked list
• C:\Users\HP\Desktop\ICREP\materials\ds\mod3\[Link]
• Complexity Analysis:
• Time Complexity: O(1), Only a new node is created and the pointer of the last node is
updated. This includes only memory allocation operations. Hence it can be said that insertion
is done in constant time.
• Space Complexity:
• The space complexity of a stack implemented using a linked list is O(n), where 'n' is the
number of elements (nodes) currently in the stack.
• Reasoning:
• Each time an element is pushed onto the stack, a new node is created. This node requires a
fixed amount of memory to store both the data and the pointer. As the number of elements in
the stack increases, the number of nodes increases proportionally, leading to a linear increase
in the total memory used.
• Pointer Overhead:
• A significant aspect of this space complexity is the "pointer overhead." Each node, in addition
to storing the actual data, also consumes memory for its pointer(s) to the next node(s). This
overhead is inherent to linked lists and contributes to the overall space usage.
• 2) pop():
• Using array:
• This operation removes the topmost element in the stack and returns an error if the stack is
already empty.
• C:\Users\HP\Desktop\ICREP\materials\ds\mod3\[Link]

• Complexity Analysis:

• Time Complexity: O(1), In array implementation, only an arithmetic operation is performed i.e.,
the top pointer is decremented by 1. This is a constant time function.
• Auxiliary Space: O(1), No extra space is utilized for deleting an element from the stack.
Pop() using linked list
• C:\Users\HP\Desktop\ICREP\materials\ds\mod3\[Link]

• Complexity Analysis:

• Time Complexity: O(1), Only the first node is deleted and the top pointer is updated. This is a
constant time operation.
• Auxiliary Space: O(1). No extra space is utilized for deleting an element from the stack.
• This is because the pop operation only involves updating a pointer (the head of the linked list)
to the next node and potentially deallocating the memory of the popped node. No
additional auxiliary space is required that scales with the size of the stack. The operation
involves a constant number of steps and does not depend on the number of elements in the
stack.
• 2. Pop Operation:

• Time Complexity: O(1) (Constant Time)

• Explanation: Removing the top element from the stack (pop) also involves a single operation,
like updating a pointer. This takes a fixed amount of time regardless of the stack's size.
3) peek():
• This operation prints the topmost element of the stack.
• peek() using Array:
• C:\Users\HP\Desktop\ICREP\materials\ds\mod3\[Link]

• Complexity Analysis:

• Time Complexity: O(1), Only a memory address is accessed. This is a constant time
operation.
• Auxiliary Space: O(1), No extra space is utilized to access the value.
peek() using Linked List :
• C:\Users\HP\Desktop\ICREP\materials\ds\mod3\[Link]

• Complexity Analysis:

• Time Complexity: O(1). In linked list implementation also a single memory address is accessed.
It takes constant time.
• Auxiliary Space: O(1). No extra space is utilized to access the element because only the value
in the node at the top pointer is read.

• This is because the peek operation only involves accessing the value of the top node (or head
of the linked list) without allocating any new memory or creating any new data structures. It
simply returns the data stored in the existing top node. Therefore, the memory usage remains
constant regardless of the number of elements in the stack.
3. Peek/Top Operation:
• Time Complexity: O(1) (Constant Time)
• Explanation: Accessing the top element without removing it (peek or top) directly accesses
the element pointed to by the top pointer. This is a single, constant-time operation.
4) isempty():
• This operation tells us whether the stack is empty or not.
• isempty() using Array :
• C:\Users\HP\Desktop\ICREP\materials\ds\mod3\[Link]

• Complexity Analysis:

• Time Complexity: O(1), It only performs an arithmetic operation to check if the stack
is empty or not.
• Auxiliary Space: O(1), It requires no extra space.
isempty() using Linked List :
• C:\Users\HP\Desktop\ICREP\materials\ds\mod3\[Link]

• Complexity Analysis:

• Time Complexity: O(1), It checks if the pointer of the top pointer is Null or not. This operation
takes constant time.
• Auxiliary Space: O(1), No extra space is required.
5) size():
• This operation returns the current size of the stack.

• size() using Array:

• C:\Users\HP\Desktop\ICREP\materials\ds\mod3\[Link]

• Complexity Analysis:

• Time Complexity: O(1), because this operation just performs a basic arithmetic operation.
• Auxiliary Space: The space complexity of a stack implemented using a linked list is O(n),
where 'n' represents the number of elements currently stored in the stack.
4. IsEmpty Operation:
• Time Complexity: O(1) (Constant Time)
• Explanation: Checking if the stack is empty typically involves checking the value of the top
pointer or a size counter. This is a single, constant-time operation.
size() using Linked List:
• C:\Users\HP\Desktop\ICREP\materials\ds\mod3\[Link]

• Complexity Analysis:

• Time Complexity: O(1), because the size is calculated and updated every time a push or pop
operation is performed and is just returned in this function.
• Auxiliary Space: The space complexity of a stack implemented using a linked list is O(n),
where 'n' represents the number of elements currently stored in the stack.

• This is because each element added to the stack corresponds to a new node in the linked list.
Each node requires space for the data it holds and a pointer (or reference) to the next node
in the sequence.
• As the number of elements in the stack grows, the number of nodes in the linked list increases
proportionally, leading to a linear relationship between the number of elements and the total
space consumed.
5. Search Operation (if implemented):
• Time Complexity: O(N) (Linear Time)

• Explanation: Stacks are not designed for efficient searching of arbitrary elements.
• To find an element other than the top, you would have to pop elements one by one until you
find the desired element or the stack becomes empty.
• In the worst case, you might have to examine all N elements, leading to O(N) complexity.
Advantages of Stacks:
• Simplicity: Stacks are a simple and easy-to-understand data structure, making them
suitable for a wide range of applications.
• Efficiency: Push and pop operations on a stack can be performed in constant time
(O(1)), providing efficient access to data.
• Last-in, First-out (LIFO): Stacks follow the LIFO principle, ensuring that the last element
added to the stack is the first one removed. This behavior is useful in many scenarios,
such as function calls and expression evaluation.
• Limited memory usage: Stacks only need to store the elements that have been
pushed onto them, making them memory-efficient compared to other data
structures.
Disadvantages of Stacks:
• Limited access: Elements in a stack can only be accessed from the top, making it difficult to
retrieve or modify elements in the middle of the stack.
• Potential for overflow: If more elements are pushed onto a stack than it can hold, an overflow
error will occur, resulting in a loss of data.
• Not suitable for random access: Stacks do not allow for random access to elements, making
them unsuitable for applications where elements need to be accessed in a specific order.
• Limited capacity: Stacks have a fixed capacity, which can be a limitation if the number of
elements that need to be stored is unknown or highly variable.
Applications of stack

• Function calls: Stacks are used to keep track of the return addresses of function calls, allowing
the program to return to the correct location after a function has finished executing.
• Recursion: Stacks are used to store the local variables and return addresses of recursive
function calls, allowing the program to keep track of the current state of the recursion.
• Expression evaluation: Stacks are used to evaluate expressions in postfix notation (Reverse
Polish Notation).
• Syntax parsing: Stacks are used to check the validity of syntax in programming languages and
other formal languages.
• Memory management: Stacks are used to allocate and manage memory in some operating
systems and programming languages.
Polish notation
• Polish notation, also known as prefix notation, is a mathematical notation where operators
precede their operands.
• This contrasts with infix notation (e.g., A + B) and postfix notation (e.g., AB+), also known as
Reverse Polish Notation (RPN).
Polish notation
• 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 (-)
Conversion of Infix Notation:
• This process also utilizes a stack to manage operators and parentheses.
• The algorithm involves scanning the infix expression and pushing operators onto a stack,
respecting operator precedence and associativity rules, to determine their correct placement
in the prefix expression.
• 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.
Conversion of an Infix expression to Postfix expression

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 of the current scanned operator is higher than the precedence of the
operator on top of the stack, or if the stack is empty, or if the stack contains a ‘(‘, then push
the current operator onto the stack.
• Else, pop all operators from the stack that have precedence higher than or equal to that of
the current operator. After that push the current operator onto 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.
• Ex. 2.7.4 : Convert the following infix expression to the postfix expression.
• Show stack traces. i) A/B$C+D*E/F-G+H (ii) (A+B)*D+E/(F+G*D)+C.
• p* q + (r-s/t)
• Following is the pictorial representation of the above logic for the infix expression A*(B*C+D*E)+F:
Polish notations
• 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+

• [Link]

• Time Complexity: O(n), where n is the size of the infix expression

• Auxiliary Space: O(n), where n is the size of the infix expression
Polish notation
• 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.
Conversion of an Infix Expression to Postfix
Expression
• if we take some operators, i.e., +, -, *, /, then these will be arranged in priority.

• Higher Priority Operators : *, /, %.

• Lower Priority Operators : +, -.
• Order of Operators : +, −, ∗, /, ^.
Evaluation of expression
• Now we need to calculate the value of these arithmetic operations by using a stack.

• The procedure for getting the result is:

• Convert the expression in Reverse Polish notation( post-fix notation).

• If an operand is encountered, push it onto the stack.
• If an operator is encountered:
• Pop the required number of operands from the stack.
• Perform the operation.
• Push the result back onto the stack.
• The final result will be the only item remaining on the stack.
The evaluation of a postfix expression
• Algorithm:
• Initialize an empty stack. This stack will be used to store operands during the evaluation.
• Iterate through each token in the postfix expression. Tokens can be either operands (numbers)
or operators (+, -, *, /).
• If the token is an operand: Convert it to an integer (if necessary) and push it onto the stack.
• If the token is an operator:
Pop the top two operands from the stack. The first popped operand will be operand2 and
the second popped operand will be operand1.
• Perform the operation using operand1 and operand2 based on the operator.
• Push the result of the operation back onto the stack.
• After processing all tokens: The final result of the expression will be the only element remaining
on the stack. Pop this value and return it.
Example
• Infix notation: (2+4) * (4+6)
• Prefix:*+24+46
• Post-fix notation: 2 4 + 4 6 + *
• Result: 60
Applications of Polish Notation

• The Polish Notations play a very vital role in evaluating arithmetic expressions for computers
and different types of machines, as they find infix or parenthesized expressions difficult to
parse, whereas they find them easy to parse the postfix or reverse polish notation expressions.

• The modern Stack-organized computers are better suited for postfix and prefix notations than
normally used infix notations due to their difficulty in parsing.

• The compiler can quickly evaluate these expressions without having to scan the expression for
operators first and then for operands, which would require several scans.
• The compiler can then evaluate the expression in one step by converting the Infix expression
to Polish notation.
mathematical expressions
• When parsing mathematical expressions, three types of notations are commonly used : Infix
Notation, Prefix Notation, and Postfix Notation.
• In Infix Notation, the operator is written in between the operands like
• (3+7)
• (3+7), (1∗(2+3))
• (1∗(2+3)).
• In Prefix Notation, the operator should be present as a prefix or before the operands like
• +37
• +37, ∗1(+23)
• ∗1(+23).
• In Postfix Notation, the operator should be present as a suffix, postfix, or after the operands like
• 37+
• 37+, (23+)1∗
(23+)1∗.
• [Link]
Queue

• the queue is a linear data structure that stores items in a

First In First Out (FIFO) manner. With a queue, the least
recently added item is removed first
Operations associated with queue are:

• Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow
condition – Time Complexity : O(1)
• Dequeue: Removes an item from the queue. The items are popped in the same order in which
they are pushed. If the queue is empty, then it is said to be an Underflow condition – Time
Complexity : O(1)
• Front: Get the front item from queue – Time Complexity : O(1)
• Rear: Get the last item from queue – Time Complexity : O(1)
Implement a Queue
• There are various ways to implement a queue in Python.
• Python Queue can be implemented by the following ways:

• list
• [Link]
• [Link]
• Implementation using list
• List is a Python's built-in data structure that can be used as a queue.
• Instead of enqueue() and dequeue(), append() and pop() function is used.
• [Link]
Implementation using [Link]
• Queue in Python can be implemented using deque class from the collections module.
• Deque is preferred over list in the cases where we need quicker append and pop operations
from both the ends of container, as deque provides an O(1) time complexity for append and
pop operations as compared to list which provides O(n) time complexity.
• Instead of enqueue and deque, append() and popleft() functions are used.
• The code uses a deque from the collections module to represent a queue.
• [Link]
Implementation using [Link]
• Queue is built-in module of Python which is used to implement a queue.
• [Link](maxsize) initializes a variable to a maximum size of maxsize.
• A maxsize of zero ‘0’ means a infinite queue.
• various functions
• maxsize – Number of items allowed in the queue.
• empty() – Return True if the queue is empty, False otherwise.
• full() – Return True if there are maxsize items in the queue. If the queue was initialized with
maxsize=0 (the default), then full() never returns True.
• get() – Remove and return an item from the queue. If queue is empty, wait until an item is
available.
• get_nowait() – Return an item if one is immediately available, else raise QueueEmpty.
• put(item) – Put an item into the queue. If the queue is full, wait until a free slot is available
before adding the item.
• put_nowait(item) – Put an item into the queue without blocking. If no free slot is immediately
available, raise QueueFull.
• qsize() – Return the number of items in the queue.
Applications of Queues:
• Task Scheduling: Managing a sequence of tasks to be processed in order.
• Job Processing: Handling a queue of jobs in systems like print queues or background
processing.
• Event Handling: Processing events in the order they occur.
• Breadth-First Search (BFS) algorithms: in graph traversal.
• Managing shared resources: like printers or communication lines.
Basic queue operations
• Enqueue: Adds a new element to the queue.
• Dequeue: Removes and returns the first (front) element from the queue.
• Peek: Returns the first element in the queue.
• isEmpty: Checks if the queue is empty.
• Size: Finds the number of elements in the queue.
• Queue using list
• quelist..docx

• Implementing a Queue Class

• [Link]
Queue Implementation using Linked Lists

• [Link]
• Reasons for using linked lists to implement queues:

• Dynamic size: The queue can grow and shrink dynamically, unlike with arrays.
• No shifting: The front element of the queue can be removed (enqueue) without having to shift
other elements in the memory.

• Reasons for not using linked lists to implement queues:

• Extra memory: Each queue element must contain the address to the next element (the next
linked list node).
• Readability: The code might be harder to read and write for some because it is longer and
more complex.
Double ended queue
• A deque (double-ended queue) is a linear data structure that allows elements to be added
or removed from either end.
• There are two specialized types of deques based on restrictions to their input and output
operations
• Input-Restricted Deque:
• Insertion: Elements can only be inserted at one designated end (e.g., only at the front or only
at the rear).
• Deletion: Elements can be deleted from both ends (front and rear).
• Analogy: This type of deque functions similarly to a standard queue for insertion but offers
more flexibility for removal.
• Output-Restricted Deque:
• Insertion: Elements can be inserted at both ends (front and rear).
• Deletion: Elements can only be deleted from one designated end (e.g., only from the front or
only from the rear).
• Analogy: This type of deque functions similarly to a standard queue for deletion but offers
more flexibility for insertion.
 Operation Description Time Complexity

append(x) Adds x to the right end of the deque. O(1)

appendleft(x) Adds x to the left end of the deque. O(1)

pop() Removes and returns an element from the right end of the deque. O(1)

popleft() Removes and returns an element from the left end of the deque. O(1)

extend(iterable) Adds all elements from iterable to the right end of the deque. O(k)

extendleft(iterable)
Adds all elements from iterable to the left end of the deque (reversed order). O(k)

remove(value)
Removes the first occurrence of value from the deque. Raises ValueError if not found. O(n)

rotate(n)
Rotates the deque n steps to the right. If n is negative, rotates to the left. O(k)

clear() Removes all elements from the deque. O(n)

count(value) Counts the number of occurrences of value in the deque. O(n)

index(value)
Returns the index of the first occurrence of value in the deque. Raises ValueError if not found. O(n)

reverse() Reverses the elements of the deque in place. O(n)

Why Do We Need deque
• It supports O(1) time for adding/removing elements from both ends.
• It is more efficient than lists for front-end operations.
• It can function as both a queue (FIFO) and a stack (LIFO).
• Ideal for scheduling, sliding window problems and real-time data processing.
• It offers powerful built-in methods like appendleft(), popleft() and rotate().
Appending and Deleting Dequeue Items
• append(x): Adds x to the right end of the deque.
• appendleft(x): Adds x to the left end of the deque.
• extend(iterable): Adds all elements from the iterable to the right end.
• extendleft(iterable): Adds all elements from the iterable to the left end (in reverse order).
• remove(value): Removes the first occurrence of the specified value from the deque. If value is
not found, it raises a ValueError.
• pop(): Removes and returns an element from the right end.
• popleft(): Removes and returns an element from the left end.
• clear(): Removes all elements from the deque.

• [Link]
Accessing Item and length of deque
• Indexing: Access elements by position using positive or negative indices.
• len(): Returns the number of elements in the deque.
• [Link]
Count, Rotation and Reversal of a deque
• count(value): This method counts the number of occurrences of a specific element in the deque.
• rotate(n): This method rotates the deque by n steps. Positive n rotates to the right and negative n
rotates to the left.
• reverse(): This method reverses the order of elements in the deque.
• [Link]
Input Restricted Queue
• An input restricted queue is a special case of a double-ended queue where data can be inserted from
one end(rear) but can be removed from both ends (front and rear).
Operations on Input Restricted Queue:

• insertRear(): Adds an item at the rear of the queue.

• deleteFront(): Deletes an item from the front of the queue.
• deleteRear(): Deletes an item from rear of the queue.

• getFront(): Gets the front item from the queue.

• getRear(): Gets the last item from the queue.
• isEmpty(): Checks whether queue is empty or not.
• isFull(): Checks whether queue is full or not.

• [Link]
• Time Complexity: O(N)
• Auxiliary Space: O(N)

• Need to implement input restricted queue:

• This queue is used when it is necessary to consume data in FIFO order but it is necessary to discard
recently added data for a variety of reasons, such as useless data, performance issues, etc.
• It is needed when we have to inhibit insertion from the front of the deque.
• It is used in job scheduling algorithms.

• Advantages of Input Restricted Queue:

• Security of the system by restricting the insert method of the queue at the front.

• Disadvantages of Input Restricted Queue:

• Can't provide the added functionality in comparison to Deque.
Priority queue
• A priority queue is an abstract data structure similar to a regular queue, but with the key
difference that elements are processed based on their assigned priority rather than their order
of insertion.
• If two elements have the same priority, their order of insertion (FIFO) typically determines their
dequeue order.

• Key properties of priority queue:

• High-priority elements are dequeued before low-priority ones.
• If two elements have the same priority, they are dequeued in their order of insertion like a
queue.
Key differences between priority queue and queue

Feature Regular Queue Priority Queue

Order of Processing First-In-First-Out (FIFO) Based on priority

Element Dequeue Order In order of arrival Highest priority first

Based on arrival time (if priority

Handling Same Priority Based on arrival time
is same)

Acts like a sorted structure

Sorting Effect No sorting
when dequeued
Explanation:

• insert(q, d) adds element d to the end of the queue q using append().

• delete(q) finds and removes the highest priority (max value) element from q. If the queue is
empty, it prints "Queue empty." and exits.
• is_empty(q) returns True if the queue q is empty, otherwise False.
• In the __main__ block while loop is used to repeatedly remove and print the highest priority
element using the delete() function until the queue becomes empty.
• [Link]
Priority queue using linked list
• [Link]

• Algorithm
• PUSH(HEAD, DATA, PRIORITY):
• Step 1: Create new node with DATA and PRIORITY
• Step 2: Check if HEAD has lower priority. If true follow Steps 3-4 and end. Else goto Step 5.
• Step 3: NEW -> NEXT = HEAD
• Step 4: HEAD = NEW
• Step 5: Set TEMP to head of the list
• Step 6: While TEMP -> NEXT != NULL and TEMP -> NEXT -> PRIORITY > PRIORITY
• Step 7: TEMP = TEMP -> NEXT
• [END OF LOOP]
• Step 8: NEW -> NEXT = TEMP -> NEXT
• Step 9: TEMP -> NEXT = NEW
• Step 10: End
Algorithm cont..
• POP(HEAD):

• Step 1: Set the head of the list to the next node in the list. HEAD = HEAD -> NEXT.
• Step 2: Free the node at the head of the list
• Step 3: End

• PEEK(HEAD):
• Step 1: Return HEAD -> DATA
• Step 2: End
Applications of priority queue

• Task Scheduling (Operating Systems) manages tasks by priority, executing high-priority tasks first in
real-time systems.
• Dijkstra's Shortest Path Algorithm uses a priority queue to find the shortest path by selecting the
nearest node.
• Huffman Encoding (Data Compression) combines least frequent symbols using a priority queue to
reduce data size.
• Merging Multiple Sorted Lists merges sorted lists by selecting the smallest element from each list.
• A Search Algorithm (Pathfinding) prioritizes nodes based on cost to find the shortest path in navigation
or games.
Types of priority queue

• Max Priority Queue: The element with the highest priority is dequeued first. It’s commonly used
when you need to process the most important or largest element first.

• Min Priority Queue: The element with the lowest priority is dequeued first. It’s useful for problems
like finding the smallest element or processing tasks with the least urgency first.