CSE 212 | Learning Activities

Learning Activity: Stacks

Overview

A stack is a data structure that is characterized by the order in which items are added and removed. Often called "Last In, First Out" (LIFO), the stack can be used to accomplish various tasks and there is a Stack class built into C#.

Preparation Material

Stack of Pancakes

If you were going to make pancakes for your family or friends, you probably would have a plate ready to stack the hot pancakes on as they finished cooking. Each time we put a pancake onto the stack, we call this a push operation. In our pancake example, we might say that each new pancake goes onto the top of the stack. In programming, it is also common to say that the pancake is added to the back. When we take a pancake off to eat, we call this a pop operation. Notice that we push and pop from the back of the stack. Removing from the middle of the stack is not generally allowed (especially at the dinner table). Notice that the pancake at the front is the very first pancake that was cooked. If the pancakes are made faster than they are eaten, then this first pancake would get cold. A LIFO (Last In, First Out) structure like the stack can result in data not being used for a long time. This might not work well for a rotating stock system in a grocery store, but the real benefit of the stack is the ability to remember where we have been.

The "Undo" Option and the Stack

One of the most common stacks that people use on a computer is related to the Undo option in word processors and editors. When we type something on the keyboard, the item is both displayed to the screen and also added to a stack. If we type the phrase "The rain in Spain stays mainly in the plain", we would expect the following commands to be put pushed onto the stack: Type "The", Type "rain", Type "in", and so forth. The last item to be pushed would be Type "plain". If we press the Undo button, the software will pop the stack and receive: Type "plain". The software will then do the opposite of this which would result in the word "plain" being removed from the screen.

Shows a computer screen and history stack with the initial text of The rain in Spain stays mainly in the plain. Changes to the screen and stack are shown as described in the text of this section. — Stack used to Undo Text

Since the stack is maintaining a history of what was typed, we can guarantee that pressing the Undo button will revert changes in the right order. If we popped five additional times, we would have "The rain in" remaining on the screen. If we type "Idaho stays mainly in Rexburg", we would see five new pushes to the stack. The original first three commands to display "The rain in" still remains at the front of the stack. If the Undo button is pressed enough times, then these initial words would eventually be removed.

Stacks are useful when we need to maintain history and perform an operation (for example, undo function in an editor) backwards.

Software and the Function Stack

Even if you didn't know what a stack was before today, we have actually been using stacks in all software we have written. When we call a function in our code, we are telling the computer two things:

Which function we want to call
Which function to go back to when we are done

The first of these is clear in our code. If we are currently in function A, then we expect to call function B. However, how do we tell the computer that we want to return to function A when function B is finished. This can be even more complicated by the fact that function B will need to call functions C, D, and E before it can finish. The computer accomplishes this by using a function stack. When a function is called, it is pushed to the stack. The current function running is always on the back of the stack. When the function finishes, it is popped off the stack. The result is that the function to return to is the one that is on the back of the stack.

Shows a structure chart of function A calling function B, function B called functions C and D (in order), and function D calling function E. Shows the function stack (front to back) when B is running (A, B), when C is running (A, B, C), when C finishes (A, B), when D is running (A, B, D), when E is running (A, B, D, E) and when B finishes. (A) — Function Stack in Programming

In addition to keeping track of the function name that is running, the stack also allows us to see where in the function we were when a function was originally called as well as the memory that we were using in our function. Stacks work well for remembering where we've been and the circumstances we were in during that previous time.

When using C# or other programming languages, we will often see error messages that look like the following. Notice that the information is showing which functions have called which functions up until the point of error. This display of information comes directly from the function stack. Here's an example of a call stack dump from an error during runtime:

Shows the call stack from a C# program running in Rider when the program died because of an array error. — C# Exception showing Function Stack

Many code editors also include a debugger. Debuggers can be used to pause execution of software so that we can see what is occurring within our code step-by-step. Part of the debugger capability is the display of the function stack (or frequently called the call stack) when the software is paused (due to a breakpoint or an exception).

Shows the call stack from a C# program running in Rider when a breakpoint was reached and paused the software. — Debugger showing Function Stack

Stacks in C#

In C#, a stack can be represented using an array of various data types. Because stack is a common data structure, the framework comes with a built-in Stack class. (See documentation). These methods are shown in the table below, along with the big O performance of them.

Common Stack Operation	Description	C# Code	Performance
push(value)	Adds "value" to the back of the stack.	`myStack.Push(value)`	O(1)
pop()	Removes and returns the item from the back of the stack.	`var value = myStack.Pop()`	O(1)
size()	Return the size of the stack.	`var length = myStack.Count`	O(1)
empty()	Returns true if the length of the stack is zero.	`if (myStack.Count == 0)`	O(1)

Video Discussion (Optional)

The following video is optional. It presents a brief discussion of the topic.

Activity Instructions

Complete each of the following:

Open the following snippet of code: SimpleStack.cs (Note: You should not execute this code. After you complete these practice problems, you are welcome to execute the code).
This code has a varied mix of push and pop operations performed on a stack. Individually, manually walk through the code and predict what the final contents of the stack will be. Even if you are good at keeping track of information in your mind, you should use a sheet of paper to keep track of the stack after each step.
When you are done, compare your your work to this solution. If you have questions, make sure to post them to Microsoft Teams.

Key Terms

back: Refers to the location in a stack where a push and pop occurs. The last item put into the stack is found in the back.
front: Refers to the location in a stack where the first item added to the stack can be found. Traditionally, this is index 0 of a dynamic array.
pop: The operation to remove the last item pushed to the stack. The item from the back of the stack is removed and returned.
push: The operation to add a new item onto the stack. The item is placed at the back of the stack.
stack: A data structure that follows a Last In, First Out (LIFO) rule. The stack is used to reverse data or remember previous data including previous results.

Submission

When you have completed all of the learning activities for this week, you will return to I-Learn and submit the associated quiz there.