What are Stacks?

Stacks are a high level data structure allowing for a Last In First Out (LIFO) characteristic when adding and removing elements.

A good analogy to use when thinking about stacks is to think about plates. When you, your mom, and your dad finish eating each person puts his or her plate on the counter on top of the current stack of plates. If you finish first, then your mom, then your dad who's plate gets washed first? Let's look at this in more detail!

(Assume the leftmost element is the top of the stack)

You Finish {Y} Mom Finishes {M, Y} Dad Finishes {D, M, Y} If we look at the time when everyone finishes then your dad's plate will be washed first. Since your dad finished last and put his plate on top of everyone else's it only makes sense that his plate is the first one to be washed. This is the basic idea behind stacks, last in first out, or first in last out, whichever makes more sense to you. (They mean the same thing!)

Stack Operations

Operation Description Push puts an element on the stack Pop removes an element from the stack Peek returns what is on top of the stack without removing it Size returns the size of the stack

Why would I ever use a Stack?

Different problems are solved by using different data structures. Being able to retrieve elements in last in first out order is actually useful in many cases. Let's look at some examples to better illustrate some uses of stacks.

Ex1 - Copy a Linked List in reverse order

Since we are dealing with a Linked List, we have no idea how many elements there are in this list. If we linearly move through the list from the beginning until you hit the end of the list pushing each element onto a stack then we have the last element on top. Now to create the copy we can simply pop off of the stack and call each next element we see as the next element in the reverse ordering of the list. Seeing that the first element in the original list is on the bottom, this algorithm should be correct.

// Sample pseudocode
Function copyReversed ( List L )
{
  List R;
  Stack S;
  List P = L;
  
  While ( P.next is not null )
  {
    S.push(P.value)
    P = P.next;
  }
  
  While ( S.size() > 0 ) L.add(S.pop());
  Return R;
}

Ex2 - Auctions

If anyone has used eBay before, we all know that it records all of the previous bids from its users in any particular auction. We actually have two things to take into consideration when dealing with auctions; we need to handle an incoming bid and we need to be able to determine who the winner is if the auction time is up. The auction function will run until time is up, checking for incoming bids and noting if they are high enough to replace the current high bid. When time is up in the auction it will then return who the winner is. There are characteristics of the stack that will help us solve this problem. The current high bid or winner (if time is up) is the person who owns the bid on the top of the stack.

// Sample pseudocode
Global Stack S;
Function User Auction ()
{
  While ( more time to go )
  {
    If ( there is a bid B )
      If ( S.size() = 0  or B > S.peek().getBid() )
        S.push(B)
  }

  // Time is out here
  // The user that owns the highest bid is the winner.
  Return S.peek().getBid().getUser();  
}

This example is obviously an oversimplification and tailored to show how stacks can be used, which is really what the purpose of this article is. In reality an auctioning system is not run as threads in memory which is how the Auction() function is depicted.

So the next time you're stuck on a problem involving the ordering of elements it might be helpful to consider how the problem could be simplified by using a simple data structure that is the stack.

Want to learn more? Check out these resources to get you started!

• Wikipedia
• Stacks public lecture
• Data Structures for Game Programmers

Steven Phung
stphung@csupomona.edu
http://www.stevenphung.org