Presentation_1638_Content_Document_20250724040014PM.pptx

Pdf of solution of lots of stack and queue problems .so please used this pptsnd study better

1. Unit 2 :Stack & Queue

2. Outline Stack Definitions & Concepts Operations on Stacks Applications of Stacks Polish Expression Reverse Polish Expression and their compilation Recursion Application: Factorial Fibonacci Series Tower of Hanoi. Queue Basic of Queue Representation of Queue Operations on Queue Circular Queue Priority Queue Array representation of Priority Queue Double Ended Queue Applications of Queue.

3. Stack

4. Stack TOP A linear list which allows insertion and deletion of an element at one end only is called stack . The insertion operation is called as PUSH and deletion operation as POP . The most accessible elements in stack is known as top . The elements can only be removed in the opposite orders from that in which they were added to the stack. Such a linear list is referred to as a LIFO (Last In First Out) list. C B A

5. Stack Cont… ‹#› A pointer TOP keeps track of the top element in the stack. Initially, when the stack is empty , TOP has a value of “zero” . Each time a new element is inserted in the stack, the pointer is incremented by “one” before, the element is placed on the stack. The pointer is decremented by “one” each time a deletion is made from the stack. A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means that the last element added (pushed) to the stack is the first one removed (popped) . Think of a stack like a pile of plates : You add plates to the top of the pile (push operation). You remove plates only from the top of the pile (pop operation).

6. A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc. A real-world stack allows operations at one end only. For example, we can place or remove a card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations at one end only. At any given time, we can only access the top element of a stack

7. Basic Operations Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following two primary operations − push() − Pushing (storing) an element on the stack. pop() − Removing (accessing) an element from the stack. When data is PUSHed onto stack. To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks − peek() − get the top data element of the stack, without removing it. isFull() − check if stack is full. isEmpty() − check if stack is empty. At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer always represents the top of the stack, hence named top. The top pointer provides top value of the stack without actually removing it.

8. Push Operation The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps − Step 1 − Checks if the stack is full. Step 2 − If the stack is full, produces an error and exit. Step 3 − If the stack is not full, increments top to point next empty space. Step 4 − Adds data element to the stack location, where top is pointing. Step 5 − Returns success.

9. Algorithm for PUSH Operation

10. Pop Operation Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space. A Pop operation may involve the following steps − Step 1 − Checks if the stack is empty. Step 2 − If the stack is empty, produces an error and exit. Step 3 − If the stack is not empty, accesses the data element at which top is pointing. Step 4 − Decreases the value of top by 1. Step 5 − Returns success.

11. Algorithm for Pop Operation

12. Top or Peek Operation Returns the top element of the stack. Algorithm for Top Operation: Before returning the top element from the stack, we check if the stack is empty. If the stack is empty (top == -1), we simply print "Stack is empty". Otherwise, we return the element stored at index = top .

13. isEmpty Operation isFull Operation Returns true if the stack is empty, else false. Algorithm for isEmpty Operation: Check for the value of top in stack. If (top == -1), then the stack is empty so return true . Otherwise, the stack is not empty so return false . Returns true if the stack is full, else false. Algorithm for isFull Operation: Check for the value of top in stack. If (top == capacity-1), then the stack is full so return true. Otherwise, the stack is not full so return false.

14. Applications of Stack ‹#› Recursion Keeping track of function calls Evaluation of expressions Reversing characters Servicing hardware interrupts Solving combinatorial problems using backtracking Expression Conversion (Infix to Postfix, Infix to Prefix) Game Playing (Chess) Microsoft Word (Undo / Redo) Compiler – Parsing syntax & expression Finding paths

15. Polish Expression & their Compilation Evaluating Infix Expression a + b * c + d * e 1 2 3 A repeated scanning from left to right is needed as operators appears inside the operands. Repeated scanning is avoided if the infix expression is first converted to an equivalent parenthesis free prefix or suffix (postfix) expression . Prefix Expression: Operator , Operand, Operand Postfix Expression: Operand, Operand, Operator

16. Polish Notation This type of notation is known Lukasiewicz Notation or Polish Notation or Reverse Polish Notation due to Polish logician Jan Lukasiewicz . In both prefix and postfix equivalents of an infix expression, the variables are in same relative position . The expressions in postfix or prefix form are parenthesis free and operators are rearranged according to rules of precedence for operators .

17. Polish Notation Sr. Infix Postfix Prefix 1 a a a 2 a + b a b + + a b 3 a + b + c a b + c + + + a b c 4 a + (b + c) a b c + + + a + b c 5 a + (b * c) a b c * + +a * b c 6 a * (b + c) a b c + * * a + b c 7 a * b * c a b *c* ** a b c a + b + c a + b + c (ab+) + c (ab+) c + a b + c +

18. What is Reverse Polish Notation (RPN)? Also known as Postfix Notation , Reverse Polish Notation is a way of writing mathematical expressions without the need for parentheses . Infix A + B * C Postfix (RPN) A B C * + 🎯 Why Use RPN? No need for parentheses Easier and faster to evaluate using a stack Commonly used in compilers , calculators , and expression parsers

19. 5 6 2 + * 12 4 / - Step-by-step: Push 5 Push 6 Push 2 Encounter + : pop 2 and 6 → 6 + 2 = 8 , push 8 Encounter * : pop 8 and 5 → 5 * 8 = 40 , push 40 Push 12 Push 4 Encounter / : pop 4 and 12 → 12 / 4 = 3 , push 3 Encounter - : pop 3 and 40 → 40 - 3 = 37 , push 37 ✅ Result: 37 Practice Question : 7 4 5 + * 6 2 - /

20. Recursion The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. A recursive algorithm takes one step toward solution and then recursively call itself to further move. The algorithm stops once we reach the solution. Since called function may further call itself, this process might continue forever. So it is essential to provide a base case to terminate this recursion process.

21. Step1 - Define a base case: Identify the simplest (or base) case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. Step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.

22. factorial(n) to calculate the factorial of number n . According to the value of n, we can have two cases: if n = 0 or n = 1 : factorial(n) = 1 Else : factorial(n) = n * factorial(n - 1)

23. Fibonacci series The Fibonacci series is a sequence where each number is the sum of the two preceding ones . It starts from: F(0) = 0, F(1) = 1 F(n) = F(n-1) + F(n-2) for n ≥ 2 It is a classic example of recursion . Helps understand stack usage in recursive calls. Forms the base for dynamic programming and memoization concepts.

24. fib(4) → fib(3) + fib(2) → (fib(2) + fib(1)) + (fib(1) + fib(0)) → ((fib(1) + fib(0)) + 1) + (1 + 0) → ((1 + 0) + 1) + (1 + 0) → (1 + 1) + 1 → 2 + 1 = 3

25. Tower of Hanoi Algorithm Tower of Hanoi is a mathematical puzzle where we have three rods (A, B, and C) and N disks. Initially, all the disks are stacked in decreasing value of diameter i.e., the smallest disk is placed on the top and they are on rod A. The objective of the puzzle is to move the entire stack to another rod (here considered C), obeying the following simple rules: Only one disk can be moved at a time. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack. No disk may be placed on top of a smaller disk.

26. The idea is to use the helper node to reach the destination using recursion. Below is the pattern for this problem: Shift 'N-1' disks from 'A' to 'B', using C. Shift last disk from 'A' to 'C'. Shift 'N-1' disks from 'B' to 'C', using A. Create a function towerOfHanoi where pass the N (current number of disk), from_rod, to_rod, aux_rod. Make a function call for N - 1 th disk. Then print the current the disk along with from_rod and to_rod Again make a function call for N - 1 th disk.

27. Queue

28. Queue A linear list which permits deletion to be performed at one end of the list and insertion at the other end is called queue . The information in such a list is processed FIFO (first in first out) or FCFS (first come first served) manner. Front is the end of queue from that deletion is to be performed. Rear is the end of queue at which new element is to be inserted. Insertion operation is called Enqueue & deletion operation is called Dequeue . 10 8 5 80 50 100 Rear Front Insertion ‹#› Deletion

29. Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.

30. Queue Representation A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops. As we now understand that in queue, we access both ends for different reasons. The following diagram given below tries to explain queue representation as data structure − In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or storing) data in the queue we take help of rear pointer.

31. Basic Operations Queue operations may involve initializing or defining the queue, utilizing it, and then completely erasing it from the memory. Here we shall try to understand the basic operations associated with queues − enqueue() − add (store) an item to the queue. dequeue() − remove (access) an item from the queue. Few more functions are required to make the above-mentioned queue operation efficient. These are − peek() − Gets the element at the front of the queue without removing it. isfull() − Checks if the queue is full. isempty() − Checks if the queue is empty.

32. Enqueue Operation Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively difficult to implement than that of stacks. The following steps should be taken to enqueue (insert) data into a queue − Step 1 − Check if the queue is full. Step 2 − If the queue is full, produce overflow error and exit. Step 3 − If the queue is not full, increment rear pointer to point the next empty space. Step 4 − Add data element to the queue location, where the rear is pointing. Step 5 − Return success.

33. Algorithm for enqueue Operation

34. Dequeue Operation Accessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access. The following steps are taken to perform dequeue operation − Step 1 − Check if the queue is empty. Step 2 − If the queue is empty, produce underflow error and exit. Step 3 − If the queue is not empty, access the data where front is pointing. Step 4 − Increment front pointer to point to the next available data element. Step 5 − Return success

35. peek() This function helps to see the data at the front of the queue. The algorithm of peek() function is as follows − Implementation of peek() function in C programming language −

36. isfull() As we are using single dimension array to implement queue, we just check for the rear pointer to reach at MAXSIZE to determine that the queue is full. In case we maintain the queue in a circular linked-list, the algorithm will differ. Algorithm of isfull() function −

37. isempty() Algorithm of isempty() function −

38. isNull() Operation The algorithm of the isNull() operation is as follows - Step 1: Check if the rear and front are pointing to null memory space, i.e., -1. Step 2: If they are pointing to -1, return “Queue is empty.” Step 3: If they are not equal, return “Queue is not empty.”

39. Enqueue Operation Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively difficult to implement than that of stacks. The following steps should be taken to enqueue (insert) data into a queue − Step 1 − Check if the queue is full. Step 2 − If the queue is full, produce overflow error and exit. Step 3 − If the queue is not full, increment rear pointer to point the next empty space. Step 4 − Add data element to the queue location, where the rear is pointing. Step 5 − Return success.

40. Algorithm for enqueue Operation

41. Implementation of enqueue() in C programming language −

42. Dequeue Operation Accessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access. The following steps are taken to perform dequeue operation − Step 1 − Check if the queue is empty. Step 2 − If the queue is empty, produce underflow error and exit. Step 3 − If the queue is not empty, access the data where front is pointing. Step 4 − Increment front pointer to point to the next available data element. Step 5 − Return success.

43. Algorithm for dequeue Operation

44. Implementation of dequeue() in C programming language −

45. Drawbacks of a Linear Queue Wasted Space (Memory Inefficiency) Once elements are dequeued from the front, that space can't be reused in a simple linear queue. Even if the queue isn't full logically, no new elements can be enqueued if the rear reaches the end. Example: After 3 dequeue operations, those front spaces are not utilized again. Fixed Size (in Static Queues) The size of the queue is fixed if implemented using arrays. If the queue gets full, you can’t add more elements unless space is manually managed or dynamically allocated. No Random Access You can only access the front or rear elements directly. You can’t access or delete an element in the middle without dequeuing all previous elements. Slow Operations in Some Cases If implemented using arrays, dequeue operations can become slow if elements need to be shifted to the front (in inefficient implementations). Doesn’t Support Priority Handling All elements are treated equally; there’s no way to process more important tasks first (which is done in priority queues ).

46. ✅ Solutions to Overcome Drawbacks Circular Queue – Reuses space efficiently by wrapping around. Dynamic Queue (using linked list) – No fixed size limitation. Double-Ended Queue (Deque) – Allows insertion/deletion from both ends. Priority Queue – Handles tasks based on priority levels.

47. Circular Queue 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 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,

48. Enqueue Operation Dequeue 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 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 T he complexity of the enqueue and dequeue operations of a circular queue is O(1) for (array implementations).

49. Enqueue Operation

50. Dequeue Operation

51. Priority Queue 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. We can also set priorities according to our needs.

52. Insert / Enqueue Operation Whenever an element is inserted into queue, priority queue inserts the item according to its order. Here we're assuming that data with high value has low priority.

53. Remove / Dequeue Operation Whenever an element is to be removed from queue, queue get the element using item count. Once element is removed. Item count is reduced by one.

54. Array representation of Priority Queue A priority queue stores elements where each element has a priority associated with it. In an array-based priority queue, elements are ordered so that the highest priority element is always at the front of the array. The array is sorted according to the priority values, with the element with the lowest priority value (highest priority) placed at the front.

55. Insert / Enqueue Operation The enqueue operation adds a new element to the priority queue based on its priority . Unlike a normal queue (which adds elements at the end), a priority queue inserts the element in the correct position according to its priority. Lower priority number = Higher priority (e.g., 1 is higher than 3).

56. Steps: If the queue is empty, simply insert the element. Otherwise, find the right position where the element should go: Compare the priority of the new element with existing elements. If the new element has higher priority , shift other elements to make space. Insert the element at the correct position, so that the queue is always sorted based on priority. You want to insert: [Data: 45, Priority: 2] After insertion, the queue becomes:

57. Remove / Dequeue Operation The dequeue operation removes the element with the highest priority (i.e., the element with the lowest priority number ). This element is always at the front of the priority queue. Steps: If the queue is empty, print “Underflow” or return nothing. Otherwise, remove and return the element at the front of the queue (since the queue is sorted by priority). After removal, move the front pointer to the next element. After dequeue , element [40,1] is removed.

58. Double Ended Queue Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends. Below is an example program of deque in different languages. Deque can act as both Stack and Queue It is useful in many problems where we need to have a subset of all operations also like insert/remove at front and insert/remove at the end. It is typically implemented either using a doubly linked list or circular array.

59. Key Characteristics Common Operations Two Ends: Elements can be added or removed from both the front and the rear of the deque. Flexibility: Can act like a queue (FIFO) or a stack (LIFO) depending on the operation. Dynamic Size: Deques can grow or shrink as needed. addFront(element): Inserts an element at the front. addRear(element): Inserts an element at the rear. removeFront(): Removes and returns the element at the front. removeRear(): Removes and returns the element at the rear. getFront(): Returns the element at the front without removing it. getRear(): Returns the element at the rear without removing it. isEmpty(): Checks if the deque is empty. size(): Returns the number of elements in the deque.

60. Application of Queue Task Scheduling : Queues can be used to schedule tasks based on priority or the order in which they were received. Resource Allocation: Queues can be used to manage and allocate resources, such as printers or CPU processing time. Batch Processing : Queues can be used to handle batch processing jobs, such as data analysis or image rendering. Message Buffering : Queues can be used to buffer messages in communication systems, such as message queues in messaging systems or buffers in computer networks. Event Handling : Queues can be used to handle events in event-driven systems, such as GUI applications or simulation systems. Traffic Management : Queues can be used to manage traffic flow in transportation systems, such as airport control systems or road networks. 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.

61. Thank you……