Home >Backend Development >Python Tutorial >Stack and Queue || Python || Data Structures and Algorithms
Stack - It is a storage container which supports retrieval by last-in, first-out ( LIFO) order. Stacks are probably the right container to use when retrieval order doesn’t matter at all, such as when processing batch jobs.
For example, consider a stack of plates used in cafeterias: the order in which plates are removed from the stack is the reverse of the order in which they were added, as only the top plate is accessible.
The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP.
Push (x,s): Insert item x at the top of stack s.
Pop(s) : Return (and remove) the top item of stack s.
Food inserted into my refrigerator usually exits the same way, despite the incentive of expiration dates. Algorithmically, LIFO tends to happen in the course of executing recursive algorithms.
Applications of Stack -
Implement Stack Using Array -
class Stack: def __init__(self): #Initializes an empty stack self.stack = [] def isEmpty(self) -> bool: #Returns True if the stack is empty, False otherwise. return len(self.stack) == 0 def push(self, item) -> None: #Pushes an item onto the stack. self.stack.append(item) def pop(self): #Removes and returns the top item from the stack. if self.isEmpty(): return None return self.stack.pop() def peek(self): #Returns the top item from the stack without removing it. if self.isEmpty(): return None return self.stack[-1]
Queue - It is a storage container which supports retrieval by first-in, first-out (FIFO) order. We call the INSERT operation on a queue ENQUEUE, and we call the DELETE operation DEQUEUE. Like the stack operation POP, DEQUEUE takes no element argument. Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is predefined.
Enqueue(x,q): Insert item x at the back of queue q.
Dequeue(q): Return (and remove) the front item from queue q.
The queue has a head and a tail.
When an element is enqueued, it takes its place at the tail of the queue, just as a newly arriving customer takes a place at the end of the line.
The element dequeued is always the one at the head of the queue, like the customer at the head of the line, who has waited the longest.
Applications of Queue -
Implement Queue Using Array-
class Stack: def __init__(self): #Initializes an empty stack self.stack = [] def isEmpty(self) -> bool: #Returns True if the stack is empty, False otherwise. return len(self.stack) == 0 def push(self, item) -> None: #Pushes an item onto the stack. self.stack.append(item) def pop(self): #Removes and returns the top item from the stack. if self.isEmpty(): return None return self.stack.pop() def peek(self): #Returns the top item from the stack without removing it. if self.isEmpty(): return None return self.stack[-1]
Implement Queue using Stacks -
class MyQueue: def __init__(self): # Store elements self.queue = [] # A pointer to indicate the start position self.p_start = 0 def enQueue(self, x): #Insert an element into the queue. self.queue.append(x) return True # Return True if the operation is successful def deQueue(self): #Delete an element from the queue. if self.isEmpty(): return False self.p_start += 1 return True #Return True if the operation is successful def Front(self): #Get the front item from the queue. if not self.isEmpty(): return self.queue[self.p_start] return None # Return None if the queue is empty def isEmpty(self): #Checks whether the queue is empty or not return self.p_start >= len(self.queue)
Implement Stack using Queues -
class MyQueue: def __init__(self): self.stack_1 = [] # Main stack for enqueue operations self.stack_2 = [] # Temporary stack for dequeue operations self.front = None # Pushes element x to the back of the queue. def push(self, x): # Move all elements from stack1 to stack 2 to reverse their order while self.stack_1: self.stack_2.append(self.stack_1.pop()) self.stack_2.append(x) # Move all elements back from stack2 to stack 1 as a queue while self.stack_2: self.stack_1.append(self.stack_2.pop()) # Removes the element from the front of the queue and returns it def pop(self): return self.stack_1.pop() # Returns the element at the front of the queue def peek(self): return self.stack_1[-1] # Returns true if the queue is empty, false otherwise def empty(self): return not self.stack_1
The above is the detailed content of Stack and Queue || Python || Data Structures and Algorithms. For more information, please follow other related articles on the PHP Chinese website!