ScaleFree

DS & A(Stacks - Array Based)

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.     //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:
  • Array-Based Implementation:
  1. #include <iostream.h>
  2. #include "name_of_the_StackADT_file.h"

  3. template<typename e>
  4. class AStack: public Stack<e>
  5. {
  6.     int max_size;
  7.     int top_index;
  8.     e *stack_array;
  9. public:
  10.     AStack(int temp_max_size = 0):
  11.     max_size(temp_max_size),stack_array(new e[max_size]),top_index(0)
  12.     {
  13.         //Initialization done with member Initializer List
  14.     }
  15.     bool push(const e& push) override;
  16.     bool pop(e& pop) override;
  17.     void print() const override;
  18. };

  19. template<typename e>
  20. bool AStack<e>::push(const e& item)
  21. {
  22.     if(top_index == max_size) return false;//when stack is full
  23.     stack_array[top_index++] = item;
  24.     return true;//on succesful push operation
  25. }

  26. template<typename e>
  27. bool AStack<e>::pop(e& item)
  28. {
  29.     if(top_index == 0) return false;//when stack is empty
  30.     item = stack_array[--top_index];
  31.     return true;//on successful pop poperation
  32. }

  33. template<typename e>
  34. void AStack<e>::print() const
  35. {
  36.    std::cout<<"< ";
  37.    int counter = top_index;
  38.    while(counter != 0)
  39.    std::cout<< stack_array[--counter]<<" ";
  40.    std::cout<<">";
  41. }
  • Testing the Implementation:
  1. int main()
  2. {
  3.    AStack <int>newStack(10);

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

( 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