Implementing Stack using Array

The core property of a Stack data structure is that it allows adding and removing elements only from one endpoint i.e, there is only one opening through which we can add or remove elements. To make it intuitive and easy to understand, we generally visualize stack as a pile of elements stacked on top of each other. Adding or removing elements will be done from the top end of pile.

Similar behavior can be achieved using an array by adding or removing elements after the last element present in the array. You can visualize this as a horizontal stack. Each time a new element has to be pushed to the stack, it can be added after the last element present in the array. Similarly when the top element has to be popped off the stack, the last element in the array can be returned.

In this way, each operation —push, pop, top and is_empty— can be achieved in constant time O(1).

Note: We can also replicate behavior of Stack by adding and removing elements from the beginning of array. But this is not efficient as all the elements after the top element have to be relocated every time a new element is added/removed from the beginning of stack.

Below is the code to implement stack using an array:

class StackUsingArray:
    def __init__(self, size):
        self.size = size
        # Initialize an array which can hold 'size' elements
        self.array = [None] * size
        # Initialize top index to -1 (Indicates empty stack)
        self.top_idx = -1

    def push(self, item):
        # Check if there's space in the array
        if self.top_idx < self.size - 1:
            # Increment the top element and add item
            self.top_idx += 1
            self.array[self.top_idx] = item
            return True
        else:
            print("Stack Overflow!")
            return False

    def pop(self):
        if not self.is_empty():
            item = self.array[self.top_idx]
            self.array[self.top_idx] = None  # Clearing the value
            self.top_idx -= 1
            return item
        else:
            print("Stack Underflow!")
            return None

    def top(self):
        if not self.is_empty():
            return self.array[self.top_idx]
        else:
            return None

    def is_empty(self):
        if self.top_idx == -1:
            return true;
        else:
            return false;

/******************************************************************************
C++ Implementation of Stack ADT using Vector/List
*******************************************************************************/

#include <iostream>
#include <vector>

// Using template with generic type T
// So that we can decide the type of elements stored
// when we use the stack
template <typename T> class Stack {
private:
  std::vector<T> array;
  int top_idx = -1;

public:
  Stack(size_t size) : array(size) {}

  void push(T element) {
    // Increment the current top position
    // and add the element at new top position
    top_idx = top_idx + 1;
    array[top_idx] = element;
  }
  
  T pop() {
    // Store the top element for returning and
    // Move the top pointer to the next element
    T result = array[top_idx];
    top_idx = top_idx - 1;
    return result;
  }
  
  T &top() const { return array[top_idx]; }
  
  bool is_empty() const { return top_idx < 0; }
};

// Let us now test the Stack ADT!
int main() {
  Stack<int> stk(5);
  stk.push(1);
  stk.push(2);
  stk.push(3);
  while (stk.is_empty() != true) {
    std::cout << stk.pop() << " ";
  }
  return 0;
}

Here is how the code works:

1. Constructor or __init__:
   • In this method, we initialize the stack by creating an empty array of desired size.
   • top_idx is set to -1 to indicate an empty stack.
2. push method:
   • The push method adds an item to the top of stack.
   • The last element in the array is considered as the top of stack.
   • So when pushing an item, we increment top_idx and add new element at the incremented index.
   • This makes sure that the new element is added after the last existing element in the array.
   • It also checks if there’s space available (top_idx < self.size - 1) before pushing the new element.
3. pop method:
   • The pop method removes the top item from the stack.
   • The last element in the array is considered as the top of stack.
   • So the element at top_idx position is returned
   • top_idx is also decremented to indicate that the next last element will be the top element.
4. top method:
   • The top method retrieves the top item from the stack without removing it. It simply looks at the item at the top_idx position in the array (array[self.top_idx]) and returns that item.
5. is_empty method:
   • The is_empty method checks if the stack is empty by examining the value of top_idx.
   • If top_idx is -1, it means there are no items in the stack, indicating that the stack is empty.