Сегодня мы с Вами поговорим о списках в С++. А именно о списке типа Стек (от англ. Stack).

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

Стек выглядит примерно так:

Теперь, смотрим:

Итак, сделаем пример с видео. Запишем очень большое число в стек (например 9^100).

Начнем с того, что нам нужно создать нашу структуру:

struct number { int x; // Здесь будет 1 цифра number *adr; // Здесь адрес следующего элем. }

Создаем два указателя типа number.

number *top = NULL, *p;

Теперь припустим что мы это число считываем с файла по цифре. (file - указатель на файл.)

do { p = new number; // Создаем новый элемент списка p->adr = top; // Привязываем к предидущему элементу file>>p->x; // Считываем цифру с файла top = p; // Смещаем вершину стека } while(top->x); // Повторяем цикл пока есть еще что-то в файле

Мы научились вводить данные в наш стек. Как Вы можете видеть здесь нет никаких ограничений по размеру, как например есть в массиве.

Теперь попробуем вставить элемент посередине нашего стека.
Допустим наш список выглядит так: 1, 2, 3, 4, 5, 6, 7, 8, 9. Теперь между цифрой 7 и 8 мы вставим цифру 15.

p = top; // Чтобы не потерять вершину стека, будем использовать дополнительный указатель while(p->x != 7 || p->adr != NULL) { // Пока мы не дошли до цыфры 7, или если ее нет, то до конца списка p = p->adr; // Смещаемся вниз } number *new_el = new number; // Создаем новый элемент списка new_el->x = 15; // Сохраняем в него число 15 new_el->adr = p->adr; // Привязываем новый элемент с элементов с цифрой 8 p->adr = new_el; // Привязываем элемент с цифрой 7 к новому элементу

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

Теперь попробуем удалить элемент. Допустим список у нас как в предыдущем примере. И нам нужно удалить наше вставленное число 15.

while(p->x != 7 || p->adr != NULL) { // Пока мы не дошли до цыфры 7, или если ее нет, то до конца списка p = p->adr; // Смещаемся вниз } number *p2 = p->adr; // Сохраняем адрес элемента в новый указатель p->adr = p->adr->adr; // Привязываем адрес к следующему элементу после удаляемого delete p2; // Удаляем элемент

Теперь мы с Вами умеем создавать списки типа стек, и заполнять их элементами. А также добавлять в них элементы и удалять их них.

Если Вам это было полезно, тогда жмите "мне нравиться".

P.S. Маленькое ДЗ, для проверки Ваших знаний. Напишите мне в комментариях код вывода всех элементов из списка.