Stack

A stack is like a plate dispenser in a cafeteria, where the first inserted plate is always being on the top and used first. Last in first out (LIFO)

stack implementation with C++

  1. implement with vector
#include <iostream>
#include <vector>

template<class T>
class Stack
{
    private:
        std::vector<T> arr;
    public:
        Stack(){}
        ~Stack(){}
        void push(T element)
        {
            arr.push_back(element);
        }
        void pop(T element)
        {
            arr.pop_back();
        }
        T peek()
        {
            T ele = arr.back();
            return ele;
        }
        std::size_t size()
        {
            return arr.size();
        }
        bool empty()
        {
            return arr.size() == 0;
        }
};
  1. implement with array
#include <iostream>

template<class T>
class StackArr
{
    private:
        int default_sz = 2;
        T *arr = new T[default_sz];
        std::size_t sz = 0;
        void expand_arr(T *old)
        {
            T *newarr = new T[sz*2];
            for(int i = 0; i < sz; i++)
                newarr[i] = old[i];
            delete []old;
            old = newarr;
        }
    public:
        StackArr(){}
        ~StackArr(){}
        void push(T element)
        {
            if(sz == default_sz)
                expand_arr(arr);
            arr[++sz] = element;
        }
        void pop()
        {
            if(sz <= 0)
            {
                std::cout << "stack is empty!" << std::endl;
                return;
            }
            sz--;
        }
        T peek()
        {
            if(sz <= 0)
                throw std::runtime_error{"stack is empty!!"};
            return arr[sz];
        }
        std::size_t size()
        {
            return sz;
        }
        bool empty()
        {
            return sz==0;
        }
        
};

Queue

A queue is a line in a cafeteria, the first person in the line will get ordered first. First in first out (FIFO)