DS & A(Stacks - Array Based)

| CHAPTER 12 |

So, we are finally done with List DS for now. And if you made it this far hats off to your determination. Let's start this new chapter with the very same determination. In today's chapter, you will be learning about a new DS called Stack. Now you might be familiar with the word Stack but let us see what it means in the world of DS & A.

Stacks:

• Stacks are restricted version of Lists with the following restrictions:
• Data can only be inserted from the top. Data insertion is referred to as PUSH.
• Data can only be deleted from the top as well. Data Deletion is referred to as POP.
• Alternatively, PUSH and POP should always be executed on the same side of the Stack.
• A Stack follows the LIFO principle also known as FILO.

• The accessible element can be referred to as TOP.

Visual Representation:

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:

• Array-Based Implementation:

1. #include <iostream.h>
2. #include "name_of_the_StackADT_file.h"
3. 
   
4. template<typename e>
5. class AStack: public Stack<e>
6. {
7.     int max_size;
8.     int top_index;
9.     e *stack_array;
10. public:
11.     AStack(int temp_max_size = 0):
12.     max_size(temp_max_size),stack_array(new e[max_size]),top_index(0)
13.     {
14.         //Initialization done with member Initializer List
15.     }
16.     bool push(const e& push) override;
17.     bool pop(e& pop) override;
18.     void print() const override;
19. };
20. 
    
21. template<typename e>
22. bool AStack<e>::push(const e& item)
23. {
24.     if(top_index == max_size) return false;//when stack is full
25.     stack_array[top_index++] = item;
26.     return true;//on succesful push operation
27. }
28. 
    
29. template<typename e>
30. bool AStack<e>::pop(e& item)
31. {
32.     if(top_index == 0) return false;//when stack is empty
33.     item = stack_array[--top_index];
34.     return true;//on successful pop poperation
35. }
36. 
    
37. template<typename e>
38. void AStack<e>::print() const
39. {
40.    std::cout<<"< ";
41.    int counter = top_index;
42.    while(counter != 0)
43.    std::cout<< stack_array[--counter]<<" ";
44.    std::cout<<">";
45. }

• Testing the Implementation:

1. int main()
2. {
3.    AStack <int>newStack(10);
4. 
   
5.    newStack.push(12);
6.    newStack.push(15);
7.    newStack.push(22);
8.    newStack.push(32);
9.    newStack.push(14);
10.    newStack.push(45);
11.    newStack.push(67);
12.    newStack.push(76);
13.    newStack.push(87);
14.    newStack.push(95);
15.    
16.    int poppedValue;
17.    std::cout<<"\nPush Order is: 12->15->22->32->14->45->67->76->87->95";
18.    std::cout<<"\nPop Order is : ";
19.    for (int i = 0; i<10 ; i++)
20.        {
21.            newStack.pop(poppedValue);
22.            std::cout<<poppedValue<<((i<9)?"->":"");
23.        }
24.    std::cout<<"\n";
25. }

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