Data structures: Stack

Стек - структура данных имеющая набор элементов и поддерживающая методы Затолкнуть и Извлечь. Элементы вносятся в набор и удаляются из него в следующие порядке: в первую очередь обрабатывается элемент поступивший последним  (т.е. LIFO).

Данный код демонстрирует две реализации стека: на базе массива и на базе связного списка.

#ifndef STACK
#define STACK 

// based on linked list 

template<typename ItemType>

struct stack
{
    linked_list<ItemType> *stack_list; 
    linked_list<ItemType> *last; 
        
    void push(ItemType new_item)
    {
        if (stack_list==NULL)
        {
            stack_list=new linked_list<ItemType>(new_item); 
        }
        else
        {
            last=new linked_list<ItemType>(new_item); 
            last->Next=stack_list; 
            stack_list=last; 
        };
    };

    ItemType pop()
    {
        ItemType res=stack_list->Item; 
        
        stack_list=stack_list->Next;

        return res; 
    };
}; 

// based on array 

template<typename ItemType>

struct stack_arr
{
    ItemType *st_arr; 
    int CURRENT_SIZE;  
    int STACK_SIZE; 

    stack_arr(int s_size)
    {
        st_arr=new ItemType[s_size]; 
        CURRENT_SIZE=0; 
        STACK_SIZE=s_size; 
    };

    void push(ItemType new_item)
    {
        
        if ((CURRENT_SIZE-1)==STACK_SIZE)
        {
            std::cout << "Stack is full" << std::endl; 
        }
        else
        {
            st_arr[CURRENT_SIZE]=new_item; 
            CURRENT_SIZE++; 
        };
    };

    ItemType pop()
    {
        ItemType res=st_arr[CURRENT_SIZE-1]; 
        CURRENT_SIZE--; 

        return res; 
    }; 
};

#endif