How to implement stack using linked list in c++

Stack is one of the basic data structure of the computer science. In modern computer technology random access memory (RAM) is used as stack to store the register’s (accumulator) of CPU on each interrupt or context change. Context change can be explained as; Let’s imagine while cpu is executing a process, operating system decides to run another process which has a higher priority, then current register data is pushed to memory (RAM) to take a snapshot of first process. After while when operating system decides to execute the first process again. Snapshot is popped from RAM to resume initial execution.

Stack can be also implemented on higher level computing languages such as c, c++ or Java. In this post I will show how to implement stack using linked list in c++.

How to implement stack using linked list in c++

Class Node represents the data which stack will store.  Class Node has two attributes; the data itself and the reference to next node which may be NULL on different circumstances.

Class Stack represents the stack itself. Class has two attributes; A reference to the top node and the current size of stack. Most important functions of Stack class are push and pop.

Push function takes the data itself or Node reference. When the push function is called with parameter data, the function allocates new Node reference with the parameter data and calls the other Push function to store node to the stack.

Pop function returns the last pushed Node’s data and decrease the stack size by one.


Note: this Stack implementation uses LIFO (Last In First Out).

To compile the source code with gcc, copy and name the following code block as stack.cpp and run the following command on console.

g++ stack.cpp -o stack

To run the compiled code.

./stack

#include <iostream>

template< class T >
class Node
{
public:
    Node(T data)
	{
		this->data = data;
		this->next = NULL;
	}
	
	~Node()
	{
	}
	
	T getData() const
	{
		return this->data;
	}
	
	Node< T >* getNext()
	{
		return this->next;
	}
	
	void setNext(Node< T >* node)
	{
		this->next = node;
	}
	
	void setData(T data)
	{
		this->data = data;
	}
	
protected:

	T data;
	Node* next;
};

template < class T >
class Stack
{
public:

	Stack()
	{
		this->top = NULL;
		this->size = 0;
	}
	
	~Stack()
	{
		Node < T > *temp = this->top;
		
		while ( temp != NULL )
		{
			Node< T >* current = temp->getNext();
			std::cout << "Deallocation : " << temp->getData() << std::endl;
			delete temp;
			temp = current;
		}
	}
	
	bool isEmpty()
	{
		return this->top == NULL;
	}
	
	void push(T t)
	{
		Node< T >* node = new Node< T >(t);
		this->push(node);
	}
	
	void push(Node< T >* node)
	{
		std::cout << "Push : " << node->getData() << std::endl;	
		if( this->top == NULL )
		{
			this->top = node;
			this->top->setNext(NULL);
		}
		else
		{
			node->setNext(this->top);
			this->top = node;
		}
		this->size += 1;
	}
	
	T pop()
	{	
		Node< T > *temp = this->top;
		this->top = top->getNext();
		
		std::cout << "Pop : " << temp->getData() << std::endl;
		this->size -= 1;
		return temp->getData();
	}
	
	void printStack()
	{
		Node< T > *current = this->top;
		
		std::cout << "Size of the stack : " << this->size << std::endl;
		
		while( current != NULL )
		{
			std::cout << current->getData() << std::endl;
			current = current->getNext();
		}
	}
	
	int getSize() const
	{
		return this->size;
	}

protected:

	Node< T >* top;
	
	int size;
};

int main(int argc, char **argv)
{
	Stack< int >* stack = new Stack< int >();
	
	stack->push(4);
	stack->push(2);
	stack->push(6);
	int popped_int = stack->pop();
	
	std::cout << "Popped node : " << popped_int << std::endl;
	
	stack->push(12);
	stack->push(67);
	stack->push(6);
	stack->printStack();
	
	int poppedNode = stack->pop();
	std::cout << "Popped node : " << poppedNode << std::endl;
	
	stack->printStack();
	
	delete stack;
	
	return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *