Data Structures: Stacks and Queues

Stacks and queues are two commonly used data structures. We'll talk about them conceptually today and look at them in more detail over the rest of the week.

Stacks

Stacks as a data structure are a lot like stacks as a physical structure. Think of stacks of dishes or books. We can remove an item from the top of the stack (by poping), or add an item to the top of the stack (by pushing it). While we may be able to Jenga stacks of real world objects, the data structure only allows us to manipulate the top item of the stack. The push and pop operations for a stack are both O(1) - constant time. Some stack implementations also allow us to peek at the value of the top item without actually poping it off of the stack.

Stacks are "Last In, First Out" -- the last item pushed on top of a stack will be the first thing popped off of the stack.

child defending stack of pancakes using fork and knife

Jim dares you to try and pop from his stack of pancakes.

Challenges: Stacks

Draw a stack after each of the following operations:
- PUSH 0
- POP
- PUSH 2
- PUSH 4
- PUSH 6
- POP
- PUSH 8

Stacks and queues are often implemented with linked lists, an important data structure that we haven't talked about yet. So, let's think of arrays. How would you store a stack in an array? How would you push something into the stack in constant time? How would you pop in constant time?

Hint: keep track of an index

Queues

Queues as a data structure are a lot like queues as a physical structure. This makes more sense with British English, where queue means "a line" or "to line up". Think of an orderly line of people waiting to do something. We can remove an item from the front of the queue when its turn comes (by poping, also known as dequeueing), or add an item to the back of the queue when it joins the line (by pushing or enqueueing it). Again, while we may be able to "cut" in line in the real world, the queue data structure only allows us to add to the end of the stack or remove from the beginning. The push and pop operations for a queue are both O(1) - constant time. Like with stacks, some implementations of queues also allow us to peek at the value of the first item without poping it.

Queues are "First In, First Out" -- the first item enqueued will be the first to move all the way through the line and get dequeued.

stick figure demon eats person cutting in line -- from popcoaster.com

Challenges: Queues

Draw a queue after each of the following operations:
- PUSH 0
- POP
- PUSH 2
- PUSH 4
- PUSH 6
- POP
- PUSH 8
Stretch Challenge How would you implement a queue with an array? How would you push something to the end of the queue in constant time? How would you pop something from the front of the queue in constant time?

Hint: keep track of 2 indices

Hint phrase: "circular array"

Basic Challenge: Design Decisions

Would you use a stack or a queue to...

... print out a list of instructions that must be done in order?
... allow a user to undo changes to a document, one by one?
... let users create playlists and play back the songs?
... display only the 10 most recent messages a user posted, in the order they were posted?

Stretch Challenges

The Call Stack

Most programming languages rely on something called the "call stack," especially for recursion. The call stack keeps track of function calls that are in the process of executing. When a function is called, it's pushed onto the call stack. When the function returns, it's poped off of the stack.

Here's the recursive factorial method from yesterday's notes:

def factorial(num)
   if num > 1
      num * factorial(num-1)
   elsif num == 1 or num == 0
      1
   else
      puts "can't do factorial of a negative number!"
   end
end

factorial(3)
# => 6

Write out the full call stack for factorial(3) at each step in the function's execution.

Message Queues

Queues are often used to create "buffers" that temporarily store data from one part of a program until another part of a program can process the data. This is common with asynchronous data transfer, or mismatches between how often data is sent and how often it can be processed.

We'll think of a scenario where students submit homework more quickly than one instructor can review it -- the instructor ends up with a queue of homework to reveiw.

Challenge

Describe how you would use a queue help the instructor keep track of homework to review. What should the teacher do when the queue is empty?

Super Stretch Challenge Two students, Alice and Bob, suggest different solutions to get homework reviewed faster. Both solutions rely on the fact that three instructors are currently available to review homework.

Alice suggests that homework assignments should be given to each instructor in a 'round robin' fashion, repeating every third assignment:

the first instructor gets the first assignment
the second instructor gets the second assignment
the third (and final) instructor gets the third assignment
the first instructor gets the fourth assignment
...

Bob suggests that homework assignments should be always be given to the first instructor unless that instructor already has 10 lined up to grade. If the first instructor's queue is full , assignments should be given to the second instructor, unless they already have 10 assignments lined up to grade. Finally, if the second instructor's queue is full, assignments should be given to the third instructor, unless the third instructor already has 10 assignments lined up to grade.

Which solution do you prefer and why?