Stack –An introduction

”Pile of things is a stack!!.. Why would such a pile used in computers? Early computers read memory in a stack form since memory operations are too costly those days. The stack based systems are a big failure when hardware bandwidth and cost reduced. Then too, register stack came which is faster to access. Even some system caches are maintained as stack and a raw machine code flow is maintained on a stack. So, stack became inevitable for low-end systems not for high end”

Metaphor

   Think about the old machines which reads punch cards and store the bits. These machines can only read one bit at once and write one at a time. They are very slow that, block read cannot be done. For a char(1-byte per cycle) based systems like this and if the data stored has a property of Last in first out (LIFO) then a stack is used to maintain the history.

   History gives a indirect meaning to a stack. The first entered element goes to the last!! So most valid use cases of a stack pile is to dump old data and get the latest one at the top!!

Concept

  Stack is a data structure. Not a data organization. We already discussed that all data structures have static and dynamic data organizations. Static is usually constructed using array and dynamic using linked list. Stack as we discussed till now, can be limited to size using array. It can be made unlimited until the full memory is exhausted using linked list.

    The major operations in a stack are:

     - INSERT – which is the PUSH operation. dump the element to the stack

     - DELETE – which is the POP operation, pick the latest element in the stack

Always, we should have the latest element at the TOP of the stack. On every PUSH, stack overflow possibility need to be checked using STACK-FULL. On every POP, stack underflow need to be checked using STACK-EMPTY.

Code

   1:  const int SIZE=10;

   2:   

   3:  template<class T>

   4:  class Stack

   5:  {

   6:      T arr[SIZE];

   7:      int top_idx;

   8:   

   9:      int top() const    {    return top_idx; }

  10:   

  11:      bool stack_empty() const {  return (top_idx == -1);     }

  12:   

  13:      bool stack_full() const { return (top_idx+1 > SIZE-1); }

  14:   

  15:  public:

  16:      Stack() {

  17:          top_idx = -1;

  18:      }

  19:   

  20:      bool push(T val)    {    

  21:          if(stack_full())

  22:              return false;

  23:          else {

  24:              arr[++top_idx] = val;

  25:              return true;

  26:          }

  27:      }

  28:   

  29:      bool pop(T& val) {

  30:          if(stack_empty())

  31:              return false;

  32:          else {

  33:              val = arr[top_idx];

  34:              top_idx -=1;

  35:              return true;

  36:          }

  37:      }

  38:  };

  39:   

  40:  void main()

  41:  {

  42:      Stack<int> sobj;

  43:      int pop_val;

  44:      for(int i = 0; i<12;i++)

  45:          sobj.push(i);

  46:   

  47:      for(int i = 0; i<12;i++)

  48:          sobj.pop(pop_val);

  49:  }

Problems while coding
- tried C++ template object for stack :). so lots of problems. Const-ness creation should be done carefully, there is something called logical and bitwise const. We will study about it later as it is related to C++ concepts.
- All the members in a class are by default private.. :D very basic problem
- You cannot initialize a member variable inside a class. It should be static or const to be initialized because, class is only a compile time structure!! Not runtime one
- incrementing the top and decrementing it.. confusing!!.. top should be -1 if array index is 0. if linked list is used, have top as zero and continue counting..
- stack full is determined when top+1 exceeds the size. for linked list case, size is up to memory full. So, just memory full check will do!!