Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Like
0Likes
Dislike

Back to Basics: Stacks

By Steven Phung | Published Sep 04 2007 05:23 AM in General Programming

stack list first time element stacks last bid top
If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource



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!


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






Comments

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS