Representation of a Stack using a Linked List

February 23, 2023

Stack using LinkedList in C++

One of the basic linear user defined data structure that is also very useful to solve problems and implement tons of Graph theory algorithms is Stack. It follows the last in first out model and cann be implemented using LinkedList if you want to get its size changing dynamically. This is anarticle on the Representation of a Stack using a Linked List.

Representation of a stack as a linked list

What is Stack?

 

Stack is a data structure where you can add any kind of and store then in a LIFO (last in first out) manner.

If you want to know about The given stack Data structure in a C++ STL,here it goes: Stack in C++ STL

Representation of a stack as a linked list in C

The Algorithm Goes here: 

So here goes the algorithm about How to use a linked list to implement a stack. It is one of the easiest algorithms, if you know what a linked list is. Here we used the inbuilt STL List (List in C++ STL) as a linked list inside a ‘Stack’ named class, otherwise you can make a class or structure with pointers to make a Linked List.

  • Firstly, This is a LinkedList, where only the last element is visible. So you have only one place open to change in the list, that is the topmost node of the list.
  • So if you want to push values, you have to push them at the back. Only if the list is empty, you can push the first value in the first node.
  • If you want to pop values, only the topmost or the last pushed place is accessible. If the list is empty, no values can be popped, otherwise, the momentary topmost value is to be popped.
  • That is how you can achieve the model of Last in First Out.
  • So Here a class is made with a list member. Then values are added only at the back, same goes for the popping.
DSA desktop gif
DSA mobile gif

Stack Representation in C++

Representation of a Stack as an Array

Infix to postfix conversion

Infix to prefix expression

Postfix to prefix conversion

The code to implement this:

Run 
#include<bits/stdc++.h>
using namespace std;
class Stack
{
public:

  list < int >L;
  void Push (int i)
  {
    cout << "Pushing the element : " << (i) << endl;
    L.push_back (i);
  }

  int pop ()
  {
    if (L.empty ())
    {
	   cout << "The Stack is empty" << endl;
    }
    int a = L.back ();
    L.pop_back ();
    cout << "Popping the element : " << a << endl;
    return a;
  }

  void Show ()
  {
    cout << "The present Stack is:" << endl;
    for (auto i:L)
       cout << i << " ";
    cout << endl;
  }
};

int main ()
{

  Stack s;
  s.Push (5);
  s.Push (2);
  s.Push (11);

  s.Show ();
  s.pop ();

  s.Push (12);

  s.Show ();
}

Output:

Pushing the element : 5
Pushing the element : 2
Pushing the element : 11
The present Stack is:
5 2 11 
Popping the element : 11
Pushing the element : 12
The present Stack is:
5 2 12

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java