Stack Implementation in C++ using Linked List

In this article, we will see how to implement stack in C++ using linked list.


Stack as an Abstract data Type

Stack is an ordered data structure to store datatypes in LIFO (Last In First Out) order. That means the element which enters last are first to exit(processed). It’s like a bunch of concentric rings kept one by one over others. Of course, the last one would be picked first when we start moving them out one by one (Tower of Hanoi). Stack is a similar data type where both insertion and deletion are done on the same side, namely top. Stack only hold similar datatypes.

The insertion process is named as Push

The deletion process is named as Pop


Operations on Stack

Type_t =any datatype

Basic operations:

Push(Type_t data): It inserts data of datatype Type_t to the stack

Type_t Pop(): Removes the topmost element from stack and returns it

Other operations:

Type_t top(): Returns topmost element

bool isEmpty(): returns true if stack is empty, else returns false

bool isFull(): returns false if stack is full, else returns false

int size(): Returns size of the stack


Stack Implementation using single linked list

A linked list is itself a data structure where every element has data and a pointer(next) to point the next element.

data next pointer

Each node like the above is a stack element

Pre-requisites

  1. Single Linked List class/struct
  2. top pointer

Let’s check an example to understand push and pop implementation

Example:

Let the elements inserted are

1, 2, 3

Stack using linkedlist

So to implement a stack with linked list,

When we push an element we actually do, inserting element at the head single linked list.

When we pop an element we actually do, deleting element from the head of single linked list.

C++ implementation:

Output:

press 1 for push

press 2 for pop()

press 3 for top()

press 4 for size()

press 0 for exit

press your choice

2

stack is empty

press your choice

1

Enter element

5

5 is pushed

press your choice

1

Enter element

7

7 is pushed

press your choice

2

Popped element: 7

press your choice

3

Top element: 5

press your choice

4

Size is: 1

press your choice

2

Popped element: 5

press your choice

2

stack is empty

press your choice

3

stack is empty

press your choice

4

Size is: 0

press your choice

1

Enter element

9

9 is pushed

press your choice

2

Popped element: 9

press your choice

5

Invalid number, try again!

press your choice

0

Exiting…

That’s all about Stack Implementation in C++ using Linked List

Was this post helpful?

Leave a Reply

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