О стеке простыми словами — для студентов и просто начинающих

в 16:46, , рубрики: c++, стек

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

Теория

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

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

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

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

О стеке простыми словами — для студентов и просто начинающих - 1

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

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

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

О стеке простыми словами — для студентов и просто начинающих - 2

На данной картинке схематично изображен стек. Блок вида «Данные/*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

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

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

Автор: SherlockD

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js