6.0 Data Structures – Stacks

A Stack is one of the most important data structures that are used in computer programming. It has many variations in its implementations. It also plays very important roles in operating systems implementation and programming languages capabilities.

To connect topics with each other, we have discussed Queues in the last post. We have seen how they are widely used in programming. In this post, I’m going to discuss the simplest implementation of a stack. And as usual, we will tackle the topic by talking about Stacks Specifications, Implementations and how to write a test driver for them.

Stacks Specification

– We want to group some items together.
– The order of the items in the data structure is very important. We want the first element we insert to be the last element we can get out of the stack.
– The stack must provide a way to insert elements from one end of the queue (the top end), and retrieve elements from the same end (the top end).
– We don’t sort items inside the queue (e.g. alphabetical sorting like lists). We just insert and retrieve.
Example: you are playing with colorful cube blocks. You put one above the other as in the figure. You put the green one on the top of the yellow cube. After that, you put the blue cube on top of the green one. And finally, you put the red one above all. If you tried to put the blue cube above the yellow one, you would have to remove the green one first. And to remove the yellow one directly, you will destroy what you have built. So, you have to add and remove cubes from one end, which is the top end. In computer science world, we call the stack data structure a Last-In First-Out (LIFO).

Let’s have a look at the specs written in code.

template<class ItemType>
class Stack{
public :
    Stack();
    bool IsEmpty() const;
    bool IsFull() const;
    void Push(ItemType item);
    void Pop();
    ItemType Top() const;
}

We have a constructor and some functions which play the role of inserting and removing elements from the stack. So Let’s see how to implement these function to meet the specifications.

Stacks Implementation

We will present the two approaches of implementing a data structure.

– Using Arrays –

The private data members we will have will be as follows.

class Stack{
private:
    int top;
    ItemType items[MAX];
};

The class maintains an array that holds the stack elements. to control access to these elements (only from one end), we hold top index which indicates the element at the top of the stack (the last element that has just been inserted. MAX is a constant integer that is declared globally and indicates the maximum elements that can be hold by a stack. It’s a very simple implementation!

Stack<ItemType>::Stack(){
    top = -1;
}

The constructor has one line that initializes the top index to be -1. This -1 indicate that there is no elements inserted to the stack.

bool Stack<ItemType>::IsEmpty() const{
    return (top == -1);
}

As we have just stated, if the stack is empty, the top index will be -1.

bool Stack<ItemType>::IsFull() const {
    return (top == MAX - 1);
}

The stack is full when all array elements are filled. This occurs when the top index points to the last array index, which is MAX-1.

void Stack<ItemType>::Push(ItemType item){
    if(IsFull())
        throw FullStack();
    items[++top] = item;
}

In stack context, when we insert a new item, we say that we push an item to the stack. This is because we deal with the stack from only one end. To push an element, we simply increment the top index and insert the that new item at the new index of the top. For example, in the first time top is -1. When inserting the first element, top is first incremented to be 0 and then we insert the new element at items[0]. When we insert the second element, top is incremented to be 1 and then we insert the new element at items[1]. And so on. Inserting too many elements without checking against the array size will result in run-time errors (when exceeding array bounds). So, every time we insert a new item, we check if the array is full, we throw an exception. The exception is defined before the class definition as follows.

class FullStack{};

You can refer to exception handling in C++ for more information. But this is not the case, we can print a warning message instead to indicate that the stack is full.

ItemType Stack<ItemType>::Top()const{
    if(IsEmpty())
        throw EmptyStack();
    return items[top];
}

The top function retrieves the top element of the stack, which is the last element inserted. If the stack is empty, it throws an EmptyStack exception. The exception is defined before the class definition as follows.

class EmptyStack{};

Note that Top() function doesn’t change the stack elements or removes that top element. It only get the value of the top element.

void Stack<ItemType>::Pop(){
    if(IsEmpty())
        throw EmptyStack();
    top--;
}

To remove the top element, we call it to Pop an element from the stack. we just decrement the index of the top to point to the element below the top. We don’t need to remove the value of the top element because it will be overwritten the next time we insert an element. The pop function first check if the stack is empty, to avoid run-time errors.

To get the big picture now, download the code file here, and review what we have come up to.
This is how we implemented stacks using the array approach. Let’s see implementation using linked nodes.

– Using Linked Nodes –

In the linked nodes approach, we represent the stack as group of nodes in which every one points to its successor. The node is the same that we use in every data structure.

struct Node{
    ItemType info;
    Node *next;
};

The node holds info variable and a pointer that connects it to the next node. The private data members of the Stack class will be as follows.

class Stack{
private:
    Node<ItemType>* top;
    int length;
};

From the stack definition, we only need to maintain a top pointer that points to the last element pushed into the stack (the top element). The length member is used to keep track of the number of stack elements (used to identify empty stacks).

Stack<ItemType>::Stack(){
    top = NULL;
    length = 0;
}

The constructor initializes the data members to be null for top element and of length zero. This is the state at which the stack will be at the initialization.

bool Stack<ItemType>::IsEmpty()const{
    return length == 0;
}

As we have just stated, the length is used to indicate whether the stack is empty or not. We also can check this situation by comparing the front with NULL.

bool Stack<ItemType>::IsFull()const{
    try{
        Node<ItemType>* temp = new Node<ItemType>;
        delete temp;
        return false;
    }
    catch(std::bad_alloc Exception){
        return true;
    }
}

As we have illustrated in the Queues post, the only situation that can prevent us from pushing a new element to the stack is when memory allocation fails to allocate a new memory space (in the heap). In the above code, we try to add a new node (dummy node not to be pushed into the stack). If the operation succeeded, we delete that temporary node and return false (i.e. it’s not full). Otherwise, an exception occurs and we return true (i.e. it’s full).

void Stack<ItemType>::Push(ItemType item){
    Node<ItemType>* newNode = new Node<ItemType>;
    newNode->info = item;
    newNode->next = NULL;
    if(top == NULL){
        top = newNode;
        length++;
    }
    else{
        newNode->next = top;
        top = newNode;
        length++;
    }
}

The above function describes how a new element is pushed. First, we initialize the new node. We have two situations. The first is when the stack is totally empty and it’s the first time to push an element. We simply makes that top pointer points to the new node. The second situation is when the stack holds some elements. We make the next pointer of the new node points to the first node of the stack (at this point, we have two pointers that points to the first node in the stack: top and the next pointer of the newly added node). Then, we make the top points to the newly added node. The figure shows this operation.

ItemType Stack<ItemType>::Top(){
    return top->info;
}

The top functions retrieves the value of the node pointed to by the top pointer (which is the node inserted).

void Stack<ItemType>::Pop(){
    Node<ItemType>* tempPtr;
    tempPtr = top;
    top = top->next;
    delete tempPtr;
    length--;
}

To pop an element from the stack, we need to remove the item pointed to be the top pointer. We initialize a new temporary pointer and make it point to the top node. After that we make the top pointer points to the node after the top (which will be the top node after deletion). After that, we delete that temporary pointer (which was just initialized to keep track of the first node to be deleted). We could have make the top points directly to the next node to the top. But this will leave the top node (that takes a memory space) at the heap which is bad practice. We have to remove the no more needed nodes to save memory space.
Note that, we have to check against the FullStack and EmptyStack situations when we push into and pop from the stack. I have removed the code snaps from the functions for simplicity. You can add them by your own (it’s just an if condition that throws an exception).

You can download the full linked stack implementation here.

Test Driver

The test driver is written to see the operation of the two functions (Push and Pop). It’s very straight-forward and indicates how the stack works. That is the last element pushed into the stack will be the first one to be popped from it. I will leave the test driver code for you to do it. It’s very similar to the test driver of the Queue with the EnQue replaced by Push and the DeQue replaced by Pop and Top. Try to write it down by your own and reply the post for any difficulties you face.

Conclusion

By now, we have covered most aspects of the stacks implementation. We use stacks in applications when we want to insert and retrieve items in a last-in first-out manner. One of the most common situations a stack is used is to for a programming language to implement a function recursion. In fact, what happens behind the scenes when we use recursion (a function that calls back itself), the run-time environment saves the states of the local variables and other related information into a stack. When, the program execution flash back to the caller, it pops the items from it. There are many other application uses for a stack. Search for them and try to test them!

In the next post, we will discuss Trees. So, stay tuned!

Your questions and feedback are very welcomed :).

6 thoughts on “6.0 Data Structures – Stacks

leave your feedback

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s