Queues vs. Stacks - A brief visual explanation

A queue is a FIFO (first-in-first-out) data structure while a stack is a LIFO (last-in-first-out) data structure.

What is a queue?

A queue holds a collection of objects where the newest object is added to the back and the oldest object is removed from the front.

Like a queue at the bank

The queue data structure works just like a queue of people in line at a bank. The first person to get in line is first to leave (i.e., first-in-first-out). The last person in the line will be the last to leave.

Common methods:

  • Enqueue = Insert an object at the back of the queue
  • Dequeue = Delete an object from the front of the queue
  • Peek = Look at the item at the front

Common terminology:

  • Front = Oldest item in the collection
  • Back = Newest item in the collection

Queue Visualization

Queue

a
Front
bcd
Back

Queues are FIFO (first-in-first-out) data structures. Enqueue on the rear, dequeue on the front.

simple_queue

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

    def __str__(self):
        array_str = " -> ".join([str(item) for item in self.items][::-1])
        return "%s" % array_str

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

    def dequeue(self):
        self.items.pop(0)


def run_queue():
    queue = Queue()
    queue.enqueue(1)
    queue.enqueue(2)
    queue.dequeue()
    queue.enqueue(3)
    queue.enqueue(4)
    queue.dequeue()
    print(queue)

Queue output:

1234

Sequence: [1] > [1,2] > [2] > [2,3] > [2,3,4] > [3,4]

Most languages have highly performant built-in queues

The above queue code is just for illustration purposes and to keep it simple we used a standard list.

You would most likely wish to use collections.deque or queue.Queue instead of rolling your own queue class.

What is a stack?

A stack holds a collection of objects that are inserted and removed from the top of the stack.

Common methods:

  • Push = Insert an object at the top of the stack
  • Pop = Remove an object from the top of the stack and return it
  • Peek = Look at the top object without modifying
  • isEmpty = Check if stack is empty

Common terminology:

  • Top = The newest item in the collection. Pushing, popping, and peeking all affect the top element.

Stack Visualization

Stack

d
Top
cba

Stacks are LIFO (last-in-first-out) data structures. Add on the top, remove from the top.

simple_stack

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

    def __str__(self):
        top = "--\n"
        bottom = "\n--"
        return "%s%s%s" % (top, '\n'.join([str(item) for item in self.items]), bottom)

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

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

    def pop(self):
        return self.items.pop()

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


if __name__ == "__main__":
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.pop()
    stack.push(3)
    print(stack)

Stack output

3
Top
21

Sequence: [1] > [2,1] > [1] > [3,1]

Most languages have a built-in stack module

As with the note about queues above, this code is merely for illustrative purposes and uses a list. In the real world, you would likely either use collections.deque, or queue.LifoQueue for more performant appending.

Author:

*no spam, just fresh content