CS211: Stacks & Queues

Imagine a scenario where you've put off doing the dishes for far too long and you need a plate to eat your daily bread. You think, "Oh God, I can't keep living like this." Before it's time to begin running the water you pull your sleeves up to your forearms, wearing out the last bit of plasticity remaining in your elastic cuffs. The joyful mundanity of scrubbing a week's worth of solidifying crust feels like a secular baptism. Every dish you polish and dry is sat atop one another such that the most recently cleaned is at the peak. Once you're done, you take the plate resting at the summit, the one you just finished drying off. You have just implemented and utilized a stack.

Stacks are one of the simplest and most foundational data structures in computing. In fact, I've already used the word "stack" many times already throughout this course when referring to dynamic memory allocated by the compiler. A stack guarantees that the order in which elements are retrieved, or popped off, are in the reverse order in which they were placed, or pushed, on the stack.

Like vectors, stacks can be implemented a variety of ways and may have different features depending on the library being used. The basic functionality is as follows:

• init
  • Initializes a stack
• push
  • Pushes an element on the top of the stack
• peek
  • Retrieves the top element on the stack but does not remove it
• pop
  • Removes and returns the top element on the stack
• is_empty
  • Indicates whether the stack is empty or not
• free
  • Frees the stack

All a stack must do is maintain last-in-first-out (LIFO) order. This gives a wide variety of possible backend implementations for the stack in question. Stacks may have a fixed or a dynamic capacity—again, this is decided by need; traditionally, stacks in standard libraries will have dynamic capacity logic so as to best apply to all general cases. It is left as an exercise for the reader to implement the stack logic.

The diagram below shows the behavior of the main three stack functions (push, pop, and peek):

    original        push(x)          pop()           peek()
                      |               |                |
                      v               |                |
   +-----+         +-----+         +-----+          +-----+
   |  c  |   top → |  x  |   top → |  c  |    top → |  c  |
   +-----+         +-----+         +-----+          +-----+
   |  b  |         |  c  |         |  b  |          |  b  |
   +-----+         +-----+         +-----+          +-----+
   |  a  |         |  b  |         |  a  |          |  a  |
   +-----+         +-----+         +-----+          +-----+
                   |  a  |
                   +-----+

                 x added to       x removed        c returned
                   the top         from top        but NOT removed
                                  returns x         returns c

--------------------------------------------------------------->
                         Time

We begin with a stack that has the elements (c, b, a) where c is at the top of the stack (the elements were pushed in alphabetical order). A call to push(x) places x at the top of the stack. A call to pop() removes the element at the top of the stack, now x, and returns it. A call to peek() takes a look at the new element at the top of the stack, now c again, and returns that element without removing it from the stack.

When I first started teaching data structures years ago, I found that stacks came across as far too abstract for students to connect with as something genuinely useful. Why would I ever need anything in the reverse order in which I added them? It's not immediately intuitive. First, think back to how function calls work in C:

 1: #include <stdio.h>
 2: int hoo(){
 3:   printf("entering hoo()\n");
 4:   printf("leaving hoo()\n");
 5: }
 6: 
 7: int goo(){
 8:   printf("entering goo()\n");
 9:   hoo();
10:   printf("leaving goo()\n");
11: }
12: 
13: int foo(){
14:   printf("entering foo()\n");
15:   goo();
16:   printf("leaving foo()\n");
17: }
18: 
19: int main(){
20:   printf("entering main()\n");
21:   foo();
22:   printf("leaving main()\n");
23: }

You should know the order in which Listing 1 prints, but I'll print out the results anyway:

1: josephraskind@stargazer:/tmp/stack$ gcc print_stack.c -o print_stack; ./print_stack
2: entering main()
3: entering foo()
4: entering goo()
5: entering hoo()
6: leaving hoo()
7: leaving goo()
8: leaving foo()
9: leaving main()

We get a nice symmatry in the "entering" and "leaving" print outs. Why? Well, it's because the compiler maintains a function call stack. We can see a visualization of this below:

main() calls foo()        foo() calls goo()         goo() calls hoo()

+----------+             +----------+              +----------+
|   foo()  |             |   goo()  |              |   hoo()  |
+----------+             +----------+              +----------+
|   main() |             |   foo()  |              |   goo()  |
+----------+             +----------+              +----------+
                         |   main() |              |   foo()  |
                         +----------+              +----------+
                                                   |   main() |
                                                   +----------+

hoo() returns             goo() returns             foo() returns

+----------+             +----------+              +----------+
|   goo()  |             |   foo()  |              |   main() |
+----------+             +----------+              +----------+
|   foo()  |             |   main() |
+----------+             +----------+
|   main() |
+----------+

Each subsequent call pushes the previous function's context onto the stack. Every return pops the recent call off of the stack. The same is done with local variables which is why they go out of scope within the lifetime memory semantics.

Stacks can also be used for parsing tasks. If you remember back to when we discussed operators, I mentioned there were three ways we can represent the syntax for binary operators: prefix, infix, and postfix. We'll focus on postfix notation, or Reverse Polish Notation (RPN), as it is perfectly suited for being handled by a stack.

Take the string 6 + 4 / 2. Without being aware of operator precedence, which a computer is not natively aware of, it is impossible to discern whether or not the user wanted to add 6 and 4 and then divide by 2, or to divide 4 by 2 then add 6. In RPN, there is no ambiguity. If we take classic precedence as a given then we can rewrite that string 6 4 2 / +. The algorithm for RPN is simple:

 1: evaluate(tokens):
 2:   for token in tokens:
 3:     if token is VALUE:
 4:       stack.push(token)
 5:     if token is OPERATOR:
 6:       op ← token
 7:       operand_R ← stack.pop()
 8:       operand_L ← stack.pop()
 9:       push(op(operand_L, operand_R))
10:   return stack.pop()

We can see this evaluation play out visually:

token: 6          token: 4          token: 2          token: /          token: +

push(6)           push(4)           push(2)           R = pop() = 2     R = pop() = 5
                                                      L = pop() = 4     L = pop() = 6
+-----+           +-----+           +-----+           op(4,2) = 4/2     op(6,5) = 6+5
|  6  |           |  4  |           |  2  |           push(2)           push(11)
+-----+           +-----+           +-----+
                  |  6  |           |  4  |           +-----+           +-----+
                  +-----+           +-----+           |  2  |           |  11 |
                                    |  6  |           +-----+           +-----+
                                    +-----+           |  6  |
                                                      +-----+

                                                                     return pop() = 11

I leave it as an exercise to implement RPN in C.

RPN was used in one of the first computers, Konrad Zuse's Z3!

Queues are nearly identical to stacks with one key difference: instead of maintaining LIFO order they maintain FIFO order, or first-in-first-out. The use-case for a queue are a bit more intuitive. For example, if there are many users who wish to run their programs on a remote server each request could be entered into a queue such that the requests are processed in the order in which they were received.

                            enqueue(x)       dequeue()           peek()
 original                       |               |                  |
                                v               v                  v
 +-----+ ← front            +-----+ ← front   +-----+ ← front   +-----+ ← front
 |  a  |                    |  a  |           |  b  |           |  b  |
 +-----+                    +-----+           +-----+           +-----+
 |  b  |                    |  b  |           |  c  |           |  c  |
 +-----+                    +-----+           +-----+           +-----+
 |  c  |                    |  c  |           |  x  |           |  x  |
 +-----+ ← back             +-----+           +-----+ ← back    +-----+ ← back
                            |  x  |
                            +-----+ ← back

                           x added to         a removed         b returned
                           the back           from front        but NOT removed
                                              returns a         returns b

------------------------------------------------------------------------------->
                                     Time

It does not take much turn a stack into a queue. I leave that as an exercise for the reader.

Following up on the case study for parsing postfix operators with a stack, we can use a stack in tandem with a queue to convert infix notation to postfix notation. The following algorithm was developed by Edsger Dijkstra in the early 1960s¹:

 1: while there are tokens to be read:
 2:     read a token
 3:     if the token is:
 4:     - a number:
 5:         put it into the output queue
 6:     - a function:
 7:         push it onto the operator stack 
 8:     - an operator o1:
 9:         while (
10:             there is an operator o2 at the top of the operator stack which is not a left parenthesis, 
11:             and (o2 has greater precedence than o1 or (o1 and o2 have the same precedence and o1 is left-associative))
12:         ):
13:             pop o2 from the operator stack into the output queue
14:         push o1 onto the operator stack
15:     - a ",":
16:         while the operator at the top of the operator stack is not a left parenthesis:
17:              pop the operator from the operator stack into the output queue
18:     - a left parenthesis (i.e. "("):
19:         push it onto the operator stack
20:     - a right parenthesis (i.e. ")"):
21:         while the operator at the top of the operator stack is not a left parenthesis:
22:             {assert the operator stack is not empty}
23:             /* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */
24:             pop the operator from the operator stack into the output queue
25:         {assert there is a left parenthesis at the top of the operator stack}
26:         pop the left parenthesis from the operator stack and discard it
27:         if there is a function token at the top of the operator stack, then:
28:             pop the function from the operator stack into the output queue
29: /* After the while loop, pop the remaining items from the operator stack into the output queue. */
30: while there are tokens on the operator stack:
31:     /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */
32:     {assert the operator on top of the stack is not a (left) parenthesis}
33:     pop the operator from the operator stack onto the output queue

Below represents the transformation of the above mentioned 6 + 4 / 2 into RPN:

token: 6          token: +          token: 4          token: /          token: 2

output: [6]       output: [6]       output: [6, 4]    output: [6, 4]    output: [6, 4, 2]

                  op stack:         op stack:         op stack:         op stack:
                  +-----+           +-----+           +-----+           +-----+
                  |  +  |           |  +  |           |  /  |           empty
                  +-----+           +-----+           +-----+
                                                      |  +  |           
                  6 is a value,     4 is a value,     +-----+           end of tokens:
                  push to output    push to output                      pop all operators
                                                      / has higher      to output
                                                      precedence        
                                                      than +, so push   
                                                      /                 

final output queue: [6, 4, 2, /, +]

I leave it as an exercise for the reader to implement this in C.

Pros:

• Keeps well-defined order

Cons:

• Elements cannot be easily retrieved without breaking order

1. Implement a stack in C using the vector you implemented in the previous lecture as the underlying data structure. Your stack should support all of the operations listed in the Stack API: init, push, peek, pop, is_empty, and free. Since your vector already handles dynamic resizing, your stack implementation should require very little additional logic.
2. Using your stack implementation, write a program that replicates the function call order behavior shown in Listing 1. Each time a function is "entered" push its name onto the stack and print the stack contents. Each time a function "leaves" pop it off and print the stack contents. Verify the output matches the diagram in the lecture.
3. Implement the RPN evaluator from the pseudocode in the lecture using your stack. Test it with the following expressions and verify each result:
   • 6 4 2 / + → 8
   • 3 4 * 2 + → 14
   • 5 1 2 + 4 * + 3 - → 14
4. Implement a queue in C. Consider what changes need to be made relative to your stack implementation to enforce FIFO rather than LIFO order. Your queue should support init, enqueue, dequeue, peek, is_empty, and free.
5. The lecture states that it "does not take much to turn a stack into a queue." Explain in your own words what the key structural difference is between the two. What changes in terms of where elements are added and removed?
6. Using your queue implementation, simulate a print queue. Write a program that enqueues five print jobs (represented as strings), then dequeues and prints them one at a time. Verify that they are processed in the order they were submitted.
7. Implement the Shunting Yard Algorithm from Listing 3 in C using your stack and queue implementations. Test it on 6 + 4 / 2 and verify the output queue matches [6, 4, 2, /, +]. Then pipe the result into your RPN evaluator from exercise 3 and verify the final result is 8.
8. Run your stack and queue implementations under valgrind to check for memory leaks. If any are found, identify which function is responsible and fix it. What is the most common source of memory leaks in data structure implementations?
9. The lecture lists "elements cannot be easily retrieved without breaking order" as a con of stacks and queues. Write a program that demonstrates this limitation by attempting to find a specific element in a stack without permanently destroying its contents. What strategy can you use to restore the stack after searching it?
10. The lecture presents two case studies showing stacks used for real computational tasks: function call management and RPN evaluation. Write a third use case of your own by implementing a program that uses your stack to check whether a string of parentheses is balanced. For example ((())) and (()()) are balanced while (() and )( are not. The algorithm is simple: push every opening parenthesis onto the stack and pop when a closing parenthesis is encountered — if the stack is empty when you try to pop, or non-empty when the string ends, the parentheses are unbalanced.
11. Implement a circular buffer in C with a fixed capacity of your choosing. Your implementation should support enqueue, dequeue, peek, is_empty, and is_full operations. Unlike your vector and stack implementations, the circular buffer should not resize — when it is full, attempting to enqueue should fail gracefully. Use two integer indices, a read pointer and a write pointer, to track the front and back of the buffer, and use the modulo operator to wrap them around the array. Test your implementation by filling the buffer to capacity, dequeuing a few elements, and then enqueuing new ones into the freed slots to verify the wrap-around behavior works correctly.