Структуры данных для самых маленьких: Стек

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

В данной статье я хотел бы рассказать о такой структуре данных как стек. Стек представляет собой одну из базовых структур данных и работает по системе LIFO (Last In First Out). Представить стек можно в виде стакана или стопки книг. Таким образом книга, положенная последней, будет взята первой и наоборот, первая положенная книга будет взята в самом конце.

Основные операции, выполняемые над стеком это вставка (Push) и удаление (Pop). Помимо этого я реализую не менее известные операции:

Показ верхнего элемента (Peek), проверку на пустоту (isEmpty), проверку на заполненность (isFull). Достаточно часто стек реализуется на базе массива, но может быть реализован и на базе других структур данных. Все примеры, приводимые в данной статье, будут написаны на C++

С чего хотелось бы начать? Давайте для начала создадим класс Stack и создадим конструктор, который будет инициализировать размер нашего массива

template <typename T>
class Stack
{
private:
    T * m_stack;
    size_t m_stackSize;
    int m_top;

public:
    Stack(size_t stackSize)
    {
        m_stack = new T[stackSize];
        this->m_stackSize = stackSize;
        m_top = -1;
    }

    ~Stack() {}
}

Итак, наш стек создан, что уже неплохо. Теперь нам нужно научиться осуществлять операции Push() и Pop().

Для начала реализуем Push(). Суть данного метода заключается в том, чтобы положить элемент в стек и увеличить значение top. В случае, если стек заполнен, выдаем сообщение о переполнении стека

void Push(T key)
{
	if (this->isFull())
        {
		cout << "Stack OverFlow" << endl;
	}
        else 
        {
		m_stack[++m_top] = key;
	}
}

Хорошо, со вставкой разобрались, пришла пора удаления. Удаление осуществляется тоже достаточно просто: мы просто достаем последний положенный элемент и уменьшаем наш top. В случае, если стек пуст, выдаем сообщение об ошибке.

T * Pop()
{
    if (this->isEmpty()) 
    {
        std::cout << "Stack is Empty" << std::endl;
        return nullptr;
    } 
    else 
    {
        return & m_stack[m_top--];
    }
}

Итак, вставлять научились, удалять научились. Пришло время операции Peek. Данная операция настолько проста, что в комментариях не нуждается: мы просто смотрим на верхний элемент (если он есть, конечно).

T * Peek()
{
	if (this->isEmpty()) 
        {
		std::cout << "Stack is Empty" << std::endl;
		return nullptr;
	} 
        else 
        {
		return & m_stack[m_top];
	}
}

Так же сразу предоставлю код isEmpty() и isFull()

bool isEmpty()
{
    return (m_top == -1) ? true : false;
}

bool isFull() 
{
	return (m_top == this->m_stackSize - 1) ? true : false;
}

Ну вот и все, наш стек реализован и мы можем спокойно выпить чашечку кофе. В последующих статьях я продолжу рассматривать структуры данных, такие как очереди, списки, кучи и деревья. Буду искренне рад критике жителей Хабрахабра, потому что критика заставляет работать над собой. Спасибо за внимание!

P.S. Исходники моей вариации стека ниже:

template <typename T>
class Stack
{
private:
    T * m_stack;
    size_t m_stackSize;
    int m_top;

public:
    Stack(size_t stackSize)
    {
        m_stack = new T[stackSize];
        this->m_stackSize = stackSize;
        m_top = -1;
    }

    ~Stack() {}

    void Push(T key)
    {
        if (top == this->stackSize - 1)
        {
            std::cout << "Stack Overflow" << std::endl;
        } 
        else 
        {
            m_stack[++m_top] = key;
        }
    }

    T * Pop()
    {
        if (this->isEmpty())
        {
            std::cout << "Stack is Empty" << std::endl;
            return nullptr;
        } 
        else 
        {
            return & m_stack[m_top--];
        }
    }

    T * Peek()
    {
		if(this->isEmpty())  
                {
			std::cout << "Stack is Empty" << std::endl;
			return nullptr;
		} 
                else 
                {
			return & m_stack[m_top];
		}
     }

    bool isEmpty()
    {
        return (m_top == -1) ? true : false;
    }

    bool isFull() 
    {
    	return (m_top == this->m_stackSize - 1) ? true : false;
    }
};

Автор: iDzyubin

Источник