ADTs: stacks and queues

This page is very incomplete. I strongly recommend that you read the appropriate sections of Sedgewick's Algorithms book.

• The most important functions for a stack are push and pop. Push adds an item to the stack, on the top of the stack. Pop removes the top item from the stack. Notice that items may only be added or removed in one place: the top of the stack. This is a LIFO data structure: the Last item In is the First item Out. We can implement a simple stack using an array to store the items in the stack and an integer to keep track of the number of items on the stack. Here's some code:

  int s[10];      /* stack can hold a max of 10 ints */
  int num = 0;    /* number of items on stack, initially 0 */
     
  void push(int item)
  {
     s[num] = item;   /* add new item to stack */
     num++;           /* adjust item count */
  }
     
  int pop()
  {
     num--;           /* adjust item count */
     return s[num];   /* return item on top of stack */
  }

  Notice that since elements in an array are indexed from 0 to n-1, the first item on the stack will be put into s[0], the second into s[1], and so on. If there are k items on the stack, then they are stored in s[0] -> s[k - 1], so the next item we push onto the stack should be placed in s[k].
  
  So, if the top item of a stack is stored at s[num - 1], we need to subtract 1 from num before we return the element. Notice also that it was important to update num before we returned the element, since the return statement will be the last one executed in the function.
  
  With an array-based implementation of a stack, you need to be careful not to push an element onto a full stack. Also, keep in mind that popping an item from the stack doesn't actually remove it from the array. You can't 'remove' an item from an array. You can only over-write one element with another. So, if you execute a 'pop' and then a 'push', the new item will be written to the array in place of the old one.

• There are many applications for stacks in computer science. One basic one to think about is the problem of determining whether parentheses are balanced. Consider: ( ( ) ( ( ) ( ) ) ) or ( ( ) ) ) ( ( ). It's not enough to just count the number of 'lefts' and the number of 'rights': you need to match-up pairs. A simple algorithm for solving this problem is: if you read a left parentheses, push it onto the stack. if you read a right parentheses, pop an item from the stack. if you attempt to pop when there is nothing on the stack, then the parentheses aren't balanced. if you finish reading the whole string of parentheses and the stack isn't empty, then the parentheses aren't balanced. Try it!
  
• The operations of a queue are 'put' and 'get' (although you will sometimes see alternative names like 'enqueue' and 'dequeue'). Put adds an item to the queue. Get removes an item. An easy way to think about a queue is to consider a line for movie tickets. Each person who enters the line must get on the end of it. People leave the line from the front, as each person buys his/her ticket. This data structure is FIFO: the First item In the queue is the First item Out of the queue. put adds an element to the end of the queue, and get takes the first item off the front of the queue.
  
• Implementing a queue with an array is slightly more complicated than implementing a stack, because you have to worry about a 'start' and an 'end' instead of just a 'top.' So, you will need two integer variables to keep track of these indices instead of just 1. And you will also have to deal with 'wrapping' the array so that it is circular. That is, array element 0 follows array element (size - 1). Try to work on the implementation for a queue on your own: send me email if you have questions.

Questions from Students

1. I am having a really hard time getting exerise #2 about stacks and queues...could you explain a bit.
   • Here's what the stack will look like at each step:

                                 T       U   T
                           R   S S S   O O O O O
                         I I I T T T T T T T T T T
               I   N   F F F F F F F F F F F F F F F
             T T T T T T T T T T T T T T T T T T T T T
       A   S S S S S S S S S S S S S S S S S S S S S S S
     L L L L L L L L L L L L L L L L L L L L L L L L L L L
     -----------------------------------------------------
     L A * S T I * N * F I R * S T * * O U * T * * * * * *
     

     s[0] always holds the bottom of the stack, if there's anything on it (or s[0] holds whatever was last at the bottom of the stack, if there's nothing on it.) So s[0] is L. Then, even though everything else has been 'popped', S, T, F, and T were the last items in s[1]-s[4]. So the answer should be LSTFT. (The solution is off-by-1.)
     The confusing part (I think) is that at the end, you have only L on the stack and you're asked for s[0]-s[4]. So your intuition is that s[1]-s[4] are EMPTY. The thing you need to remember, though, is that they're not empty. You can never 'take something out of an array.' You can only overwrite an existing value with a new one. So, when you 'pop' an element of a stack that has been implemented with an array, all you really do is subtract one from an integer variable that is keeping track of the position of the top of the stack. So even though the stack doesn't have the item in it, the array still does. That's why, at the end, the array still holds the last letters that were stored on the stack. If the question asked for the contents of the stack at the end, just 'L' would be the right answer.