ScaleFree

DS & A(Stacks - Pointer Based)

In the previous chapter, we talked about Array Based Stacks so continuing our discussion on Stacks, In this chapter, we will see how to implement pointer-based Stacks also known as Linked Stacks.

Visual Representation:


Properties of Linked Stack:

  • Follows LIFO principle and all the other general properties of a stack.
  • Unlike Array-based stack it's size is not fixed. Its size grows with the addition of new elements.
  • A Linked Stack can have head and tail pointers but it is not mandatory.
Stack ADT:

  1. template<typename e> class Stack{
  2. public:
  3.     //Function to insert a value at the pop of the Stack
  4.     virtual bool push(const e& item) = 0;

  5.     //Function to remove top-most Stack value
  6.     virtual bool pop(e& item) = 0;

  7.     //Function to Display the stack
  8.     virtual void print() const= 0;
  9. };

Stack Implementation:
  • Creating the Node:
  1. public:
  2. template<typename e>class Node
  3. {
  4. public:
  5.     e element;
  6.     Link<e>* next;

  7.     Link(e elemValue = 0, Link<e>* nextValue = nullptr)
  8.     {
  9.         element = elemValue;
  10.         next = nextValue;
  11.     }
  12.     Link(Link<e>* nextValue = nullptr)
  13.     {
  14.         next = nextValue;
  15.     }
  16. };

NOTE: It's pretty clear after looking at the code that we will be using singly linked node. Can you
              guess why Singly Linked and not Doubly Linked node?
  • Pointer-Based Implementation:
  1. #include"Stack.h"
  2. #include"Link.h"
  3. #include <iostream>

  4. template <typename E>class LStack:public Stack<E>
  5. {
  6.     Link<E>* top;
  7.     int Size;
  8. public:

  9.     LStack()
  10.     {
  11.         top = nullptr;
  12.         Size = 0;

  13.     }
  14.     ~LStack()
  15.     {
  16.         delete top;
  17.     }

  18.     int getSize() const  {return Size;}

  19.     bool Push(const E&);
  20.     bool Pop(E&);
  21.     void Print() const;
  22. };

  23. template<typename E>
  24. bool LStack<E>:: Push(const E& item)
  25. {
  26.     top = new Link<E>(item,top);
  27.     Size++;
  28.     return true;
  29. }

  30. template<typename E>
  31. bool LStack<E>:: Pop(E& item)
  32. {
  33.     if(Size == 0) return false;
  34.     item = top->element;
  35.     Link<E>* temp = top->next;
  36.     delete top;
  37.     top = temp;
  38.     Size--;
  39.     return true;
  40. }

  41. template<typename E>
  42. void LStack<E>:: Print() const
  43. {
  44.     Link<E>* temp = top;
  45.     std::cout<<"< ";
  46.     while(temp != nullptr)
  47.     {
  48.         std::cout<<temp->element<<" ";
  49.         temp=temp->next;
  50.     }
  51.     std::cout<<">";
  52. }
  • Testing the Implementation:
  1. #include "LStack.h"
  2. int main()
  3. {
  4.     LStack<int> newStack;
  5.     newStack.Push(32);
  6.     newStack.Push(25);
  7.     newStack.Push(67);
  8.     newStack.Push(34);
  9.     newStack.Push(56);
  10.     newStack.Push(76);
  11.     newStack.Push(32);
  12.     newStack.Push(398);
  13.     newStack.Push(36);
  14.     std::cout<<"Original Stack  : ";
  15.     newStack.Print();

  16.     int tempSize = newStack.getSize();
  17.     int tempPoppedValue = 0;
  18.     while(tempSize != 0)
  19.     {
  20.         newStack.Pop(tempPoppedValue);
  21.         std::cout<<"\nAfter removing "<<tempPoppedValue<<" :";
  22.         newStack.Print();
  23.         tempSize--;
  24.     }
  25. }

( If you like the content here, follow TSP on social media to get notified on future updates)


Comments

Share on Social Media

Most Viewed Posts

DS & A (Lists - Array Based)

SPACE & DRAGONS

DATA STRUCTURES AND ALGORITHMS