Comparing Data Structures: Stacks vs Queues

Let's compare and contrast two simple data structures: stacks and queues

ยท

5 min read

Comparing Data Structures: Stacks vs Queues

Photo by Mae Mu on Unsplash

Introduction

This article provides an in-depth look at two fundamental data structures in programming: stacks and queues. It discusses the characteristics, advantages, and disadvantages of both, with Python code examples provided for better understanding. Stacks, operating on a Last In First Out (LIFO) principle, are efficient in memory usage and fast in operations, but lack flexibility and search operations. Queues, following the First In First Out (FIFO) model, are predictable and widely used, but can be inefficient in memory usage and slower in operations. The choice between a stack and a queue depends on the specific problem you are trying to solve.


I. Stacks

Similar to a list, a stack is an ordered sequence of values.

A stack is a linear data structure that follows a particular order in which operations are performed. The order in which values are added to a stack is LIFO (Last In First Out).

In Python, you can create a stack data structure using either an implementation of lists or linked lists.

In this article, I'll be demonstrating how to use Python's built-in list data structure to create a stack data structure.

a) Creating a stack in Python

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

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

# Example usage:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2
print(stack.is_empty())  # Output: False

b) Stack methods

Some basic methods for stacks include:

  • push - adds a value to the top of the stack

  • pop - removes the value at the top of the stack

  • peek - returns the value at the top of the stack

  • is_empty - returns True if the stack is empty, otherwise returns False

c) Advantages

Some advantages of stacks include:

  1. Efficient Memory Usage: stacks use a block of memory that fits exactly the amount of data stored, minimizing wasted space.

  2. Fast Operations: All operations like push, pop, and peek have a time complexity of O(1)

d) Disadvantages

Some disadvantages of stacks include:

  1. Limited Flexibility: Stacks operate on the LIFO principle, which means the most recently added item is the first one to be removed. This lack of flexibility can be a disadvantage in scenarios where access to other values is needed

  2. Lack of Search Operation: Stacks do not allow you to search through the data. To access data that is not on the top of the stack, you must remove its preceding items.


II. Queues

Similar to stacks, a queue is a type of data structure that stores elements in a sequence.

Contrary to stacks, queue operations occur in a FIFO (First In First Out) manner. This means that the element that is inserted first is the one that gets removed first.

Similar to stacks, queues can be implemented using lists or linked lists.

Just like the stacks example, I'm going to demonstrate how you can create queues in Python using an implementation of Python's built-in list data structure.

a) Creating a queue in Python

class Queue:
  def __init__(self):        
    self.list = []   

  def enqueue(self, data):        
    self.list.append(data)    

  def dequeue(self):        
    val = self.list[0]        
    del self.list[0]        
    return val    

  def is_empty(self):        
    return len(self.list) == 0

# Example usage:
my_queue = Queue()
my_queue.enqueue(1)
my_queue.enqueue(2)
my_queue.enqueue(3)
print(my_queue.dequeue())  # Output: 1

b) Queue methods

Some basic methods for queues include:

  • enqueue - adds a value to the end of the queue

  • dequeue - removes the value at the beginning of the queue

  • is_empty - returns True if the queue is empty, otherwise returns False

c) Advantages

Some advantages of queues include:

  1. Predictability: Since queues follow the FIFO model, the timing of operations is highly predictable. You always know which item is next in line.

  2. Broad Usage: Queues are used in a wide variety of programming scenarios, such as managing processes in a job scheduling system, handling requests on a single shared resource like a printer, and in CPU scheduling and disk scheduling.

d) Disadvantages

  1. Inefficient Memory Usage: Unlike arrays, queues that are implemented using linked lists can use more memory because of the extra storage needed for pointers.

  2. Slow Operations: Depending on the implementation, operations like enqueue and dequeue can be slower in queues than in arrays or stacks.

  3. Complexity: Queues are more complex to manage than stacks because you need to maintain two pointers (front and rear), compared to stacks where only one pointer (top) is required.

  4. Limited Access: Similar to stacks, queues don't provide the ability to access elements in the middle. You can only directly access the first and last elements.


III. Conclusion

In conclusion, both stacks and queues are essential data structures in programming, each with their unique characteristics and use cases.

Stacks operate on the LIFO principle, making them ideal for scenarios that require reversing or where the most recent data is of primary interest. On the other hand, queues operate on the FIFO model, making them suitable for maintaining the order of operations and handling asynchronous tasks.

However, both have their limitations. Stacks lack flexibility and do not support search operations, while queues can be inefficient in memory usage and slower in operations. Therefore, the choice between a stack and a queue depends on the specific requirements of the problem you are trying to solve.

If you have any lingering questions or suggestions for an article you want me to cover in the future, feel free to leave a comment in the comment section below.

Lastly, make sure to follow my newsletter so you never miss out on when I post new content! When you subscribe to my newsletter, you'll be able to read my articles straight from your inbox as soon as they're released.


a person typing on a laptop on a desk

This article is part of a series called Bit by Bit, a series devoted to all things programming. Whether you're still a computer science undergrad or the CTO of Apple, there's something for you here.

New articles in this series are posted every Tuesday!

Did you find this article valuable?

Support Scrapped Script by becoming a sponsor. Any amount is appreciated!

ย