Skip to main content

How Stacks works

· 6 min read
Strider

A stack is a data structure which is used in many areas, e.g. in CPUs, in network technology under Linux(TCP/IP stack), or also generally with other algorithms like e.g. PDAs, depth search in graphs, etc....

Stacks are nothing else than stacks that work according to the LIFO principle. LIFO is Last In First Out, so what was put down last is also taken down first, similar to the office. A small sketch shows how a stack is structured.

dia.png

Here we see a stack that already contains elements, the elements can be anything from numbers, strings, or whole shellcodes to exploits and much more. The red arrow shows that we put the record "DDDD" on the stack, this is the push operation. The more stuff you put on the stack, the bigger it gets. The blue arrow shows the direction in which the stack grows. The red arrow represents the pop operation, which takes the first item, on top of the stack, back down. In this case the record "DDDD".

The element is then no longer on the stack, so it is deleted. Another operation is represented by the red arrow, the peek operation where only the element on top of the stack is read but not deleted. The white arrow represents the stack pointer or the current top element on the stack.

All operations push, pop and peek have an overhead of O(1)O(1), since there is no need to wander through the stack.

You can easily make stacks from simply chained lists. I have a small code example here. We just take the Node.cpp and the Node.h from the Linked-List post. We create a class stack that illustrates the example from above quite well.

#include <iostream>
#include "Node.h"
class Stack
{
private:
    Node* top = nullptr;
    int _max = INT32_MAX;
    int _size = 0;

public:
    Stack();
    Stack(int max);
    ~Stack();
    void push(int data);
    int pop();
    int peek();
    void show();
    int size();
    bool empty();
    bool full();
};

If we look at the header file, we can see that the structure is similar to the List.h. Here a few methods were taken over. We have here the method push which puts our data on the stack. A method pop which reads and removes our data set on the stack. The special method peek, which works similar to pop without deleting the data.

Show will later output the complete stack. The method size should show the size of the stack and the number of nodes. Very important are the methods full and empty, because they are needed for the push, pop and peek to check if the stack is full or empty, otherwise errors will occur.

We have two constructors for our stack, a default constructor and one that defines the maximum size of our stack. By default, the stack size 2312^{31} is defined here in the default constructor. And we have a destructor that deletes our stack completely.

Stack::Stack() {}

Stack::Stack(int max)
{
    if(max < 0)
    {
        max *=-1;
    }
}

If we look at the lower constructor here, we see that it is checked whether, size our is negative as a passing parameter as a maximum. If this is the case, the maximum is simply made positive. Here one can use also alternatively abs(), which here times times not made.

int Stack::size()
{
    return this->_size;
}

bool Stack::empty()
{
    return (this->top == nullptr); 
}

bool Stack::full()
{
    return !(this->_size < this->_max);
}

We consider the three methods size, empty and full. The size method returns the size (number of elements) in the stack. The empty method checks if the stack is empty, because the stack pointer top is always set to a nullptr when empty. To check if the stack is full we compare the current size with our maximum, this is exactly what the method full does.

Let's move on to our push operation. With this operation we can put data on our stack. Here we have the overhead O(1)O(1), since we don't have to do anything other than instantiate a node, and populate it with data. After that, we just need to set the new node, top as successor and set our new node as top. After that we only need to increase the _size attribute by 1. Important here is now the part that we should check here if the stack is full and if necessary abort here if this is the case.

void Stack::push(int data)
{
    if(full())
        return;

    Node *node = new Node(data);
    node->Next(this->top);
    this->top = node;
    this->_size++;
}

The pop operation has the same overhead as the push operation. But here the element on the stack is read and removed afterwards. First we check if the stack is empty. If this is the case nothing has to be done and we simply return -1. Otherwise the record is read and temporarily stored. The node where our stack pointer top points to is deleted and then _size is decreased by 1. Then the temporarily stored record is returned.

int Stack::pop()
{
    if(empty())
        return -1;

    int v = this->top->value();
    Node * temp = this->top;
    this->top = temp->Next();
    temp->Next(nullptr);
    delete temp;
    this->_size--;
    return v;
}

The Peek operation works as mentioned, similar to Pop. But here the record is not deleted.

int Stack::peek()
{
    if(empty())
        return -1;
	return this->top->value();
}

The show method that should output our stack is split into two cases. The first case is that the stack is empty, in which case only two square brackets are output. The other case similar to the simple chained list, to completely wander through the stack and output everything. Here we have an effort O(n)O(n) if the stack is not empty. Otherwise O(1)O(1) if the stack is empty.

void Stack::show()
{
    if(this->top == nullptr)
    {
        std::cout << "->[]" << std::endl;
        return;
    }

    std::cout << "->[";
    Node * ptr = this->top;
    while(ptr != nullptr)
    {
        std::cout << ptr->value() << "| ";
        ptr = ptr->Next();
    }

    std::cout << "]" << std::endl;

}

The destructor that is supposed to remove all elements when deleting the stack to free memory is also split in two cases. Once when the stack is empty, only the stack pointer top must be deleted. Otherwise, wander through the stack and delete each element individually. Here we also have an overhead O(n)O(n) if the stack is not empty.

Stack::~Stack()
{
	if(this->top != nullptr)
	{
		Node*ptr = this->top;
		while(ptr->Next() != nullptr)
		{
			Node * temp = ptr;
			ptr = ptr->Next();
			temp->Next(nullptr);
			delete temp;
		}

        delete ptr;
	}
    else
    {
        delete this->top;
    }
}

Small fun fact: The stack normally grows downwards, but the heap grows upwards. A small sketch shows the approximate structure in memory.

memory.png

I hope I could give a little insight in the stack data structure 😄