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

В данной статье я хотел бы рассказать о такой структуре данных как стек. Стек представляет собой одну из базовых структур данных и работает по системе 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;
    }
};

Поделиться с друзьями
-->

Комментарии (11)


  1. DmitryKoterov
    10.09.2016 19:27
    #9799634
    +1

    > this->isFull()
    > this->m_stackSize

    PHP detected. :)


  1. lizarge
    10.09.2016 20:19
    #9799664
    +1

    Минутка для самых маленьких? Зачем это на хабре?


  1. lpre
    10.09.2016 20:21
    #9799670
    +4

    T * m_stack;
Stack(size_t stackSize)

{
        m_stack = new T[stackSize];
}

~Stack() {}


    А почему вы в конструкторе создаете m_stack, а в деструкторе не удаляете?
    И почему вообще создаете динамически?


  1. sophist
    10.09.2016 20:35
    #9799680
    +5

    > return (m_top == -1)? true: false;

    Логическое выражение — это такое же выражение, как и арифметическое, его можно не только использовать в условиях, но и присваивать, и возвращать из функций.

    Ваша строчка эквивалентна следующей:
    return m_top == -1;


  1. lukdiman
    10.09.2016 21:31
    #9799726
    -1

    А почему не расширяете размер массива когда вставляете элемент с индексом равным размеру массива?


  1. ukhegg
    10.09.2016 21:52
    #9799742
    +1

    Появились, конечно, некоторые замечания:

    1. Отсутствие проверки на 0 в конструкторе переданного параметра
    2. Передача неизменяемых параметров в методы(Push) в православном программированиии производится по const&
      void Push(T const& arg){...}
      .До кучи еще бы добавить методы с перемещением параметров
      void Push(T&& arg){...}
    3. Для Peek(...) логичнее и правильнее возвращать значение опять же по ссылке(T const& и T&)
      T const& Peek() const {...}
T& Peek(){...}

      Тогда им никто не сможет зарядить пистолет и выстрелить в ногу
      delete s.Peek();
    4. Методs isEmpty и isFull суть константные:
      bool isEmpty() const {...}
bool isFull() const {...}
    5. Как было сказано выше: а кто ответственен за удаление выделенной памяти?
    6. А как же копирующие, перемещающие конструкторы, операторы сравнения, присваивания?

    ИМХО, почитали бы что-нибудь серьезнее учебника по C++. Не говорю про исходники Stl или Boost, там много лишней отвлекающей кросскомпиляторной материи, отвлекающей внимание.


  1. dacentered
    10.09.2016 23:30
    #9799796

    Так как Pop забирает значение из стека безвозвратно, лучше бы было передавать сам объект или его копию, а не ссылку на него. Это бы повысило локальность данных.


  1. hose314
    10.09.2016 23:30
    #9799798
    +1

    Если уж для самый маленьких, то хорошо бы написать зачем и где нужен этот атд. Сейчас образовательная нагрузка -> 0.


  1. StriderAJR
    10.09.2016 23:30
    #9799802

    Комментарий удален, потому что больше не актуален.


  1. Onito
    11.09.2016 00:39
    #9799870
    +2

    Действительно? Не в
    Освободить память? Передавать в пул не по конст ссылке как замечено ниже? Это что вообще такое? Спрячьте в черновики быстрее мне стыдно за Хабр с такими постами


  1. kalobyte
    11.09.2016 07:22
    #9799994

    почему я не пошел в быдловуз?
    потому что там вот так же дают какие-то данные, а зачем они нужны и что с ними делать — непонятно

    про типы данных есть в любой книжке, лучше бы ты писал в формате:
    — вот есть тип данных ааа
    — его можно использовать там и тут
    — вот код такого-то приложения с гитхаба, вот в этом месте используется тип ааа
    — вот так это выглядит во время выполнения программы
    — благодаря ему мы имеем профит ххх

    — нельзя использовать тип ббб, потому что…
    — можно использовать типы ццц и ддд, потому что…