Taking it From the Top, and Putting it There, Too

The Concept of stacks

This topic is the first of two related to special applications of data structures. The stack is as literally definitive as it could be. If you will picture some children's blocks stacked up, you will understand the data structure. Here is one block in a stack.

Here is another block on the stack. The procss of adding a block is said to be pushing a block onto the stack.

Now to some rules that should be intuitive. This data structure only allows access from one place: The top of the stack. Just as it wouldn't work to try to pull blocks out from below the top, it is not allowed to take data out from below the top of the stack data structure. Again, the block ("E") is said to be pushed onto the stack. The next operation will push an "I" onto the stack as shown.

So far, this shouldn't be too complicated, and it isn't. The next process is to remove or "pop" a value from the top of the stack. This leads to the next result, which shouldn't be too surprising.

That said, if another value is "pushed" onto the stack, it just goes back on top, as shown.

That's it. You now know everything you need to know about stacks, although you might want to know that stacks use a Last In First Out or LIFO strategy, which of course, makes sense. It's just not difficult. Next, creating stacks with a couple kinds of supporting data structures will be discussed.

Stacks, with Arrays

As you might expect for a data structure such as this one, the code is not terribly complicated either. In an array situation, there will be an array that starts at index zero and "top" index that will also start at zero. The top index can be named anything but a good variable name could be size which would be self descriptive. The array capacity must also be considered so that the stack doesn't overgrow the array capacity but that is not critical for this discussion, and is easy to manage. With that in mind, the code would like the following.

   stackArray[ size ] = pushedValue;

   size++;

Again, not complicated. To pop a value off the stack takes the reverse action, shown here.

   size--;

   poppedValue = stackArray[ size ];

Obviously, some kind of testing must be conducted prior to the push process so the stack does not attempt to outside the array capacity, and there are some other array management conditions to be managed, but this is about it for the stack data structure.

Stacks, with Linked Lists

Linked lists do not offer too much more complexity. Pushing a value on to the stack requires a two-stage approach. Step one is to handle the empty stack condtion, and step two is to handle all the rest. Consider the pseudo code here.

   // check for empty stack
      {
       // assign a new node to the head pointer
      }

   // otherwise, assume list not empty
      {
       // loop while current node's next pointer is not null
          {
           // advance working pointer
          }

       // append new node to last linked list node
      } 

Like the one above for arrays, this strategy will work for both C or C++, or for that matter, almost any other programming language. It still doesn't get any more complicated.

The pop process is a little more complicated since you have to deal with the empty case and the single node case before you start iterating through the rest of the list, and you must return the value that was popped. Consider the following pseudo code.

    // initially set return value to default/failure value

    // check for list not empty
       {
        // check for only one node
           {
            // get value from head node

            // return data to OS

            // set node to NULL
           }

 
        // otherwise, assume at least two nodes
           {
            // loop while current node's next node's next node is not empty
               {
                // advance working pointer
               }

            // get value from node to be removed

            // return memory of node to OS

            // set next node's next node to NULL
           }

        // return acquired value, or failed indication
       }

Stacks are a good opportunity to practice your array and/or linked list management skills but they really aren't too complicated. The same can be said for queues, which are coming up in the next topic. Stay tuned.