Welcome!
This page is the main page for Stacks
Subsections of Stacks
What is a Stack?
A stack is a data structure with two main operations that are simple in concept. One is the push operation that lets you put data into the data structure and the other is the pop operation that lets you get data out of the structure.
Why do we call it a stack? Think about a stack of boxes. When you stack boxes, you can do one of two things: put boxes onto the stack and take boxes off of the stack. And here is the key. You can only put boxes on the top of the stack, and you can only take boxes off the top of the stack. That’s how stacks work in programming as well!
A stack is what we call a “Last In First Out”, or LIFO, data structure. That means that when we pop a piece of data off the stack, we get the last piece of data we put on the stack.
Stacks in the Real World
So, where do we see stacks in the real world? A great example is repairing an automobile. It is much easier to put a car back together if we put the pieces back on in the reverse order we took them off. Thus, as we take parts off a car, it is highly recommended that we lay them out in a line. Then, when we are ready to put things back together, we can just start at the last piece we took off and work our way back. This operation is exactly how a stack works.
Another example is a stack of chairs. Often in schools or in places that hold different types of events, chairs are stacked in large piles to make moving the chairs easier and to make their storage more efficient. Once again, however, if we are going to put chairs onto the stack or remove chairs from the stack, we are going to have to do it from the top.
Stacks in Code
How do we implement stacks in code? One way would be to use something we already understand, an array. Remember that arrays allow us to store multiple items, where each entry in the array has a unique index number. This is a great way to implement stacks. We can store items directly in the array and use a special top variable to hold the index of the top of the stack.
The following figure shows how we might implement a stack with an array. First, we define our array myStack to be an array that can hold 10 numbers, with an index of 0 to 9. Then we create a top variable that keeps track of the index at the top of the array.
Notice that since we have not put any items onto the stack, we initialize top to be -1. Although this is not a legal index into the array, we can use it to recognize when the stack is empty, and it makes manipulating items in the array much simpler. When we want to push an item onto the stack, we follow a simple procedure as shown below. Of course, since our array has a fixed size, we need to make sure that we don’t try to put an item in a full array. Thus, the precondition is that the array cannot be full. Enforcing this precondition is the function of the if statement at the beginning of the function. If the array is already full, then we’ll throw an exception and let the user handle the situation. Next, we increment the top variable to point to the next available location to store our data. Then it is just a matter of storing the item into the array at the index stored in top.
function PUSH(ITEM)
if MYSTACK is full then
throw exception
end if
TOP = TOP + 1
MYSTACK[TOP] = ITEM
end functionIf we call the function push(a) and follow the pseudocode above, we will get an array with a stored in myStack[0] and top will have the value 0 as shown below.
As we push items onto the stack, we continue to increment top and store the items on the stack. The figure below shows how the stack would look if we performed the following push operations.
push("b")
push("c")
push("d")
push("e")
Although we are implementing our stack with an array, we often show stacks vertically instead of horizontally as shown below. In this way the semantics of top makes more sense.
Of course, the next question you might ask is “how do we get items off the stack?”. As discussed above, we have a special operation called pop to take care of that for us. The pseudocode for the pop operation is shown below and is similar in structure to the push operation.
function POP
if TOP == -1 then
throw exception
end if
TOP = TOP - 1
return MYSTACK[TOP + 1]
end functionHowever, instead of checking to see if the stack is full, we need to check if the stack is empty. Thus, our precondition is that the stack is not empty, which we evaluate by checking if top is equal to -1. If it is, we simply throw an exception and let the user handle it. If myStack is not empty, then we can go ahead and perform the pop function. We simply decrement the value of top and return the value stored in myStack[top+1].
Now, if we perform three straight pop operations, we get the following stack.
Basic Operations
We have already seen two basic stack operations: push and pop. However, there are others that make the stack much easier to use. These basic operations are:
push: places an item on top of the stack,pop: removes the item on the top of the stack and returns it,peek: returns the item on the top of the stack without removing it from the stack,isEmpty: returns true if there are no items on the stack, andisFull: returns true if our stack array is full.
We will discuss each of these operations. But first, let’s talk about the constructor for the stack class and what it must do to properly set up a stack object.
Constructor
The main responsibility of the constructor is to initialize our attributes in the stack class. As we discussed above, the attributes include the myStack array and the top attribute that keeps track of the top of the stack.
Since we are using an array for our stack, we will need to know how big to make the array in our constructor. There are two options. We could just use a default size for the array. Or, we could allow the user to pass in a positive integer to set the size. In this module we assume the caller must provide a capacity value, which must be greater than 0.
function STACKCONSTRUCTOR(CAPACITY)
if CAPACITY not an integer then
throw exception
else if CAPACITY <= 0 then
throw exception
end if
MYSTACK = new array[CAPACITY]
TOP = -1
end functionThe first thing we do in the code is to check to make sure that capacity is actually an integer that is greater than 0. Essentially, this is our precondition for the method. If our precondition is not met, we throw an exception. (If we are using a typed language such as Java, we can enforce our precondition by requiring that capacity be of type integer instead of explicitly checking it in the code.) Once we’ve validated our precondition, we create a new array of size capacity for the myStack array and set the attribute top to -1.
Push
We have already discussed the push operation and seen it in operation earlier in this module. In the pseudocode below, we see that we must first check to ensure that the stack is not already full. Again, this is our precondition. You may be picking up on the fact that the first thing we do in our methods is to check our precondition and throw an exception if it is not met. This is good coding practice.
function PUSH(ITEM)
if MYSTACK is full then
throw exception
end if
TOP = TOP + 1
MYSTACK[TOP] = ITEM
end functionOnce our precondition is validated, we simply increment top by 1 and store the item into the array at index top. We do not return anything from the push function. Also, notice that there are no loops in the push operation and thus the time it takes to execute the operation will always be the same regardless of the size of the myStack array. We call this constant time performance, which is typically very fast.
Pop
Like push, we have already seen the pop operation. It simply takes the top item off of the stack and returns it. However, once again we need to validate our precondition before getting into the body of the operation. For the pop operation, our precondition is that the stack must not already be empty, which is detected when top equals -1.
function POP
if TOP == -1 then
throw exception
end if
TOP = TOP - 1
return MYSTACK[TOP + 1]
end functionOnce we have validated our precondition, we simply decrement top by 1 and then return the previous item at the top of the stack (myStack[top + 1]). Like the push operation, the pop operation takes a constant time to execute.
IsFull
To allow the calling program to detect when the stack is full, we define an isFull operation. Notice that code external to the stack class cannot access the value of top and so it cannot simply check if top + 1 == length of myStack on its own. In this case, the operation is very simple as we only need to return the Boolean value of top + 1 == length of myStack as shown below. There is no precondition for isFull and isFull operates in constant time.
function ISFULL()
return TOP + 1 == length of MYSTACK
end functionIsEmpty
The isEmpty operation is very similar to the isFull operation except that we return the Boolean value of the condition top == -1 instead of top + 1 == length of myStack.
Peek
The peek operation returns the top item on the stack, without removing it from the stack. Like the pop operation it has the precondition that the stack must not be empty. The pseudocode for the peek operation is shown below. It is also a constant time operation.
function PEEK()
if ISEMTPY() then
throw exception
end if
return MYSTACK[TOP]
end functionNotice that we replaced the precondition check of top == -1 with a call to isEmpty, which produces the same result. The real benefit here is the readability of the code and the fact that we only have to code the top == -1 check in the isEmpty operation. This will make it easier to maintain the code in the future if we change the way we implement the stack.
DoubleCapacity
The doubleCapacity operation doubles the size of the array holding our stack. So, if we started with an array of size 4, the doubleCapacity operation will result in an array of size 8 with the contents of our original array stored in it. Unfortunately, most programming languages (like Java) do not simply let you double the size of the array. A noted exception to this is Python, which does allow you to directly extend an array.
In a traditional programming language, the easiest way to accomplish the doubleCapacity operation is to complete the following steps:
- Create a new array with twice the capacity of the existing array,
- Copy the contents of original array into the new array, then
- Point the
myStackarray at the new array.
The pseudocode for the doubleCapacity operation is shown below.
function DOUBLECAPACITY()
NEWSTACK = new array[length of MYSTACK * 2]
loop I from 0 to TOP
NEWSTACK[i] = MYSTACK[i]
end for
MYSTACK = NEWSTACK
end functionThe doubleCapacity operation is not a constant time operation. This is due to the fact that copying the contents of the original array into the new array requires us to copy each item in the stack into the new array individually. This requires N steps. Thus, we would say that doubleCapacity runs in the order of $N$ time.
HalveCapacity
The halveCapacity operation is like the doubleCapacity operation except that we now have a precondition. We must make sure that when we cut the space for storing the stack that we still have enough space to store all the items currently in the stack. For example, if we have 10 items in a stack with a capacity of 16, we can’t successfully perform halveCapacity. Doing so would only leave us a stack with a capacity of 8 and we would not be able to fit all 10 items in the new stack.
function HALVECAPACITY()
if TOP + 1 > length of MYSTACK / 2 then
throw exception
end if
NEWSTACK = new array[length of MYSTACK / 2]
loop I from 0 to TOP
NEWSTACK[i] = MYSTACK[i]
end for
MYSTACK = NEWSTACK
end functionToString
The toString operation returns a string that concatenates the strings representing all the items stored in an array. In most programming languages, each object class must implement the toString operation. For instance, in the stack below where each item is a character, if we called myStack.toString(), we would expect to be returned the string "K-State".
Notice that we must read the stack array from top (right) to bottom (left) to get the proper output string.
In the pseudocode below we first create an empty string and then loop through the stack from top to bottom (0) using the item’s own toString operation to create the appropriate output string. Notice that there are no preconditions for the operation. This is because if the stack is empty, the for loop is not executed and we simply return an empty string. However, because of the loop the toString operation runs in order N time.
function TOSTRING()
OUTPUT = ""
loop I from TOP to 0
OUTPUT = OUTPUT + MYSTACK[I].TOSTRING()
end for
return OUTPUT
end functionUsing Operations
The following table shows an example of how to use the above operations to create and manipulate a stack. It assumes the steps are performed sequentially and the result of the operation is shown.
| Step | Operation | Effect |
|---|---|---|
| 1 | Constructor | Creates an empty stack.
|
| 2 | isFull() |
Returns false since top is not equal to the capacity of the stack.
|
| 3 | isEmpty() |
Returns true since top is equal to -1
|
| 4 | push(1) |
Increments top by 1 and then places item $1$ onto the top of the stack
|
| 5 | push(2) |
Increments top by 1 and then places item $2$ onto the top of the stack
|
| 6 | push(3) |
Increments top by 1 and then places item $3$ onto the top of the stack
|
| 7 | peek() |
Returns the item $3$ on the top of the stack but does not remove the item from the stack. top is unaffected by peek
|
| 8 | pop() |
Returns the item $3$ from the top of the stack and removes the item from the stack. top is decremented by 1.
|
| 9 | pop() |
Returns the item $2$ from the top of the stack and removes the item from the stack. top is decremented by 1.
|
| 10 | pop() |
Returns the item $1$ from the top of the stack and removes the item from the stack. top is decremented by 1.
|
| 11 | isEmpty() |
Returns true since top is equal to -1
|
Using a Stack
Stacks are useful in many applications. Classic real-world software that uses stacks includes the undo feature in a text editor, or the forward and back features of web browsers. In a text editor, each user action is pushed onto the stack as it is performed. Then, if the user wants to undo an action, the text editor simply pops the stack to get the last action performed, and then undoes the action. The redo command can be implemented as a second stack. In this case, when actions are popped from the stack in order to undo them, they are pushed onto the redo stack.
Maze Explorer
Another example is a maze exploration application. In this application, we are given a maze, a starting location, and an ending location. Our first goal is to find a path from the start location to the end location. Once we’ve arrived at the end location, our goal becomes returning to the start location in the most direct manner.
We can do this simply with a stack. We will have to search the maze to find the path from the starting location to the ending location. Each time we take a step forward, we push that move onto a stack. If we run into a dead end, we can simply retrace our steps by popping moves off the list and looking for an alternative path. Once we reach the end state, we will have our path stored in the stack. At this point it becomes easy to follow our path backward by popping each move off the top of the stack and performing it. There is no searching involved.
We start with a maze, a startCell, a goalCell, and a stack as shown below. In this case our startCell is 0,0 and our end goal is 1,1. We will store each location on the stack as we move to that location. We will also keep track of the direction we are headed: up, right, down, or left, which we’ll abbreviate as u,r,d,and l.
In our first step, we will store our location and direction 0,0,u on the stack.
For the second step, we will try to move “up”, or to location 1,0. However, that square in the maze is blocked. So, we change our direction to r as shown below.
After turning right, we attempt to move in that direction to square 0,1, which is successful. Thus, we create a new location 0,1,u and push it on the stack. (Here we always assume we point up when we enter a new square.) The new state of the maze and our stack are shown below.
Next, we try to move to 1,1, which again is successful. We again push our new location 1,1,u onto the stack. And, since our current location matches our goalCell location (ignoring the direction indicator) we recognize that we have reached our goal.
Of course, it’s one thing to find our goal cell, but it’s another thing to get back to our starting position. However, we already know the path back given our wise choice of data structures. Since we stored the path in a stack, we can now simply reverse our path and move back to the start cell. All we need to do is pop the top location off of the stack and move to that location over and over again until the stack is empty. The pseudocode for following the path back home is simple.
loop while !MYSTACK.ISEMPTY()
NEXTLOCATION = MYSTACK.POP()
MOVETO(NEXTLOCATION)
end whilePath Finding Algorithm
The pseudocode for finding the initial path using the stack is shown below. We assume the enclosing class has already defined a stack called myStack and the datatype called Cell, which represents the squares in the maze. The algorithm also uses three helper functions as described below:
getNextCell(maze, topCell): computes the next cell based on our current cell’s location and direction;incrementDirection(topCell): increments a cell’s direction attribute following the clockwise sequence of up, right, down, left, and then finally done, which means that we’ve tried all directions; andvalid(nextCell): determines if a cell is valid. A cell is invalid if it is “blocked”, is outside the boundaries of the maze, or is in the current path (i.e., if it exists in the stack).
The parameters of findPath are a 2-dimensional array called maze, the startCell and the endCell. The algorithm begins by pushing the startCell onto myStack. The cell at the top of the stack will always represent our current cell, while the remaining cells in the stack represent the path of cells taken to reach the current cell.
Next, we enter a loop, where we will do the bulk of the work. We peek at the cell on the top of the stack in order to use it in our computations. If the topCell is equal to our goalCell, then we are done and return true indicating that we have found a path to the goal.
If we are not at our goal, we check to see if we have searched all directions from the current cell. If that is the case, then the direction attribute of the topCell will have been set to done. If the direction attribute of topCell is equal to done, then we pop the topCell of the stack, effectively leaving that cell and returning to the next cell in the stack. This is an algorithmic technique called backtracking.
function FINDPATH(MAZE, STARTCELL, GOALCELL)
MYSTACK.PUSH(STARTCELL);
loop while !MYSTACK.ISEMPTY()
TOPCELL = MYSTACK.PEEK()
if TOPCELL equals GOALCELL
return true
if TOPCELL.GETDIRECTION() = done then
MYSTACK.POP()
else
NEXTCELL = GETNEXTCELL(MAZE, TOPCELL)
INCREMENTDIRECTION(TOPCELL)
if VALID(MAZE, NEXTCELL) then
if MYSTACK.ISFULL() then
MYSTACK.DOUBLECAPACITY();
end if
MYSTACK.PUSH(NEXTCELL)
end if
end if
end while
return false
end functionHowever, if we have not searched in all directions from topCell, we will try to explore a new cell (nextCell) adjacent to the topCell. Specifically, nextCell will be the adjacent cell in the direction stored by the direction attribute. We then increment the direction attribute of the topCell so if we end up backtracking, we will know which direction to try next.
Before we push the nextCell onto the stack, we must first check to see if it’s a valid cell by calling the helper function valid. A cell is valid if it is open to be explored. A cell is invalid if it is “blocked,” is outside the boundaries of the maze, or is in the current path (i.e., if it exists in the stack). To help us determine if a cell is in the stack, we will need to extend our stack operations to include a find operation that searches the stack while leaving its contents intact. You will get to implement this operation in your project.
If nextCell is valid, we then check to make sure that the stack is not already full. If it is, we simply call doubleCapacity and continue on our way. Then we push nextCell onto myStack so it will become our next topCell on the next pass through the loop.
After we have explored all possible paths through the maze, the loop will eventually end, and the operation will return false indicating no path was found. While this is not the most efficient path finding algorithm, it is a good example of using stacks for backtracking. Also, if we do find a path and return, the path will be saved in the stack. We can then use the previous pseudocode for retracing our steps and going back to the startCell.
Stacks Summary
In this module we looked at the stack data structure. Stacks are a “last in first out” data structure that use two main operations, push and pop, to put data onto the stack and to remove data off of the stack. Stacks are useful in many applications including text editor “undo” and web browser “back” functions.