DS & A(Stacks - Pointer Based)

| CHAPTER 13 |

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. 
   
6.     //Function to remove top-most Stack value
7.     virtual bool pop(e& item) = 0;
8. 
   
9.     //Function to Display the stack
10.     virtual void print() const= 0;
11. };

Stack Implementation:

• Creating the Node:

1. public:
2. template<typename e>class Node
3. {
4. public:
5.     e element;
6.     Link<e>* next;
7. 
   
8.     Link(e elemValue = 0, Link<e>* nextValue = nullptr)
9.     {
10.         element = elemValue;
11.         next = nextValue;
12.     }
13.     Link(Link<e>* nextValue = nullptr)
14.     {
15.         next = nextValue;
16.     }
17. };

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. 
   
5. template <typename E>class LStack:public Stack<E>
6. {
7.     Link<E>* top;
8.     int Size;
9. public:
10. 
    
11.     LStack()
12.     {
13.         top = nullptr;
14.         Size = 0;
15. 
    
16.     }
17.     ~LStack()
18.     {
19.         delete top;
20.     }
21. 
    
22.     int getSize() const  {return Size;}
23. 
    
24.     bool Push(const E&);
25.     bool Pop(E&);
26.     void Print() const;
27. };
28. 
    
29. template<typename E>
30. bool LStack<E>:: Push(const E& item)
31. {
32.     top = new Link<E>(item,top);
33.     Size++;
34.     return true;
35. }
36. 
    
37. template<typename E>
38. bool LStack<E>:: Pop(E& item)
39. {
40.     if(Size == 0) return false;
41.     item = top->element;
42.     Link<E>* temp = top->next;
43.     delete top;
44.     top = temp;
45.     Size--;
46.     return true;
47. }
48. 
    
49. template<typename E>
50. void LStack<E>:: Print() const
51. {
52.     Link<E>* temp = top;
53.     std::cout<<"< ";
54.     while(temp != nullptr)
55.     {
56.         std::cout<<temp->element<<" ";
57.         temp=temp->next;
58.     }
59.     std::cout<<">";
60. }

• 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. 
    
17.     int tempSize = newStack.getSize();
18.     int tempPoppedValue = 0;
19.     while(tempSize != 0)
20.     {
21.         newStack.Pop(tempPoppedValue);
22.         std::cout<<"\nAfter removing "<<tempPoppedValue<<" :";
23.         newStack.Print();
24.         tempSize--;
25.     }
26. }

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