Stacks

A stack is a special type of list, where only the element at one end can be accessed. Items can be "pushed" onto one end of the stack structure. New items are inserted before the others, as each old element moves down one position. The first element is referred to as the "top" item, and is the only item that may be accessed at any time. In order to access items that are further down the stack, they must be moved to the top by "popping" the appropriate number of items. Popping refers to removing the top element of a stack. This is referred to as a LIFO structure, "Last In, First Out".

These rules make stacks very restricted in use, however they are very efficient and much easier to implement than lists. The uses of stacks vary from programming a simple card game, to maintaining the order of operations in a complex program. For example, a stack is useful in a management program where the newest tasks must be executed first. The node of a stack is usually presented with the following structure, which is very similar to that of a list node.

template <class ItemType>
struct StackNode
{
   ItemType data;
   StackNode<ItemType> *next;
};

Implementing a generic stack class, which can be modified to work in any type of programming situation is very easy to do. A definition of such a class is shown below.

template <class ItemType>
class Stack
{
public:
   Stack(); //class constructor - initialize private variables
   ~Stack(); //class destructor - free up used memory
   void push(const ItemType); //add a new node to the top of the stack
   ItemType pop(); //remove the top node and return its contents
   ItemType top() const; //return the top node without popping it
   void clear(); //delete all nodes in the stack
   bool IsEmpty() const; //return true if the stack has no elements
   bool IsFull() const; //return true if there is no free memory for new nodes
   int count() const; //return the amount of nodes on the stack
private:
   StackNode<ItemType> *top; //pointer to the top node in stack
   int counter; //maintain the amount of nodes in the stack
};

The class constructor sets counter to zero. Since there are no nodes in the stack when an instance of the class is first created, top is set to NULL.

template <class ItemType>
Stack<ItemType>::Stack()
{
   counter = 0;
   top = NULL;
}

The role of the destructor is to delete all nodes in the list, and return the memory they occupy to free store. Since the clear() function does this task, it can be called by the destructor.

template <class ItemType>
Stack<ItemType>::~Stack()
{
   clear();
}

The push() function inserts a new node on top of the stack, and sets the top pointer to reference this new node. First, we check if there is enough system memory to create a new node, and then create the node, assigning it to top. The node's value is set equal to item, and its next component is set to the node that was on top before the creation of the new node.

template <class ItemType>
void Stack<ItemType>::push(const ItemType item)
{
   assert(!IsFull()); //abort if there is not enough memory to create a new node
   StackNode<ItemType> *tmp = new StackNode<ItemType>; //create a new node on top of the others with value item. set the original top node to follow the new one.
   tmp->data = item;    tmp->next = top;    top = tmp;    counter++; //increment the amount of nodes in the stack
}

The pop() function removes the top node from the stack (freeing up the memory it uses) and returns its value. top is set to the next node in the stack, and a temporary local variable(tmp) is created to point to the original top node. It is then used to reference the memory address of the node to delete. If we were to delete the node using top as a reference, the position of the next node in the stack would be lost, since top->next would no longer exist.

template <class ItemType>
ItemType Stack<ItemType>::pop()
{
   assert(!IsEmpty()); //abort if the stack is empty, no node to pop
   ItemType item = top->data; //maintain top value, to be returned later
   StackNode<ItemType> *tmp = top; //create a temporary reference to the top node
   top = top->next; //set top to be the next node
   delete tmp; //delete the top node
   counter--; //decrement the amount of nodes in the stack
   return item; //return the original top value
}

The top() function simple returns the value of the top node, without any modifications to the stack.

template <class ItemType>
ItemType Stack<ItemType>::top() const
{
   assert(!IsEmpty());
   return top->data;
}

The clear() function delete all nodes in the stack, and frees the memory they occupy. Each node in the stack is visited using a loop, which executes until it reaches a NULL reference. A temporary variable is used for the same reason as in the list implementation. If we were to delete a node using top as a reference, the position of the next node in the list would be lost, since top->next would no longer exist.

template <class ItemType>
void Stack<ItemType>::clear()
{
   StackNode<ItemType> *tmp;
   while(top != NULL) //loop through every node in the stack
   {
      tmp = top; //reference the top node
      top = top->next; //set top to the next node
      delete tmp; //delete the original top node
   }
}

The IsEmpty() function returns true if the stack has no nodes. This task is accomplished very simply by checking to see if the top pointer is NULL.

template <class ItemType>
bool Stack<ItemType>::IsEmpty() const
{
   return (top == NULL);
}

The IsFull() function checks to see if there is enough system memory avaliable to create a new node for the stack. It works exactly the same way as it did in the linked list class. A node is "created" using the new command, which is then evaluated. If the new command had failed to set aside the necessary memory, its value is NULL, in which case the function returns true. If the new node is created successfully, it is deleted, and the function returns false.

template <class ItemType>
bool Stack<ItemType>::IsFull() const
{
   StackNode<ItemType> *tmp = new StackNode<ItemType>;
   if(tmp == NULL)
      return true;
   else
   {
      delete tmp;
      return false;
   }
}

The count() function returns the amount of nodes in the stack, which is maintained by the class' private counter member. Again, this value can be maintained using a public member which the programmer can access directly, however it is good practice to hide this value from the programmer, since it can be modified without any nodes being added or removed. Also, if we were to change the class implementation, a program using the stack class would not require any change, since all the new code will be written in the count() function.

template <class ItemType>
int Stack<ItemType>::count() const
{
   return counter;
}