Algorithms and Data Structures: Stacks, Queues, and Dequeues

Which Data Structures will we cover?

The three data structures that we’ll cover on this page are going to be stacks, queues, and dequeues. Why did I choose these three? These are some of the common data structures in computer science and I feel that they’re not only commonly used but also are important to know as a concept.

Stacks are used in memory operations. Queues are commonly used to implement buffers. Dequeues are used for multiprocessor scheduling. In this Python tutorial we’ll go over what these data structures are, how to build them, and how to use them.

Python Stack Implementation

When you think of a Stack, I want you to think of a deck of cards. Pretend like you’re playing a card game. We can draw from the top of the deck, look at the top card, place cards on top of the deck, count the number of cards in the deck, and know if the deck is empty or not. In programming, these will translate to pop, top (or peek), push, size, and empty. To implement these in basic Python, we’ll borrow the Python list structure.

stack = []
def push(a):
    stack.append(a)

def pop():

    try:
        del stack[-1]

    except:
        return "Empty Stack"

def top():
    return stack[-1]

def size():
    return len(stack)

def empty():
    return True if size() == 0 else False

print(f'Let\'s see how a stack works')
stack = ['abc', 'xyz', 'dog', 'cat', 'mouse']
print(f'Our current stack is {stack}')
print(f'The current size of our stack is {size()}')
print(f'The topmost element is {top()} but if we pop an element')
pop()
print(f'The new topmost element is {top()} and the stack is now {stack}')
print('We can also add a few strings to our stack')
push('moose')
push('bear')
push('gelatinous cube')
print(f'After pushing three new elements our stack is now {stack}')
print(f'It\'s new size is {size()}')
print(f'If we check for emptiness, this should be False: {empty()}')
for i in range(size()):
    pop()
print(f'If we pop 7 times though, checking for emptiness should now return True: {empty()}')

Your print out should look something like:

Python Stack Implementation Example

Python Queue Implementation

When you think of a queue, I want you to think of a line of people. Queue is also the name that the Brits use to call what we here in America call a line. When you have a queue, you should be able to add to the queue, let an element out of the queue, check the length or size of the queue, check if it’s empty, know what the value of the first element is, and know what the value of the last element is. We’ll call these (in order), add, pop, size, empty, first, and last. In this example we’ll implement a Python Queue with a list.


queue = []

def empty():
    return True if len(queue) == 0 else False

def size():
    return len(queue)

def first():
    return queue[0]

def last():
    return queue[-1]

def add(a):
    queue.append(a)

def pop():
    try:
        del queue[0]
    except:
        return "Empty Queue"

queue = ['s', 'y', 'umbrella', 'purple', 'g']
print(f"Starting queue is {queue} with size {size()}")
print(f"The first element is {first()} the last element is {last()}")
add('q')
print(f"If we 'add' the element 'q', the queue is now {queue} with size {size()} and last element {last()}")
pop()
print(f"If we pop from the queue, the first element is now {first()}")
print(f"The queue is currently not empty so calling empty should return False: {empty()}")
for i in range(len(queue)):
    pop()
print(f"If we 'pop' 5 times though, our queue should now be {queue} and return True for empty - {empty()}")

When we run this code we should get an output like this:

Python Queue Implementation Example

Python Dequeue (or Deque) Implementation

Dequeues, or Deques, I’m not really sure which is right but you’ll see both spellings, are “doubly ended” queues. In other words, they’re a list that you can only play with the first and last elements of. I will be implementing dequeue with a list and I will not implement the size() or empty() functions. I will leave that up to you as an exercise, they should be pretty much the same as the Queue and Stack ones. The functions to know on a dequeue are append, appendleft, pop, and popleft. Append adds an element to the right, appendleft adds an element to the left. Pop removes an element from the right hand side, popleft removes an element from the left.

deq = []

def append(a):
    deq.append(a)

def appendleft(a):
    deq.insert(0, a)

def pop():
    try:
        del deq[-1]
    except:
        return "Dequeue is empty"

def popleft():
    try:
        del deq[0]
    except:
        return "Dequeue is empty"

deq = ['left', 'inner left', 'middle', 'inner right', 'right']
print(f"The current deq is {deq}")
pop()
popleft()
print(f"After we pop and popleft, the new deq is {deq}")
append("new right")
appendleft("new left")
print(f"After we append and append left two new elements we now have {deq}")
for i in range(len(deq)):
    pop()
print(f"After we pop all the values, the deq is now{deq} and should return that it is empty")
print(f"If we try to pop again like so - {pop()}")

If you run the code block above, you should get a result like this:

Python Dequeue or Deque Implementation Example

Remember to implement size() and empty() on your own! To learn more feel free to reach out to me @yujian_tang on Twitter, follow the blog, or join our Discord.

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang