02.11.2017 16:46
SherlockD 24 3500 Источник

Привет, я студент второго курса технического университета. После пропуска нескольких пар программирования по состоянию здоровья, я столкнулся с непониманием таких тем, как «Стек» и «Очередь». Путем проб и ошибок, спустя несколько дней, до меня наконец дошло, что это такое и с чем это едят. Чтобы у вас понимание не заняло столько времени, в данной статье я расскажу о том что такое «Стек», каким образом и на каких примерах я понял что это такое. Если вам понравится, я напишу вторую часть, которая будет затрагивать уже такое понятие, как «Очередь»


Теория


На Википедии определение стека звучит так:

Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

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

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


На самом деле стек можно представить в виде стопки любых предметов будь то стопка листов, тетрадей, рубашек и тому подобное, но пример с книгами я думаю будет самым оптимальным.

Итак, из чего же состоит стек.

Стек состоит из ячеек(в примере — это книги), которые представлены в виде структуры, содержащей какие-либо данные и указатель типа данной структуры на следующий элемент.
Сложно? Не беда, давайте разбираться.





На данной картинке схематично изображен стек. Блок вида «Данные/*next» и есть наша ячейка. *next, как мы видим, указывает на следующий элемент, другими словами указатель *next хранит адрес следующей ячейки. Указатель *TOP указывает на вершину стек, то есть хранит её адрес.


С теорией закончили, перейдем к практике.


Практика


Для начала нам нужно создать структуру, которая будет являться нашей «ячейкой»


Код на C++
struct comp { //Структура с названием comp(от слова component)
	int Data; //Какие-то данные(могут быть любыми, к примеру можно написать int key; char Data; так-же можно добавить еще какие-либо данные)
	comp *next;//Указатель типа comp на следующий элемент
};

Новичкам возможно будет не понятно, зачем наш указатель — типа comp, точнее сказать указатель типа структуры comp. Объясню, для того чтобы указатель *next мог хранить структуру comp, ей нужно обозначить тип этой структуры. Другими словами указать, что будет хранить указатель.


После того как у нас задана «Ячейка», перейдем к созданию функций.


Функции


Функция создания «Стека»/добавления элемента в «Стек»


При добавлении элемента у нас возникнет две ситуации:

  • Стек пуст, и нужно создать его
  • Стек уже есть и нужно лишь добавить в него новый элемент

Функцию я назову s_push, перейдем к коду.

Код на C++
void s_push(comp **top, int D) { //функция типа void(ничего не возвращает) которая принимает указатль на вершину стека и переменную которая будет записываться в ячейку
	comp *q; //Создаем новый указатель q типа структуры comp. По сути это и есть наш новый элемент
	q = new comp(); //выделяем память для нового элемента
	q->Data = D; //Записываем необходимое число  в Data элемента
	if (top == NULL) { //Если вершины нет, то есть стек пустой
		*top = q; //вершиной стека будет новый элемент
	}
	else //если стек не пустой
	{
		q->next = *top; //Проводим связь от нового элемента, к вершине. Тоесть кладем книжку на вершину стопки.
		*top = q; //Обозначаем, что вершиной теперь является новый элемент
	}
}

Разберем чуть чуть по-подробнее.
Во-первых, почему функция принимает **top, то есть указатель на указатель, для того чтобы вам было наиболее понятно, я оставлю рассмотрение этого вопроса на потом. Во-вторых, по-подробнее поговорим о q->next = *top и о том, что же означает ->.


-> означает то, что грубо говоря, мы заходим в нашу структуру и достаем оттуда элемент этой структуры. В строчке q->next = *top мы из нашей ячейки достаем указатель на следующий элемент *next и заменяем его на указатель, который указывает на вершину стека *top. Другими словами мы проводим связь, от нового элемента к вершине стека. Тут ничего сложного, все как с книгами. Новую книгу мы кладем ровно на вершину стопки, то есть проводим связь от новой книги к вершине стопки книг. После этого новая книга автоматически становится вершиной, так как стек не стопка книг, нам нужно указать, что новый элемент — вершина, для этого пишется: *top = q;.


Функция удаления элемента из «Стека» по данным


Данная функция будет удалять элемент из стека, если число Data ячейки(q->Data) будет равна числу, которое мы сами обозначим.


Здесь могут быть такие варианты:

  • Ячейка, которую нам нужно удалить является вершиной стека
  • Ячейка, которую нам нужно удалить находится в конце, либо между двумя ячейками

Код на C++
void s_delete_key(comp **top, int N) {//функция которая принимает вершину top и число которое нужно удалить
	comp *q = *top; //создаем указатель типа comp и приравниваем(ставим) его на вершину стека
	comp *prev = NULL;//создаем указатель на предыдуший элемент, с начала он будет пустым
	while (q != NULL) {//пока указатель q не пустой, мы будем выполнять код в цикле, если он все же пустой цикл заканчивается
		if (q->Data == N) {//если Data элемента равна числу, которое нам нужно удалить
			if (q == *top) {//если такой указатель равен вершине, то есть элемент, который нам нужно удалить - вершина
				*top = q->next;//передвигаем вершину на следующий элемент
				free(q);//очищаем ячейку
				q->Data = NULL; //Далее во избежание ошибок мы обнуляем переменные в удаленной ячейке, так как в некоторых компиляторах удаленная ячейка имеет переменные не NULL значения, а дословно "Чтение памяти невозможно" или числа  "-2738568384" или другие, в зависимости от компилятора.
				q->next = NULL;
			}
			else//если элемент последний или находится между двумя другими элементами
			{
				prev->next = q->next;//Проводим связь от предыдущего элемента к следующему
				free(q);//очищаем ячейку 
				q->Data = NULL;//обнуляем переменные
				q->next = NULL;
			}
		}// если Data элемента НЕ равна числу, которое нам нужно удалить
		prev = q; //запоминаем текущую ячейку как предыдущую
		q = q->next;//перемещаем указатель q на следующий элемент
	}
}

Указатель q в данном случае играет такую же роль, что и указатель в блокноте, он бегает по всему стеку, пока не станет равным NULL(while(q != NULL)), другими словами, пока стек не закончится.

Для лучшего понимания удаления элемента проведем аналогии с уже привычной стопкой книг. Если нам нужно убрать книгу сверху, мы её убираем, а книга под ней становится верхней. Тут то же самое, только в начале мы должны определить, что следующий элемент станет вершиной *top = q->next; и только потом удалить элемент free(q);


Если книга, которую нужно убрать находится между двумя книгами или между книгой и столом, предыдущая книга ляжет на следующую или на стол. Как мы уже поняли, книга у нас-это ячейка, а стол получается это NULL, то есть следующего элемента нет. Получается так же как с книгами, мы обозначаем, что предыдущая ячейка будет связана с последующей prev->next = q->next;, стоит отметить что prev->next может равняться как ячейке, так и нулю, в случае если q->next = NULL, то есть ячейки нет(книга ляжет на стол), после этого мы очищаем ячейку free(q).

Так же стоит отметить, что если не провести данную связь, участок ячеек, который лежит после удаленной ячейки станет недоступным, так как потеряется та самая связь, которая соединяет одну ячейку с другой и данный участок просто затеряется в памяти


Функция вывода данных стека на экран


Самая простая функция:


Код на C++
void s_print(comp *top) { //принимает указатель на вершину стека		
	comp *q = top; //устанавливаем q на вершину
	while (q) { //пока q не пустой (while(q) эквивалентно while(q != NULL))
		printf_s("%i", q->Data);//выводим на экран данные ячейки стека
		q = q->next;//после того как вывели передвигаем q на следующий элемент(ячейку)
	}
}

Здесь я думаю все понятно, хочу сказать лишь то, что q нужно воспринимать как бегунок, он бегает по всем ячейкам от вершины, куда мы его установили вначале: *q = top;, до последнего элемента.


Главная функция


Хорошо, основные функции по работе со стеком мы записали, вызываем.
Посмотрим код:

Код на C++
void main() {
	comp *top = NULL; //в начале программы у нас нет очереди, соответственно вершины нет, даем ей значение NULL
	//Дальше начинаем добавлять цифры от 1 до 5 в наш стек
		s_push(&top, 1);
		s_push(&top, 2);
		s_push(&top, 3);
		s_push(&top, 4);
		s_push(&top, 5);
	//после выполнения функций в стеке у нас будет 54321
	s_print(top);//выводим
	s_delete_key(&top, 4); //Затем удаляем 4, в стеке получается 5321
	printf_s("\n");//переводим на новую строку
	s_print(top);//выводим
	system("pause");//ставим на паузу
}

Вернемся к тому, почему же в функцию мы передавали указатель на указатель вершины. Дело в том, что если бы мы ввели в функцию только указатель на вершину, то «Стек» создавался и изменялся только внутри функции, в главной функции вершина бы как была, так и оставалась NULL. Передавая указатель на указатель мы изменяем вершину *top в главной функции. Получается если функция изменяет стек, нужно передавать в нее вершину указателем на указатель, так у нас было в функции s_push,s_delete_key. В функции s_print «Стек» не должен изменяться, поэтому мы передаем просто указатель на вершину.
Вместо цифр 1,2,3,4,5 можно так-же использовать переменные типа int.


Заключение


Полный код программы:


Код на C++
#include <stdio.h>;
#include <iostream>;

struct comp { //Структура с именем comp
	int Data; //Кикие то данные(могут быть любими, к примеру можно написать int key; char Data; или добавить еще какие то данные)
	comp *next;//Указатель типа comp на следующий эелемент
};

void s_push(comp **top, int D) { //функция типа void(ничего не возвращает) которая принимает указатль на вершину стека и переменную которая будет записываться в ячейку
	comp *q; //Создаем новый указатель q, который приравниваем к вершине стека. По сути это и есть наш новый элемент
	q = new comp(); //выделяем память для нового элемента
	q->Data = D; //Записываем D в Data элемента
	if (top == NULL) { //Если вершины нет, тоесть стек пустой
		*top = q; //вершиной стека будет новый элемент
	}
	else //если стек не пустой
	{
		q->next = *top; //Проводим связь от нового элемента, к вершине. Тоесть кладем книжку на вершину стопки.
		*top = q; //Пишем, что вершиной теперь является новый элемент
	}
}

void s_delete_key(comp **top, int N) {//функция которая принимает вершину top и число которое нужно удалить
	comp *q = *top; //создаем указатель типа comp и приравниваем(ставим) его на вершину стека
	comp *prev = NULL;//создаем указатель на предыдуший элемент, с начала он будет пустым
	while (q != NULL) {//пока указатель q не путой, мы его будем проверять, если он все же пусть цикл заканчивается
		if (q->Data == N) {//если Data элемента равна числу, которое нам нужно удалить
			if (q == *top) {//если такой указатель равен вершине, то есть элемент, который нам нужно удалить - вершина
				*top = q->next;//передвигаем вершину на следующий элемент
				free(q);//очищаем ячейку
				q->Data = NULL; //Далее во избежание ошибок мы обнуляем переменные в удаленной ячейке, так как в некоторых компиляторах удаленная ячейка имеет переменные не NULL значения, а дословно "Чение памяти невозможно" или числа  "-2738568384" или других, в зависимости от компилятора.
				q->next = NULL;
			}
			else//если элемент последний или находится между двумя другими элементами
			{
				prev->next = q->next;//Проводим связь от предыдущего элемента к следующему
				free(q);//очищаем ячейку 
				q->Data = NULL;//обнуляем переменные
				q->next = NULL;
			}
		}// если Data элемента НЕ равна числу, которое нам нужно удалить
		prev = q; //запоминаем текущую ячейку как предыдущую
		q = q->next;//перемещаем указатель q на следующий элемент
	}
}

void s_print(comp *top) { //принимает указатель на вершину стека		
	comp *q = top; //устанавливаем q на вершину
	while (q) { //пока q не пустой (while(q) эквивалентно while(q != NULL))
		printf_s("%i", q->Data);//выводим на экран данные ячейки стека
		q = q->next;//после того как вывели передвигаем q на следующий элемент(ячейку)
	}
}

void main() {
	comp *top = NULL; //в начале программы у нас нет очереди, соответственно вершины нет, даем ей значение NULL
	//Дальше начинаем добавлять цифры от 1 до 5 в наш стек
		s_push(&top, 1);
		s_push(&top, 2);
		s_push(&top, 3);
		s_push(&top, 4);
		s_push(&top, 5);
	//после выполнения функций в стеке у нас будет 54321
	s_print(top);//выводим
	s_delete_key(&top, 4); //Затем удаляем 4, в стеке получается 5321
	printf_s("\n");//переводим на новую строку
	s_print(top);//выводим
	system("pause");//ставим на паузу
}

Результат выполнения


54321
5321

Так как в стек элементы постоянно добавляются на вершину, выводиться элементы будут в обратном порядке



В заключение хотелось бы поблагодарить за уделенное моей статье время, я очень надеюсь что данный материал помог некоторым начинающим программистам понять, что такое «Стек», как им пользоваться и в дальнейшем у них больше не возникнет проблем. Пишите в комментариях свое мнение, а так же о том, как мне улучшить свои статьи в будущем. Спасибо за внимание.

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


  1. x893
    02.11.2017 19:53
    #10503860

    Кто в армии не служил сложно понять, что такое стек и очередь.
    Из стека легко очередь сделать.


    1. Sdima1357
      02.11.2017 20:26
      #10503900

      Ваше объяснение уже ближе:
      стек — это патроны в магазине автомата. Последний вставленный выходит первым.


      1. x893
        02.11.2017 20:43
        #10503914
        +1

        И дальше они двигаются в очереди.
        Первая вылетела — первая прилетела.
        А еще есть куча — это мины.
        В общем LIFO/FIFO


  1. alexyr
    02.11.2017 20:02
    #10503866
    +1

    We need to go deeper: нужно объяснение что такое linked list


    1. Sdima1357
      02.11.2017 20:18
      #10503890

      Тут вообще много пропущено. Что такое функции new и delete и как они работают. Объяснять простые понятия основываясь на более сложных наверное не самый оптимальный подход.


      1. SherlockD Автор
        02.11.2017 22:11
        #10504022

        Спасибо за отзыв! В будущем буду внимательнее


  1. aamonster
    02.11.2017 20:14
    #10503886

    Мило, что вы пишете что-то "от чайника к чайнику", но вы немного запутались. Обратите внимание: стек из вашего первого примера (стопка книг) не лезет в рамки последующего объяснения (связный список).


    Стек — штука абстрактная, не раскрывающая детали реализации (только требования к операциям push и pop). И реализация поверх массива на практике встречается чаще, чем поверх связного списка.


    1. SherlockD Автор
      02.11.2017 22:46
      #10504066

      Спасибо за отзыв! Обязательно учту!


  1. Videoman
    02.11.2017 20:54
    #10503930
    +1

    Эх, зря вы все-таки пропустили лекции по структурам данных и, видимо, С++)
    Для новичков, кто действительно хочет чему-то научиться: ни в коем случае не реализуйте стеки таким образом, как это продемонстрировал автор. Это один из наихудших вариантов, как с точки зрения понимания, так и с точки зрения эффективности. А на С++, вообще, больно смотреть, максимум тянет на С. Для начала:

    std::vector<int> stack;

// Положить
stack.push_pack(5); 

// Забрать
const int value = stack.back();
stack.pop_back();

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


    1. SherlockD Автор
      02.11.2017 22:27
      #10504046

      На тех парах, что я пропустил как раз разбирали реализацию стека именно таким способом :) Моей задачей было объяснение именно этого способа реализации стека. А за отзыв спасибо большое, действительно, думаю стоит в начале привести пример работы стандартных функций, а потом переходить к классике! В будущем учту.


    1. Free_ze
      02.11.2017 23:12
      #10504098

      std::stack же


    1. ustaspolansky
      02.11.2017 23:39
      #10504124

      На провах новичка.
      Тестировал свой стек используя "STL с Vector" vs «C style с Char и memcpy».

      Результат:
      Vector медленнее от 11 до 13 раз при комплексном тесте.

      П.С.
      Мне это нужно для парсера Autodesk FBX в свой внутренний формат MDL (Много работы с сотнями пакетов наборов вершин по 1-100 метров).


      1. poxvuibr
        03.11.2017 07:25
        #10504292

        Vector медленнее от 11 до 13 раз при комплексном тесте.

        Код в студию :)


        1. ustaspolansky
          03.11.2017 19:56
          #10505378

          Код теста pastebin.com/FKWQLBkE (url не отобр. вставил так. Пр. прощения, возм затуп мой.)

          — Это не чистый стэк! Точнее не стэк. Тест накидал для сравнения (Проект в котором использовал именно стэк сейчас недоступен).
          — И там и там происходит резервирование места перед заполнением и изменением.
          — Вызовы у обоих способов одинаковые, отличия в реализации.

          По сути происходит заполнение, потом последовательное считывание и изменение ячейки.

          П.С. Если возможно аргументированно. Можно минусовать, отношусь к этому спокойно.


          1. poxvuibr
            03.11.2017 23:19
            #10505550

            По поводу производительности. Из вектора элемент выбирается с помощью at. at проверяет, есть ли в векторе такой индекс и, если его нет — бросает исключение. Было бы неплохо попробовать выбирать значения из вектора простым [ ]. И писать тоже. [ ] проверок не делает и, соответственно, работает немного быстрее. Плюс, возможно, проверка внутри push_back, не надо ли увеличить внутренний массив, даёт свой вклад.


            По поводу CharStack. У вас там хранится int и только int, соответственно, чего бы не сделать просто массив интов? memcpy тогда не нужен, можно просто писать значения в массив по индексу.


            Плюс традиционный вопрос. Какой компилятор использовали и с какими флагами оптимизации :)?


            1. ustaspolansky
              04.11.2017 13:03
              #10505808

              Спасибо, что потратили время на мой индусский код и дали ответ :).
              Да, про «at» и «push_back» интересно, буду копать дальше.

              Собственно и проект свой потёр по причине «А не начать ли всё заново. Книжки перечитать с самого начала».
              Конечно в начале пути иногда после теста говорю — «ИИиху! Вот оно». Но потом понимаю, что не всё так очевидно. Возможно это тот самый случай.

              Спасибо!


          1. Videoman
            05.11.2017 01:08
            #10506436

            В вашем коде последний аргумент (size) при всех вызовах memcpy равен offset = sizeof(int); При включенной оптимизации компилятор преобразует это выражение в константу времени компиляции, а следовательно, memcpy выродится в intrinsinc — простое копирование значения без вызова функции.
            В итоге, вы сравниваете методы std::vector: at() и push_back() в которых присутствует проверка граничных условий и выброс исключений, в случае неудачи (такие методы, как правило, не могут быть заинлайнены), и просто копирование значения по указателю, даже, без проверки выхода за границы.
            Простое копирование значения по адресу и приращение указателя действительно может быть на порядок медленнее честного вызова функции с обработкой исключений. Но сравнение не корректно, на мой взгляд.


  1. ziv
    02.11.2017 23:07
    #10504092

        free(q);//очищаем ячейку 
    q->Data = NULL;//обнуляем переменные
    q->next = NULL;


    Так делать нельзя, это доступ к освобождённой памяти — undefined behavior.
    www.securecoding.cert.org/confluence/display/cplusplus/MEM50-CPP.+Do+not+access+freed+memory


  1. myxo
    03.11.2017 01:06
    #10504168

    По опыту, если у ученика проблемы с пониманием стека, то у ученика проблемы с пониманием того, что такое структуры данных и зачем они нужны. Ну то есть если абстрактно начать ни с того ни с сего рассказывать про стек, то единственным вопросом будет «эээ, ну ок, и че дальше?».

    Нужно для начала показать зачем нужны разные структуры данных, как с помощью них можно опускать большие куски размышлений.Что это не то как мы организуем память, а то как мы работаем с нашими данными.


    1. SherlockD Автор
      03.11.2017 01:36
      #10504178

      Благодарю за отзыв, в будущем буду начинать с основ.


  1. michael_vostrikov
    03.11.2017 12:02
    #10504578

    Стоит добавить, что тот стек, который работает в исполняемых файлах, устроен немного не так. Есть просто указатель вершины (хранится в регистре ESP/RSP), а данные располагаются в памяти друг за другом. Стек находится в конце региона памяти и растет в обратную сторону. При добавлении данных указатель уменьшается на их размер.


    1. Videoman
      03.11.2017 13:39
      #10504756

      И тогда «ближайшая» к аппаратному стеку реализация на С будет тривиальной:

      int* stack = ...; // Указатель на голову стека
// Положить
*--stack = 100;
// Снять
const int value = *stack++;
// Проверить
assert(value == 100);


  1. Free_ze
    03.11.2017 13:10
    #10504708

    Что-то какой-то связный список получился, а не стек. На рисунке книжки у вас физически лежат стопкой, а в сишном варианте — беспорядочно, связанные через указатели.


  1. Serge78rus
    03.11.2017 15:38
    #10504998

    1. Вы называете «код на C++» код, написанный на C. То, что Вы один раз использовали оператор new, делает этот код не компилируемым в C, но отнюдь не кодом на C++
    2. Использование для выделения памяти оператора new в паре с функцией освобождения памяти free() — очень плохая практика. Либо new/delete, либо malloc()/free(), но не смесь их.
    3. Фрагмент
      	free(q);//очищаем ячейку
	q->Data = NULL; //Далее во избежание ошибок мы обнуляем п
      вообще не выдерживает никакой критики: Вы освободили память, занимаемую объектом, больше она Вам не принадлежит и Вы не имеете права к ней обращаться. То же самое в этом же фрагменте чуть ниже.
    4. Поле comp::Data у Вас типа int, а Вы присваиваете ему NULL — нулевой указатель. Кстати, если уж Вы говорите о C++, то используйте nullptr, а не C-шный NULL (естественно, не для int, а для указателей)