Stack

Stack is a simple data structure serves collection of elements with 2 main operations (push and pop). The order of each element is added or removed from a stack is referred by LIFO (Last In First Out).

Array Stack

template <typename E>
class ArrayStack
{
  enum
  {
    DEF_CAPACITY = 100
  };

public:
  ArrayStack(int cap = DEF_CAPACITY)
  {
    capacity = cap;
    it = -1;
    arr = new E[capacity];
  }
  int size() const
  {
    return it + 1;
  }
  bool empty() const
  {
    return size() == 0;
  }
  const E &top() const
  {
    if (empty())
      throw runtime_error("Top of empty stack!");
    return arr[it];
  }
  void push(const E &e)
  {
    if (size() == capacity)
      throw runtime_error("Push to full stack");
    arr[++it] = e;
  }
  void pop()
  {
    if (empty())
      throw runtime_error("Pop from empty stack");
    it--;
  }

private:
  E *arr;
  int capacity; // stack capacity
  int it;       // index of the top of the stack
};

Linked List Stack

We’ll use SLinkedList from Linked List.

template <typename E>
class LinkedStack
{
public:
  LinkedStack() : n(0), S() {}
  int size() const
  {
    return n;
  }
  bool empty() const
  {
    return n == 0;
  }
  const E &top()
  {
    if (empty())
      throw(runtime_error("Top of empty stack"));
    return S.front();
  }
  void push(const E &e)
  {
    S.addFront(e);
    n++;
  }
  void pop()
  {
    if (empty())
      throw(runtime_error("Pop from empty stack"));
    S.removeFront();
    n--;
  }

private:
  SLinkedList<E> S;
  int n; // number of elements
};