Lecture 5. Stacks and Queues

Friday October 6

Today we will discuss use of Stack and Queue. These containers store data in an ordered format and are used to solve many problems.

Readings: Text 5.1 - 5.3, Class documentation for Stack and Queue
Lecture quiz on Canvas
QueueViz.zip
StackViz.zip

Contents

1. Announcements

2. Preliminaries: Client-Side Approach to ADTs

3. Stack Overview

4. Stack Examples in Code

5. Stack Applications

6. Vectors as Stacks

7. Queue Overview

8. Queue Examples in Code

9. Mod Operator (%)

10. Queue Applications

11. Stack Application: Postfix Notation

12. Grid Redux

13. What's next?

14. Practice Problems

Announcements

Assignment 1 is due Monday at 5 PM. Please be sure to head to LaIR early for help with these assignments (and to ensure that you don't get stuck in a really long queue). We appreciate your patience in LaIR. Please keep in mind we're doing our best to help a large number of students.

Solutions to this week's section problems are now posted to the course website. Be sure to work through any problems you found tricky or that your SL didn't have time to cover this week.

Your next batch of quizzes will be due Wednesday at 2 PM.

Preliminaries: Client-Side Approach to ADTs

I mentioned at the top of class today that we're currently taking a client-side approach to the ADTs we're exploring. That means we're exploring how to use them, but not their nitty-gritty, behind-the-scenes implementation details. However, we will discuss those implementation details later this quarter, after we've built up some additional requisite knowledge for doing so.

In the meantime, exploring ADTs from the client side empowers us to solve all kinds of interesting problems.

Stack Overview

Attachment: StackViz.zip

The first ADT we saw today was the stack. A stack is a LIFO (last-in, first-out) data structure. It generally supports a limited set of operations:

Member Function	Description
clear()	removes all elements from the stack
equals(stack)	returns true if the two stacks contain the same elements in the same order, false otherwise
isEmpty()	returns true if the stack contains no elements, false otherwise
peek()	returns the element on the top of the stack without removing it
pop()	removes the element from the top of the stack and returns it
push(value)	pushes value onto the stack
size()	returns the number of values in the stack
. . .	For an exhaustive list, see: Stanford Stack class

Notably, a stack does not support a search operation or an operation to find and remove an element with a specific value.

Before delving into actual code, we explored the behaviors of stacks through the StackViz program attached above.

Stack Examples in Code

To create a stack using the Stanford C++ Libraries, we must include the following:

#include "stack.h"

The syntax for creating a stack is as follows:

Stack< DATA_TYPE >  VARIABLE_NAME ;

(Important note!) We must capitalize the 'S' in "Stack" when declaring one in code. As with the other ADTs we have seen this quarter, C++ has its own built-in version of a stack that uses a lowercase 's'.

Here's the first example we saw of an actual stack in class today:

#include <iostream>
#include "console.h"
#include "stack.h"
using namespace std;

int main()
{
   Stack<int> s;

   s.push(10);
   s.push(20);
   s.push(15);
   s.push(12);

   while (!s.isEmpty())
   {
      cout << s.pop() << endl;
   }

   return 0;
}

output:

We also saw the following, which uses a stack to print the characters of a string in reverse order:

#include <iostream>
#include "console.h"
#include "stack.h"
using namespace std;

int main()
{
   string str = "hello";
   Stack<char> myStack;

   for (char ch : str)
   {
      myStack.push(ch);
   }

   while (!myStack.isEmpty())
   {
      cout << myStack.pop();
   }
   cout << endl;

   return 0;
}

output:

olleh

We also saw that we can print a stack using the << operator. This is super helpful for debugging, and we saw that C++'s built-in stack does not support that behavior:

#include <iostream>
#include "console.h"
#include "stack.h"
using namespace std;

int main()
{
   Stack<int> s;

   s.push(10);
   s.push(20);
   s.push(15);
   s.push(12);

   cout << "Stack contents: " << s << endl;

   return 0;
}

output:

Stack contents: {10, 20, 15, 12}

(Not mentioned in class.) We can also use the == and != operators to check whether two stacks are the same (i.e., they contain the same elements in the same order). For example:

#include <iostream>
#include "console.h"
#include "stack.h"
using namespace std;

int main()
{
   Stack<int> s1;
   Stack<int> s2;
   Stack<int> s3;

   s1.push(12);
   s1.push(10);

   s2.push(12);
   s2.push(10);

   s3.push(12);
   s3.push(10);
   s3.push(10);

   if (s1 == s2)
   {
      cout << "s1 == s2" << endl;
   }
   else
   {
      cout << "s1 != s2" << endl;
   }

   if (s1 == s3)
   {
      cout << "s1 == s3" << endl;
   }
   else
   {
      cout << "s1 != s3" << endl;
   }

   return 0;
}

output:

s1 == s2
s1 != s3

Stack Applications

Stacks come up all over the place in computer science. Here are a few of the applications we discussed today:

Stacks are useful for reversing things! See the example above in which we print the characters of a string in reverse order.
We talked about the call stack, which your programs use to keep track of which functions have been called in which order and where we need to return to when we hit the end of some function's execution.
Toward the end of class, I returned to stacks to talk about how they can be used to process arithmetic postfix expressions. (A write-up about that is included toward the bottom of today's notes.)

Vectors as Stacks

We saw that we could actually implement a stack using a vector. The following two programs effectively have the same functionality:

Stack approach:

#include <iostream>
#include "console.h"
#include "stack.h"
using namespace std;

int main()
{
   Stack<int> s;

   s.push(10);
   s.push(20);
   s.push(15);

   cout << s.pop() << endl;
   cout << "Stack contents: " << s << endl;

   return 0;
}

output:

15
Stack contents: {10, 20}

Vector approach:

#include <iostream>
#include "console.h"
#include "vector.h"
using namespace std;

int main()
{
   Vector<int> v;
   v.add(10);
   v.add(20);
   v.add(15);

   cout << v.remove(v.size() - 1) << endl;
   cout << "Vector contents: " << v << endl;

   return 0;
}

output:

15
Vector contents: {10, 20}

Notice, however, that the stack version is not only easier to read, but also less error prone. There is less code to parse (we can infer its semantics with a quick glance at the operations being performed), and we don't have to stop to consider whether we're pushing and popping at the correct index.

With the vector approach, we might have to stop to consider the relationship between v.add() and v.remove(v.size() - 1) to ensure we understand what the code is doing. Someone coding this up with vectors could also easily remove elements from the wrong end of the vector or have an off-by-one error that causes us to go out of bounds. Those problems simply don't exist with the stack approach, where the details of the s.push() and s.pop() operations are abstracted away from us and we can assume they work as intended.

Queue Overview

Attachment: QueueViz.zip

We then discussed the queue ADT. A queue is a FIFO (first-in, first-out) data structure. Like the stack, it generally supports a limited set of operations:

Member Function	Description
clear()	removes all elements from the queue
dequeue()	removes and returns the frontmost element in the queue
enqueue(value)	adds value to the back of the queue
equals()	returns true if the two queues contain the same elements in the same order, false otherwise
isEmpty()	returns true if the queue contains no elements, false otherwise
peek()	returns the frontmost element in the queue without removing it
size()	returns the number of values in the queue
. . .	For an exhaustive list, see: Stanford Queue class

Before delving into actual code, we explored the behaviors of queues through the QueueViz program attached above.

Queue Examples in Code

To create a queue using the Stanford C++ Libraries, we must include the following:

#include "queue.h"

The syntax for creating a queue is as follows:

Queue< DATA_TYPE >  VARIABLE_NAME ;

(Important note!) We must capitalize the 'Q' in "Queue" when declaring one in code. This distinguishes it from C++'s built-in queue, which has a lowercase 'q'. (You're seeing the trend here, yes?)

Here are the first examples we saw of actual queue code in class today:

⚠️ Warning! This doesn't work as intended!

#include <iostream>
#include "console.h"
#include "queue.h"
using namespace std;

int main()
{
   Queue<int> q;

   for (int i = 1; i <= 6; i++)
   {
      q.enqueue(i);
   }

   // This does not actually remove and print all elements from the queue!
   for (int i = 0; i < q.size(); i++)
   {
      cout << q.dequeue() << endl;
   }

   return 0;
}

output:

1
2
3

The following is a more conventional way to loop through a queue while emptying it out. Recall that a coding idiom is a good, solid, widely-used approach to accomplishing a particular task.

Idiom #1

#include <iostream>
#include "console.h"
#include "queue.h"
using namespace std;

int main()
{
   Queue<int> q;

   for (int i = 1; i <= 6; i++)
   {
      q.enqueue(i);
   }

   // Much better. :)
   while (!q.isEmpty())
   {
      cout << q.dequeue() << endl;
   }

   return 0;
}

output:

The following idiom can be used to loop through a queue while emptying it out (as we did above), but it can also be used to process all the original elements of a queue while adding others to the back:

Idiom #2

#include <iostream>
#include "console.h"
#include "queue.h"
using namespace std;

int main()
{
   Queue<int> q;

   for (int i = 1; i <= 6; i++)
   {
      q.enqueue(i);
   }

   // Keep track of original queue size. This loop will only do 6 iterations now,
   // even though we're adding some elements back into the queue as we go.
   int ogSize = q.size();
   for (int i = 0; i < ogSize; i++)
   {
      int val = q.dequeue();
      cout << val << endl;

      // Even values get added back to the queue.
      if (val % 2 == 0)
      {
         q.enqueue(val);
      }
   }

   cout << "Final queue contents: " << q << endl;

   return 0;
}

output:

1
2
3
4
5
6
Final queue contents: {2, 4, 6}

Mod Operator (%)

We briefly saw the mod operator (%) in the above example. Recall that the mod operator returns the remainder after division. So, 5 % 2 = 1, since 5 / 2 = 2 R 1. Similarly, 17 % 3 = 2 since 17 / 3 = 5 R 2.

Queue Applications

Queues come up all over the place in real-world applications. A few examples from today:

Purchase queues for online ticket sales.
Login queues for online games.
Printer queues for processing multiple print jobs.

We will see additional applications of queues later this quarter. There's at least one very common application of queues that we'll see when we get to our section on graph theory; they can be used to implement an algorithm called breadth-first search. A related algorithm, called depth-first search, can actually be implemented with a stack.

Stack Application: Postfix Notation

I then talked briefly about the complexity of processing an arithmetic expression such as "3 + 5 * 2 - 12 / (2 * 3)" and introduced the idea of postfix notation (also sometimes called Reverse Polish Notation). We can actually process a postfix expression token-by-token quite easily using a stack. The algorithm for that is as follows:

⚠️ Warning! The following algorithm assumes a valid, well-formed postfix expression as its input. There are some gotchas to consider if the postfix expression is not well-formed. (See Exercise #2 in today's practice problems.)

Let s be an initially empty stack.
For each token (tok) in your postfix expression:
- If tok is a numeric value:
  - Push tok onto s.
- If tok is an operator (+, -, *, /):
  - Let rightHandOperand = s.pop().
  - Let leftHandOperand = s.pop().
  - Apply the given operator (tok) to the leftHandOperand and rightHandOperand and push the resulting value onto s.
  - Note that the first value we pop above must be the right-hand operand, and the second must be the left-hand operand. This makes no difference with addition and multiplication, but it matters when performing subtraction and division.
Return s.pop().

For an example of this algorithm in action, skip to 47:05 in today's lecture video.

There is an algorithm for converting infix expressions to postfix expressions that also uses stacks. If you're interested, you can read more about that on GeeksforGeeks: https://www.geeksforgeeks.org/convert-infix-expression-to-postfix-expression/

Grid Redux

Finally, at the end of class, I rounded back to grids show the following:

We can send a grid directly to cout and get a nicely formatted string that conveys the grid contents.
We can use a for-each loop to loop through and display the contents of a grid. These are processed in a row-major fashion.
We can loop through all the valid coordinates in a grid as GridLocation objects, and those can be used to access specific grid elements.

#include <iostream>
#include "console.h"
#include "grid.h"
using namespace std;

int main()
{
   Grid<int> g(2, 3);

   g[1][0] = 50;
   g[1][1] = 33;

   cout << "Grid contents:" << endl;
   cout << g << endl;

   cout << endl << "Grid for-each loop:" << endl;
   for (int i : g)
   {
      cout << i << endl;
   }

   cout << endl << "Grid locations:" << endl;
   for (GridLocation loc : g.locations())
   {
      cout << loc << " (" << g[loc] << ")" << endl;
   }

   return 0;
}

output:

Grid contents:
{{0, 0, 0}, {50, 33, 0}}

Grid for-each loop:
0
0
0
50
33
0

Grid locations:
r0c0 (0)
r0c1 (0)
r0c2 (0)
r1c0 (50)
r1c1 (33)
r1c2 (0)

What's next?

On Monday, we'll examine two more ADTs: sets and maps.

Following that, we'll delve into two major topics that will stick with us for the rest of the quarter: recursion and Big-O runtime analysis.

Practice Problems

1. Write a function that processes a postfix expression using the stack-based algorithm discussed in class. The function should take two parameters: a string representing the postfix expression to be processed, and a reference to an integer where the final result should be stored. The function should return true if it successfully processes the given expression, false otherwise. If the function returns false, the reference parameter should remain unchanged. The function signature is as follows:

bool processPostfix(string expr, int& result);

For example function calls, see the test cases provided below.

For this problem, you may make the following assumptions:

If our postfix string is valid, all tokens will be separated with a single space. For example: "25 12 * 3 + 84 -"
If our postfix string is valid, all values will be integers, and the only operators will be +, -, *, and /

In completing this exercise, you might find the following functions from strlib.h useful:

stringSplit()
stringIsInteger()
stringToInteger()

Here are some test cases to get you started:

⚠️ Spoiler Alert! These test cases for invalid postfix expressions contain spoilers for Exercise #2.

#include <iostream>
#include "console.h"
#include "SimpleTest.h"
#include "stack.h"
#include "strlib.h"
using namespace std;

PROVIDED_TEST("valid postfix expressions")
{
    int result = 0;

    EXPECT_EQUAL(processPostfix("5 10 +", result), true);
    EXPECT_EQUAL(result, 15);

    EXPECT_EQUAL(processPostfix("3 8 *", result), true);
    EXPECT_EQUAL(result, 24);

    EXPECT_EQUAL(processPostfix("5 10 12 + -", result), true);
    EXPECT_EQUAL(result, -17);

    EXPECT_EQUAL(processPostfix("10 12 + 5 -", result), true);
    EXPECT_EQUAL(result, 17);

    EXPECT_EQUAL(processPostfix("5 2 * 3 + 4 -", result), true);
    EXPECT_EQUAL(result, 9);

    EXPECT_EQUAL(processPostfix("2 3 + 4 5 + *", result), true);
    EXPECT_EQUAL(result, 45);

    EXPECT_EQUAL(processPostfix("2 3 4 * + 5 +", result), true);
    EXPECT_EQUAL(result, 19);

    EXPECT_EQUAL(processPostfix("2 3 + 4 +", result), true);
    EXPECT_EQUAL(result, 9);

    EXPECT_EQUAL(processPostfix("2 3 4 + +", result), true);
    EXPECT_EQUAL(result, 9);

    EXPECT_EQUAL(processPostfix("2 3 1 * + 9 -", result), true);
    EXPECT_EQUAL(result, -4);

    EXPECT_EQUAL(processPostfix("10", result), true);
    EXPECT_EQUAL(result, 10);
}

PROVIDED_TEST("invalid postfix expressions")
{
    int result = 0;

    EXPECT_EQUAL(processPostfix("5 10 + +", --result), false);
    EXPECT_EQUAL(result, -1);

    EXPECT_EQUAL(processPostfix("3 8 * 0 / 5 +", --result), false);
    EXPECT_EQUAL(result, -2);

    EXPECT_EQUAL(processPostfix("", --result), false);
    EXPECT_EQUAL(result, -3);

    EXPECT_EQUAL(processPostfix("10 12 + 13", --result), false);
    EXPECT_EQUAL(result, -4);

    EXPECT_EQUAL(processPostfix("10 12 13 +", --result), false);
    EXPECT_EQUAL(result, -5);

    EXPECT_EQUAL(processPostfix("10 + 20", --result), false);
    EXPECT_EQUAL(result, -6);

    EXPECT_EQUAL(processPostfix("- 10 8", --result), false);
    EXPECT_EQUAL(result, -7);

    EXPECT_EQUAL(processPostfix("- 10", --result), false);
    EXPECT_EQUAL(result, -8);

    EXPECT_EQUAL(processPostfix("-", --result), false);
    EXPECT_EQUAL(result, -9);

    EXPECT_EQUAL(processPostfix("10 15 + sandwhich", --result), false);
    EXPECT_EQUAL(result, -10);
}

int main()
{
   runSimpleTests(ALL_TESTS);
   return 0;
}

2. What errors might we encounter while processing a postfix expression that would indicate that the expression was invalid or malformed? Modify your solution to the previous problem to account for each of these scenarios.

Highlight for solutions:

Encountering a token in our input string that is neither an integer nor a valid operator.
Encountering an operator in our expression when stack.size() < 2. In this case, we don't have enough operands to perform the desired operation.
Encountering division by zero.
Encountering a final stack with stack.size() != 1. If there is nothing in the stack when we finish processing our expression, or if the final stack contains multiple values, the original expression must have been malformed.

3. In the test cases for invalid postfix expressions given above (in Exercise #1), result is being decremented with each new test case. What benefit does this have compared to simply setting result = -1 and always checking that result is still -1 when returning from each of those individual test cases?

Highlight for solution: If we always check that result is -1 in those test cases, someone might think the goal of processPostfix() is to set result equal to -1 in the event that a postfix expression is malformed, and if they did so, they would get a false sense of security from passing all those test cases. In actuality, the function is supposed to leave that parameter completely unchanged when it encounters a malformed postfix expression. Changing result before we make a new call to processPostfix() with a malformed expression -- and checking that its value is unchanged when we return from that function -- more clearly conveys (and tests!) that desired behavior.

4. As always, be sure to trace through all the code presented in class today to ensure that you understand how it works. Ideally, you should take a break after reviewing today's notes and then try to replicate many of those examples from scratch.

5. Be sure to review the section in today's notes labeled "(Not mentioned in class.)"