Unit No 3 Stacks and Queues PDF

**Unit No 3: Stacks and Queues** **3.1 Introduction and Definition of a Stack** What is a Stack? A Stack is a linear data structure that follows the **LIFO (Last-In-First-Out)** principle. Stack has one end, whereas the Queue has two ends (**front and rear**). It contains only one pointer **top p...

**Unit No 3: Stacks and Queues** **3.1 Introduction and Definition of a Stack** What is a Stack? A Stack is a linear data structure that follows the **LIFO (Last-In-First-Out)** principle. Stack has one end, whereas the Queue has two ends (**front and rear**). It contains only one pointer **top pointer** pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other words, a ***stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.*** - It is called as stack because it behaves like a real-world stack, piles of books, etc. - A Stack is an abstract data type with a pre-defined capacity, which means that it can store the elements of a limited size. - It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO. ### Working of Stack Stack works on the LIFO pattern. As we can observe in the below figure there are five memory blocks in the stack; therefore, the size of the stack is 5. Suppose we want to store the elements in a stack and let\'s assume that stack is empty. We have taken the stack of size 5 as shown below in which we are pushing the elements one by one until the stack becomes full. DS Stack Introduction Since our stack is full as the size of the stack is 5. In the above cases, we can observe that it goes from the top to the bottom when we were entering the new element in the stack. The stack gets filled up from the bottom to the top. When we perform the delete operation on the stack, there is only one way for entry and exit as the other end is closed. It follows the LIFO pattern, which means that the value entered first will be removed last. In the above case, the value 5 is entered first, so it will be removed only after the deletion of all the other elements. **3.2 Implementation of a Stack** **3.2.1 Implementation of Stacks Using Arrays** An array implementation of a stack is a way to create a stack data structure using a one-dimensional array or list in a programming language. In this implementation, the array is used to store the elements of the stack, and the stack operations (push, pop, peek, etc.) are performed using the array's operations.  **Initializing the Stack**To create a stack, we need an array to hold the elements and an index to keep track of the top element. class Stack: def \_\_init\_\_(self, capacity): self.capacity = capacity self.stack = \[None\] \* capacity self.top = -1 **Push Operation**Adding an element to the stack is known as the \"push\" operation. Here\'s how it can be implemented: def push(self, item): if self.top == self.capacity - 1: print(\"Stack Overflow\") return self.top += 1 self.stack\[self.top\] = item **Pop Operation**The \"pop\" operation removes and returns the top element from the stack: def pop(self): if self.top == -1: print(\"Stack Underflow\") return None item = self.stack\[self.top\] self.top -= 1 return item ### Example:  Implementation of Stack using Array in Python class Stack: def \_\_init\_\_(self): self.stack = \[\] def is\_empty(self): return len(self.stack) == 0 def push(self, item): self.stack.append(item) def pop(self): if not self.is\_empty(): return self.stack.pop() else: print(\"Stack is empty. Cannot pop.\") return None def peek(self): if not self.is\_empty(): return self.stack\[-1\] else: print(\"Stack is empty. Cannot peek.\") return None def size(self): return len(self.stack) \# Example usage: stack = Stack() stack.push(1) stack.push(2) stack.push(3) print(\"Stack:\", stack.stack) \# Output: Stack: \[1, 2, 3\] print(\"Peek:\", stack.peek()) \# Output: Peek: 3 print(\"Pop:\", stack.pop()) \# Output: Pop: 3 print(\"Stack:\", stack.stack) \# Output: Stack: \[1, 2\] print(\"Is Empty?\", stack.is\_empty()) \# Output: Is Empty? False print(\"Stack Size:\", stack.size()) \# Output: Stack Size: 2 **3.2.2 Implementation of Stacks Using Linked Lists** To implement a [[stack]](https://www.geeksforgeeks.org/stack-data-structure/) using the singly linked list concept, all the singly [[linked list]](https://www.geeksforgeeks.org/data-structures/linked-list/) operations should be performed based on Stack operations LIFO(last in first out) and with the help of that knowledge, we are going to implement a stack using a singly linked list.  So we need to follow a simple rule in the implementation of a stack which is **last in first out** and all the operations can be performed with the help of a top variable. Let us learn how to perform **Pop, Push, Peek, and Display** operations in the following article:https://media.geeksforgeeks.org/wp-content/uploads/1-354.pnghttps://media.geeksforgeeks.org/wp-content/uploads/3-186.png In the stack Implementation, a stack contains a top pointer. which is the "head" of the stack where pushing and popping items happens at the head of the list. The first node has a null in the link field and second node-link has the first node address in the link field and so on and the last node address is in the "top" pointer. The main advantage of using a linked list over arrays is that it is possible to implement a stack that can shrink or grow as much as needed. Using an array will put a restriction on the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocated. so overflow is not possible. *\# Java program to implement a stack using singly linked* *\# list* *\# Class representing a node in the linked list* **class** **Node**: **def** \_\_init\_\_(self, new\_data): self.data = new\_data self.next = **None** *\# Class to implement stack using a singly linked list* **class** **Stack**: **def** \_\_init\_\_(self): *\# head of the linked list* self.head = **None** *\# Function to check if the stack is empty* **def** is\_empty(self): *\# If head is None, the stack is empty* **return** self.head **is** **None** *\# Function to push an element onto the stack* **def** push(self, new\_data): *\# Create a new node with given data* new\_node = Node(new\_data) *\# Check if memory allocation for the new node failed* **if** **not** new\_node: print(\"**\\n**Stack Overflow\") **return** *\# Link the new node to the current top node* new\_node.next = self.head *\# Update the top to the new node* self.head = new\_node *\# Function to remove the top element from the stack* **def** pop(self): *\# Check for stack underflow* **if** self.is\_empty(): print(\"**\\n**Stack is empty\") **else**: *\# Assign the current top to a temporary variable* temp = self.head *\# Update the top to the next node* self.head = self.head.next *\# Deallocate the memory of the old top node* **del** temp *\# Function to return the top element of the stack* **def** peek(self): *\# If stack is not empty, return the top element* **if** **not** self.is\_empty(): **return** self.head.data **else**: print(\"**\\n**Stack is empty\") **return** float(\'-inf\') *\# Creating a stack* st = Stack() *\# Push elements onto the stack* st.push(11) st.push(22) st.push(33) st.push(44) *\# Print top element of the stack* print(\"Top element is\", st.peek()) *\# removing two elemements from the top* print(\"Removing two elements\...\"); st.pop() st.pop() *\# Print top element of the stack* print(\"Top element is\", st.peek()) **Output** Top element is 44 Top element is 22 **3.3 Applications of Stacks:** - - - - - **3.3.1 Conversion of an expression (Infix, Prefix, Postfix)** Postfix to Infix Conversion in Python **Infix expression:** Infix expressions contain the operator in between the two operands. The operands can themselves contain operators. Though with respect to the middle operator, the expression will be an infix expression. **Infix expressions are of the form** 1. (operand\_1 operator oprand\_2)   **Example:** (X + Y) \* (X1 + Y1) **Postfix expression:** Postfix expressions contain the operator at the end of the two operands. The operands can themselves contain operators. Though with respect to the operator, at the end, the expression will be a postfix expression. **Postfix expressions are of the form** 1. (operand\_1 oprand\_2 operator)   **Example:** XY - X1Y1+\* (Infix: (X - Y) \* (X1 + Y1)) Postfix expressions are also known as reverse Polish expressions. Computers are designed to compute the expressions most often in postfix or sometimes in prefixes. However, it is difficult for us to understand and compute a postfix expression. Postfix Expressions Are Complex ------------------------------- Postfix expressions can be very complicated, with multiple parentheses and operators present in a certain order. We are trained to solve infix expressions. Therefore, we need to convert a prefix expression to an infix expression. Here are some sample inputs and outputs for a better understanding of the problem at hand. **Examples:** **Input:** xyz++ **Output:** (x + (y + z)) **Input:** xy\*z+ **Output:** ((x\*y)+z) ### Algorithm 1. We will create a while loop, and the condition will be that the loop will work until there are symbols in the string. 2. The interpreter will read the symbols one by one 3. If the symbol is an operand, then it will be pushed onto the stack. 4. Else, if the symbol is an operator, we will pop two items from the stack. We will insert the operator with the values as its arguments and construct a string of these. Then we will push this string back onto the stack. 5. If the stack has only one value, then that value is the required infix string. Here is the implementation of this algorithm in Python **Code** 1. \# Python Program to convert the given postfix expression into an infix expression   2.    3. \# Get Infix for a given postfix   4. \# expression   5. **def** PostfixToInfix(postfix) :   6.    7.     symbols = \[\]   8.    9.     **for** \_ **in** postfix:       10.             11.         \# Push operands   12.         **if** **not** Operator(\_):           13.             symbols.insert(0, \_)   14.                 15.         \# We will assume that the given expression is a valid postfix   16.         **else**:   17.             18.             op\_1 = symbols\[0\]   19.             symbols.pop(0)   20.             op\_2 = symbols\[0\]   21.             symbols.pop(0)   22.             symbols.insert(0, \"(\" + op\_2 + \_ +  op\_1 + \")\")   23.                 24.     \# At the end, the stack will contain only one string   25.     **return** symbols\[0\]   26.    27. \# Defnining a function to check if the symbol is an operator   28. **def** Operator(symbols):   29.     **if** symbols == \"\*\" **or** symbols == \"+\" **or** symbols == \"-\" **or** symbols == \"/\" **or** symbols == \"\^\" **or** symbols == \"(\" **or** symbols == \")\":   30.         **return** True   31.     **else**:   32.         **return** False   33.    34. \# Calling the function   35. string = \"xy\*z+\"   36. **print**(\"The infix expression is: \", PostfixToInfix(string))   **Output:** The infix expression is: ((x\*y)+z) **3.3.3 String Reversal** There is no built-in function to reverse a String in Python. The fastest (and easiest?) way is to use a slice that steps backwards, -1. **txt = \"Hello World\"\[::-1\]** **print(txt)** **Output:** dlroW olleH **3.4 Introduction and Definition of a Queue** Like a stack, the queue is a linear data structure that stores items in a First In First Out ([FIFO](https://www.geeksforgeeks.org/fifo-first-in-first-out-approach-in-programming/)) manner. With a queue, the least recently added item is removed first. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.  Operations associated with queue are:  - - - - **3.5 Implementation of a Queue** There are various ways to implement a queue in [Python.](https://www.geeksforgeeks.org/python-programming-language/) This article covers the implementation of queue using data structures and modules from Python library. Python Queue can be implemented by the following ways: - - - **3.5.1 Implementation of Queues Using Arrays** Similar to [Stack](https://www.geeksforgeeks.org/stack-data-structure-introduction-program/), [Queue ](https://www.geeksforgeeks.org/introduction-to-queue-in-data-structures-and-algorithms/)is a linear data structure that follows a particular order in which the operations are performed for storing data. The order is First In First Out **(FIFO)**. One can imagine a queue as a line of people waiting to receive something in sequential order which starts from the beginning of the line. It is an ordered list in which insertions are done at one end which is known as the rear and deletions are done from the other end known as the front. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. \ The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added. C:\\Users\\User\\AppData\\Local\\Packages\\Microsoft.Windows.Photos\_8wekyb3d8bbwe\\TempState\\ShareServiceTempFolder\\Queue (1).jpeg **Array implementation Of Queue:** ---------------------------------- For implementing queue, we need to keep track of two indices, front and rear. We enqueue an item at the rear and dequeue an item from the front. If we simply increment front and rear indices, then there may be problems, the front may reach the end of the array. The solution to this problem is to increase front and rear in circular manner. ### **Steps for enqueue:** 1. 2. 3. ### **Steps for dequeue:** 1. 2. 3. Below is a program to implement above operation on queue - **\# Python3 program for array implementation of queue** **\# Class Queue to represent a queue** **class Queue:** **\# \_\_init\_\_ function** **def \_\_init\_\_(self, capacity):** **self.front = self.size = 0** **self.rear = capacity -1** **self.Q = \[None\]\*capacity** **self.capacity = capacity** **\# Queue is full when size becomes** **\# equal to the capacity** **def isFull(self):** **return self.size == self.capacity** **\# Queue is empty when size is 0** **def isEmpty(self):** **return self.size == 0** **\# Function to add an item to the queue.** **\# It changes rear and size** **def EnQueue(self, item):** **if self.isFull():** **print(\"Full\")** **return** **self.rear = (self.rear + 1) % (self.capacity)** **self.Q\[self.rear\] = item** **self.size = self.size + 1** **print(\"% s enqueued to queue\" % str(item))** **\# Function to remove an item from queue.** **\# It changes front and size** **def DeQueue(self):** **if self.isEmpty():** **print(\"Empty\")** **return** **print(\"% s dequeued from queue\" % str(self.Q\[self.front\]))** **self.front = (self.front + 1) % (self.capacity)** **self.size = self.size -1** **\# Function to get front of queue** **def que\_front(self):** **if self.isEmpty():** **print(\"Queue is empty\")** **print(\"Front item is\", self.Q\[self.front\])** **\# Function to get rear of queue** **def que\_rear(self):** **if self.isEmpty():** **print(\"Queue is empty\")** **print(\"Rear item is\", self.Q\[self.rear\])** **\# Driver Code** **if \_\_name\_\_ == \'\_\_main\_\_\':** **queue = Queue(30)** **queue.EnQueue(10)** **queue.EnQueue(20)** **queue.EnQueue(30)** **queue.EnQueue(40)** **queue.DeQueue()** **queue.que\_front()** **queue.que\_rear()** **Output** 10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40 **3.5.2 Implementation of Queues Using Linked Lists** Follow the below steps to solve the problem: - - A parameterized constructor that takes an integer x value as a parameter and sets data equal to x** **and next as NULL - - - Initialize QNode\* temp** **with data = x - If the rear is set to NULL then set the front and rear to temp** **and return(Base Case) - Else set rear next to** **temp and then move rear to temp - - If the front is set to NULL return(Base Case) - Initialize QNode temp** **with front and set front to its next - If the front is equal to NULL** **then set the rear to NULL - Delete temp from the memory **\# Python program to implement the queue data structure using** **\# linked list** **\# Node class representing a single node in the linked list** **class Node:** **def \_\_init\_\_(self, new\_data):** **self.data = new\_data** **self.next = None** **\# Class to implement queue operations using a linked list** **class Queue:** **def \_\_init\_\_(self):** **\# Pointer to the front and the rear of the linked list** **self.front = None** **self.rear = None** **\# Function to check if the queue is empty** **def is\_empty(self):** **\# If the front and rear are null, then the queue is** **\# empty, otherwise it\'s not** **return self.front is None and self.rear is None** **\# Function to add an element to the queue** **def enqueue(self, new\_data):** **\# Create a new linked list node** **new\_node = Node(new\_data)** **\# If queue is empty, the new node is both the front** **\# and rear** **if self.rear is None:** **self.front = self.rear = new\_node** **return** **\# Add the new node at the end of the queue and change rear** **self.rear.next = new\_node** **self.rear = new\_node** **\# Function to remove an element from the queue** **def dequeue(self):** **\# If queue is empty, return** **if self.is\_empty():** **print(\"Queue Underflow\")** **return** **\# Store previous front and move front one node** **\# ahead** **temp = self.front** **self.front = self.front.next** **\# If front becomes null, then change rear also** **\# to null** **if self.front is None:** **self.rear = None** **\# Function to get the front element of the queue** **def get\_front(self):** **\# Checking if the queue is empty** **if self.is\_empty():** **print(\"Queue is empty\")** **return float(\'-inf\')** **return self.front.data** **\# Function to get the rear element of the queue** **def get\_rear(self):** **\# Checking if the queue is empty** **if self.is\_empty():** **print(\"Queue is empty\")** **return float(\'-inf\')** **return self.rear.data** **\# Driver code** **if \_\_name\_\_ == \"\_\_main\_\_\":** **q = Queue()** **\# Enqueue elements into the queue** **q.enqueue(10)** **q.enqueue(20)** **\# Display the front and rear elements of the queue** **print(\"Queue Front:\", q.get\_front())** **print(\"Queue Rear:\", q.get\_rear())** **\# Dequeue elements from the queue** **q.dequeue()** **q.dequeue()** **\# Enqueue more elements into the queue** **q.enqueue(30)** **q.enqueue(40)** **q.enqueue(50)** **\# Dequeue an element from the queue** **q.dequeue()** **\# Display the front and rear elements of the queue** **print(\"Queue Front:\", q.get\_front())** **print(\"Queue Rear:\", q.get\_rear())** **Output** Queue Front: 10 Queue Rear: 20 Queue Front: 40 Queue Rear: 50 **3.6 Applications of Queues**