Stacks and Queues

Data Structures and Algorithms with Python is an introductory course that covers the fundamentals of data structures and algorithms. In this course, we will focus on two important data structures—stacks and queues—and how to implement them using arrays, classes, and the queue module in Python. We will also discuss the applications of stacks and queues.

What Are Stacks and Queues?

Stacks and queues are two of the most commonly used data structures. A stack is a collection of objects that are organized in a Last-In-First-Out (LIFO) structure. The last object that was added to the stack is the first one that can be removed. Stacks are often used to store data in a temporary or intermediate format, such as when reversing a string or evaluating an expression.

A queue is a collection of objects that are organized in a First-In-First-Out (FIFO) structure. The first object that was added to the queue is the first one that can be removed. Queues are often used to store data in a waiting state, such as when processing jobs or tasks in a system.

Implementing Stacks and Queues Using Arrays Stacks and queues can be implemented using arrays. An array is a data structure that stores a collection of items in a contiguous block of memory. Each item in the array is referred to as an element, and it can be accessed using its index or position in the array.

To implement a stack using an array, we will need to use the following methods:

• push(): This method adds an element to the top of the stack.
• pop(): This method removes the element from the top of the stack.
• isEmpty(): This method checks if the stack is empty.

The following code snippet shows how to implement a stack using an array in Python:

class Stack:
  def __init__(self):
    self.stack = []
  
  def push(self, item):
    self.stack.append(item)
    
  def pop(self):
    if self.isEmpty():
      return None
    else:
      return self.stack.pop()

  def isEmpty(self):
    return len(self.stack) == 0

To implement a queue using an array, we will need to use the following methods:

• enqueue(): This method adds an element to the back of the queue.
• dequeue(): This method removes the element from the front of the queue.
• isEmpty(): This method checks if the queue is empty.

The following code snippet shows how to implement a queue using an array in Python:

class Queue:
  def __init__(self):
    self.queue = []
  
  def enqueue(self, item):
    self.queue.append(item)
    
  def dequeue(self):
    if self.isEmpty():
      return None
    else:
      return self.queue.pop(0)

  def isEmpty(self):
    return len(self.queue) == 0

Implementing Stacks and Queues Using Classes

Stacks and queues can also be implemented using classes. A class is a blueprint for creating objects. Objects are instances of classes, and they can have their own attributes and methods.

The following code snippet shows how to implement a stack using a class in Python:

class Stack:
  def __init__(self):
    self.items = []
  
  def push(self, item):
    self.items.append(item)
    
  def pop(self):
    if self.isEmpty():
      return None
    else:
      return self.items.pop()

  def isEmpty(self):
    return len(self.items) == 0

The following code snippet shows how to implement a queue using a class in Python:

class Queue:
  def __init__(self):
    self.items = []
  
  def enqueue(self, item):
    self.items.append(item)
    
  def dequeue(self):
    if self.isEmpty():
      return None
    else:
      return self.items.pop(0)
  
  def isEmpty(self):
    return len(self.items) == 0

Using the Queue Module in Python

The queue module in Python provides a number of queue-related data structures and algorithms. The most commonly used data structure is the Queue class, which is a FIFO queue. The Queue class provides the following methods:

• put(): This method adds an element to the back of the queue.
• get(): This method removes the element from the front of the queue.
• empty(): This method checks if the queue is empty.

The following code snippet shows how to use the Queue class in Python:

import queue

q = queue.Queue()

q.put(1)
q.put(2)
q.put(3)

while not q.empty():
  print(q.get())

# Output:
# 1
# 2
# 3

Applications of Stacks and Queues

Stacks and queues are used in a variety of applications, such as:

• Operating system processes: Stacks are used to store the state of a process before it is suspended, while queues are used to store the list of processes that are waiting to be executed.
• Compilers: Stacks are used to store intermediate results during compilation, while queues are used to store symbols for lexical analysis.
• Graph algorithms: Stacks are used to store the nodes that have been visited during a depth-first search (DFS), while queues are used to store the nodes that need to be visited during a breadth-first search (BFS).
• Network routing algorithms: Stacks are used to store the shortest path between two nodes, while queues are used to store the nodes that need to be visited during a routing algorithm.

Conclusion

In this article, we have discussed the fundamentals of stacks and queues, and how to implement them using arrays, classes, and the queue module in Python. We have also discussed the applications of stacks and queues in various domains. With this knowledge, you are now ready to explore and use stacks and queues in your own projects.

Exercises

class Stack:
  def __init__(self):
    self.items = []
  
  def push(self, item):
    self.items.append(item)
    
  def pop(self):
    if self.isEmpty():
      return None
    else:
      return self.items.pop()

  def isEmpty(self):
    return len(self.items) == 0

s = Stack()
s.push(1)
s.push(2)
s.push(3)

while not s.isEmpty():
  print(s.pop())

class Queue:
  def __init__(self):
    self.items = []
  
  def enqueue(self, item):
    self.items.append(item)
    
  def dequeue(self):
    if self.isEmpty():
      return None
    else:
      return self.items.pop(0)
  
  def isEmpty(self):
    return len(self.items) == 0

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

while not q.isEmpty():
  print(q.dequeue())

import queue

q = queue.Queue()

q.put("Hello")
q.put("World")
q.put("!")

while not q.empty():
  print(q.get(), end="")

# Output: !dlroW olleH

class Stack:
  def __init__(self):
    self.items = []
  
  def push(self, item):
    self.items.append(item)
    
  def pop(self):
    if self.isEmpty():
      return None
    else:
      return self.items.pop()

  def isEmpty(self):
    return len(self.items) == 0

s = Stack()
s.push(1)
s.push(2)
s.push(3)

while not s.isEmpty():
  print(s.pop(), end="")

# Output: 321

import queue

q = queue.Queue()

q.put(1)
q.put(2)
q.put(3)

while not q.empty():
  print(q.get(), end="")

# Output: 123