Stacks and Queues: Mastering Advanced Data Structures in Python

Introduction: Stacks and Queues

Welcome to an exciting exploration of two fundamental data structures: Stacks and Queues! Remember, data structures store and organize data in a manner that is structured and efficient. Stacks and Queues are akin to stacking plates and standing in a line, respectively. Intriguing, isn't it? Let's dive in!

Stacks: Last In, First Out (LIFO)

A Stack adheres to the "Last In, First Out" or LIFO principle. It's like a pile of plates where the last plate added is the first one to be removed. Python uses the list to create a stack, with append() used for push, and pop() used for pop . Let's explore this using a pile of plates. Python class StackOfPlates: def __init__(self): self.stack = [] # Inserts a plate at the top of the stack def add_plate(self, plate): self.stack.append(plate) # Removes the top plate from the stack def remove_plate(self): if len(self.stack) == 0: return "No plates left to remove!" return self.stack.pop() # Create a stack of plates plates = StackOfPlates() plates.add_plate('Plate') # Pushing a plate plates.add_plate('Another Plate') # Pushing another plate # Let's remove a plate; it should be the last one we added. print('Removed:', plates.remove_plate()) # Outputs: Removed: Another Plate class StackOfPlates: def __init__(self): self.stack = [] # Inserts a plate at the top of the stack def add_plate(self, plate): self.stack.append(plate) # Removes the top plate from the stack def remove_plate(self): if len(self.stack) == 0: return "No plates left to remove!" return self.stack.pop() # Create a stack of plates plates = StackOfPlates() plates.add_plate('Plate') # Pushing a plate plates.add_plate('Another Plate') # Pushing another plate # Let's remove a plate; it should be the last one we added. print('Removed:', plates.remove_plate()) # Outputs: Removed: Another Plate The last plate added was removed first, demonstrating the LIFO property of a stack.

Queues: First In, First Out (FIFO)

A Queue represents the "First In, First Out" or FIFO principle, much like waiting in line at the grocery store. Python's deque class creates queues according to the FIFO principle, providing append() for enqueue and popleft() for dequeue . Let's examine this through a queue of people. Python from collections import deque class QueueOfPeople: def __init__(self): self.queue = deque([]) # Add a person to the end of the queue def enqueue_person(self, person): self.queue.append(person) # Remove the first person from the queue (who has been waiting the longest) def dequeue_person(self): if len(self.queue) == 0: return "No people left to dequeue!" return self.queue.popleft() # Create a queue of people people = QueueOfPeople() people.enqueue_person('Person 1') # Person 1 enters the queue people.enqueue_person('Person 2') # Person 2 arrives after Person 1 # Who's next in line? It must be Person 1! print('Removed:', people.dequeue_person()) # Outputs: Removed: Person 1 from collections import deque class QueueOfPeople: def __init__(self): self.queue = deque([]) # Add a person to the end of the queue def enqueue_person(self, person): self.queue.append(person) # Remove the first person from the queue (who has been waiting the longest) def dequeue_person(self): if len(self.queue) == 0: return "No people left to dequeue!" return self.queue.popleft() # Create a queue of people people = QueueOfPeople() people.enqueue_person('Person 1') # Person 1 enters the queue people.enqueue_person('Person 2') # Person 2 arrives after Person 1 # Who's next in line? It must be Person 1! print('Removed:', people.dequeue_person()) # Outputs: Removed: Person 1 Here, Person 1, the first to join the queue, left before Person 2, demonstrating the FIFO property of a queue.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Python

class StackOfPlates:
  def __init__(self):
    self.stack = []

  # Inserts a plate at the top of the stack
  def add_plate(self, plate):
    self.stack.append(plate)

  # Removes the top plate from the stack
  def remove_plate(self):
    if len(self.stack) == 0:
      return "No plates left to remove!"
    return self.stack.pop()

# Create a stack of plates
plates = StackOfPlates()
plates.add_plate('Plate') # Pushing a plate
plates.add_plate('Another Plate') # Pushing another plate
# Let's remove a plate; it should be the last one we added.
print('Removed:', plates.remove_plate())  # Outputs: Removed: Another Plate

Python

from collections import deque

class QueueOfPeople:
  def __init__(self):
    self.queue = deque([])

  # Add a person to the end of the queue
  def enqueue_person(self, person):
    self.queue.append(person)

  # Remove the first person from the queue (who has been waiting the longest)
  def dequeue_person(self):
    if len(self.queue) == 0:
      return "No people left to dequeue!"
    return self.queue.popleft()

# Create a queue of people
people = QueueOfPeople()
people.enqueue_person('Person 1') # Person 1 enters the queue
people.enqueue_person('Person 2') # Person 2 arrives after Person 1
# Who's next in line? It must be Person 1!
print('Removed:', people.dequeue_person())  # Outputs: Removed: Person 1

Python

from collections import deque

class TextEditor:
  def __init__(self):
    self.stack = []
    self.queue = deque([])

  # Make a change (e.g., edit text, insert image, change font)
  def make_change(self, action):
    self.stack.append(action) # Add to the stack of actions

  # Undo the most recent change
  def undo_change(self):
    if len(self.stack) == 0:
      return "No changes to undo!"
    return self.stack.pop() # Remove the last action from the stack

  # Add a document to the queue for printing
  def add_to_print(self, doc):
    self.queue.append(doc)

  # Print the document that has been waiting the longest
  def print_doc(self):
    if len(self.queue) == 0:
      return "No documents in print queue!"
    return self.queue.popleft() # Remove the first document from the queue

# Use our text editor!
editor = TextEditor()
editor.make_change("Changed font size") # Make a change
editor.make_change("Inserted image") # Make another change
# Let's undo a change. It should be the last change we made.
print('Undo:', editor.undo_change())  # Undo: Inserted image

editor.add_to_print("Proposal.docx") # Queue a document for printing
editor.add_to_print("Report.xlsx") # Queue another document
# Let's print a document. It should be the document that has been waiting the longest.
print('Print:', editor.print_doc())  # Print: Proposal.docx

from collections import deque

class TextEditor:
  def __init__(self):
    self.stack = []
    self.queue = deque([])

  # Make a change (e.g., edit text, insert image, change font)
  def make_change(self, action):
    self.stack.append(action) # Add to the stack of actions

  # Undo the most recent change
  def undo_change(self):
    if len(self.stack) == 0:
      return "No changes to undo!"
    return self.stack.pop() # Remove the last action from the stack

  # Add a document to the queue for printing
  def add_to_print(self, doc):
    self.queue.append(doc)

  # Print the document that has been waiting the longest
  def print_doc(self):
    if len(self.queue) == 0:
      return "No documents in print queue!"
    return self.queue.popleft() # Remove the first document from the queue

# Use our text editor!
editor = TextEditor()
editor.make_change("Changed font size") # Make a change
editor.make_change("Inserted image") # Make another change
# Let's undo a change. It should be the last change we made.
print('Undo:', editor.undo_change())  # Undo: Inserted image

editor.add_to_print("Proposal.docx") # Queue a document for printing
editor.add_to_print("Report.xlsx") # Queue another document
# Let's print a document. It should be the document that has been waiting the longest.
print('Print:', editor.print_doc())  # Print: Proposal.docx

Python

from collections import deque

class TextEditor:
  def __init__(self):
    self.stack = []
    self.queue = deque([])

  # Make a change (e.g., edit text, insert image, change font)
  def make_change(self, action):
    self.stack.append(action) # Add to the stack of actions

  # Undo the most recent change
  def undo_change(self):
    if len(self.stack) == 0:
      return "No changes to undo!"
    return self.stack.pop() # Remove the last action from the stack

  # Add a document to the queue for printing
  def add_to_print(self, doc):
    self.queue.append(doc)

  # Print the document that has been waiting the longest
  def print_doc(self):
    if len(self.queue) == 0:
      return "No documents in print queue!"
    return self.queue.popleft() # Remove the first document from the queue

# Use our text editor!
editor = TextEditor()
editor.make_change("Changed font size") # Make a change
editor.make_change("Inserted image") # Make another change
# Let's undo a change. It should be the last change we made.
print('Undo:', editor.undo_change())  # Undo: Inserted image

editor.add_to_print("Proposal.docx") # Queue a document for printing
editor.add_to_print("Report.xlsx") # Queue another document
# Let's print a document. It should be the document that has been waiting the longest.
print('Print:', editor.print_doc())  # Print: Proposal.docx