Алгоритмы и структуры данных для начинающих: стеки и очереди. Использование стека в программировании

Стек - это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO) . Это значит, что мы будем иметь доступ только к последнему добавленному элементу.

В отличие от списков, мы не можем получить доступ к произвольному элементу стека. Мы можем только добавлять или удалять элементы с помощью специальных методов. У стека нет также метода Contains , как у списков. Кроме того, у стека нет итератора. Для того, чтобы понимать, почему на стек накладываются такие ограничения, давайте посмотрим на то, как он работает и как используется.

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

Если мы положим, например, красную тарелку, затем синюю, а затем зеленую, то сначала надо будет снять зеленую, потом синюю, и, наконец, красную. Главное, что надо запомнить - тарелки всегда ставятся и на верх стопки. Когда кто-то берет тарелку, он также снимает ее сверху. Получается, что тарелки разбираются в порядке, обратном тому, в котором ставились.

Теперь, когда мы понимаем, как работает стек, введем несколько терминов. Операция добавления элемента на стек называется «push», удаления - «pop». Последний добавленный элемент называется верхушкой стека, или «top», и его можно посмотреть с помощью операции «peek». Давайте теперь посмотрим на заготовку класса, реализующего стек.

Класс Stack

Класс Stack определяет методы Push , Pop , Peek для доступа к элементам и поле Count . В реализации мы будем использовать LinkedList для хранения элементов.

Public class Stack { LinkedList _items = new LinkedList(); public void Push(T value) { throw new NotImplementedException(); } public T Pop() { throw new NotImplementedException(); } public T Peek() { throw new NotImplementedException(); } public int Count { get; } }

Метод Push

• Поведение: Добавляет элемент на вершину стека.
• Сложность: O(1).

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

Public void Push(T value) { _items.AddLast(value); }

Метод Pop

• Поведение: Удаляет элемент с вершины стека и возвращает его. Если стек пустой, кидает InvalidOperationException .
• Сложность: O(1).

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

Public T Pop() { if (_items.Count == 0) { throw new InvalidOperationException("The stack is empty"); } T result = _items.Tail.Value; _items.RemoveLast(); return result; }

Метод Peek

• Поведение: Возвращает верхний элемент стека, но не удаляет его. Если стек пустой, кидает InvalidOperationException .
• Сложность: O(1).

public T Peek() { if (_items.Count == 0) { throw new InvalidOperationException("The stack is empty"); } return _items.Tail.Value; }

Метод Count

• Поведение: Возвращает количество элементов в стеке.
• Сложность: O(1).

Зачем нам знать, сколько элементов находится в стеке, если мы все равно не имеем к ним доступа? С помощью этого поля мы можем проверить, есть ли элементы на стеке или он пуст. Это очень полезно, учитывая, что метод Pop кидает исключение.

Пример: калькулятор в обратной польской записи.

Классический пример использования стека - калькулятор в обратной польской, или постфиксной, записи. В ней оператор записывается после своих операндов. То есть, мы пишем:

<операнд> <операнд> <оператор>

вместо традиционного:

<операнд> <оператор> <операнд>

Другими словами, вместо «4 + 2» мы запишем «4 2 +». Если вам интересно происхождение обратной польской записи и ее названия, вы можете узнать об этом на Википедии или в поисковике.

То, как вычисляется обратная польская запись и почему стек так полезен при ее использовании, хорошо видно из следующего алгоритма:

For each input value if the value is an integer push the value on to the operand stack else if the value is an operator pop the left and right values from the stack evaluate the operator push the result on to the stack pop answer from stack.

То есть, для выражения «4 2 +» действия будут следующие:

Push(4) push(2) push(pop() + pop())

В конце на стеке окажется одно значение - 6.

Далее приводится полный код простого калькулятора, который считывает выражение (например, 4 2 +) из консоли, разбивает входные данные по пробелам (["4", "2", "+"]) и выполняет алгоритм вычисления. Вычисление продолжается до тех пор, пока не будет встречено слово quit .

Void RpnLoop() { while (true) { Console.Write("> "); string input = Console.ReadLine(); if (input.Trim().ToLower() == "quit") { break; } // Стек еще не обработанных значений. Stack values = new Stack(); foreach (string token in input.Split(new char { " " })) { // Если значение - целое число... int value; if (int.TryParse(token, out value)) { // ... положить его на стек. values.Push(value); } else { // в противном случае выполнить операцию... int rhs = values.Pop(); int lhs = values.Pop(); // ... и положить результат обратно. switch (token) { case "+": values.Push(lhs + rhs); break; case "-": values.Push(lhs - rhs); break; case "*": values.Push(lhs * rhs); break; case "/": values.Push(lhs / rhs); break; case "%": values.Push(lhs % rhs); break; default: // Если операция не +, -, * или / throw new ArgumentException(string.Format("Unrecognized token: {0}", token)); } } } // Последний элемент на стеке и есть результат. Console.WriteLine(values.Pop()); } }

Очередь

Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO) . То есть забирать элементы из очереди мы будем в том же порядке, что и клали. Как реальная очередь или конвейер.

Очереди часто используются в программах для реализации буфера, в который можно положить элемент для последующей обработки, сохраняя порядок поступления. Например, если база данных поддерживает только одно соединение, можно использовать очередь потоков, которые будут, как ни странно, ждать своей очереди на доступ к БД.

Класс Queue

Класс Queue , как и стек, будет реализован с помощью связного списка. Он будет предоставлять методы Enqueue для добавления элемента, Dequeue для удаления, Peek и Count . Как и класс Stack , он не будет реализовывать интерфейс ICollection , поскольку это коллекции специального назначения.

Public class Queue { LinkedList _items = new LinkedList(); public void Enqueue(T value) { throw new NotImplementedException(); } public T Dequeue() { throw new NotImplementedException(); } public T Peek() { throw new NotImplementedException(); } public int Count { get; } }

Метод Enqueue

• Поведение: Добавляет элемент в очередь.
• Сложность: O(1).

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

Public void Enqueue(T value) { _items.AddFirst(value); }

Метод Dequeue

• Поведение: Удаляет первый помещенный элемент из очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Поскольку мы вставляем элементы в начало списка, убирать мы их будем с конца. Если список пуст, кидается исключение.

Public T Dequeue() { if (_items.Count == 0) { throw new InvalidOperationException("The queue is empty"); } T last = _items.Tail.Value; _items.RemoveLast(); return last; }

Метод Peek

• Поведение: Возвращает элемент, который вернет следующий вызов метода Dequeue . Очередь остается без изменений. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T Peek() { if (_items.Count == 0) { throw new InvalidOperationException("The queue is empty"); } return _items.Tail.Value; }

Метод Count

• Поведение:
• Сложность: O(1).

public int Count { get { return _items.Count; } }

Двусторонняя очередь

Двусторонняя очередь (Double-ended queue) , или дек (Deque) , расширяет поведение очереди. В дек можно добавлять или удалять элементы как с начала, так и с конца очереди. Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных. Позже мы рассмотрим вариант реализации стека с помощью двусторонней очереди.

Класс Deque

Класс Deque проще всего реализовать с помощью двусвязного списка. Он позволяет просматривать, удалять и добавлять элементы в начало и в конец списка. Основное отличие двусторонней очереди от обычной - методы Enqueue , Dequeue , и Peek разделены на пары для работы с обоими концами списка.

Public class Deque { LinkedList _items = new LinkedList(); public void EnqueueFirst(T value) { throw new NotImplementedException(); } public void EnqueueLast(T value) { throw new NotImplementedException(); } public T DequeueFirst() { throw new NotImplementedException(); } public T DequeueLast() { throw new NotImplementedException(); } public T PeekFirst() { throw new NotImplementedException(); } public T PeekLast() { throw new NotImplementedException(); } public int Count { get; } }

Метод EnqueueFirst

• Поведение:
• Сложность: O(1).

public void EnqueueFirst(T value) { _items.AddFirst(value); }

Метод EnqueueLast

• Поведение:
• Сложность: O(1).

public void EnqueueLast(T value) { _items.AddLast(value); }

Метод DequeueFirst

• Поведение: Удаляет элемент из начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T DequeueFirst() { if (_items.Count == 0) { throw new InvalidOperationException("DequeueFirst called when deque is empty"); } T temp = _items.Head.Value; _items.RemoveFirst(); return temp; }

Метод DequeueLast

• Поведение:
• Сложность: O(1).

public T DequeueLast() { if (_items.Count == 0) { throw new InvalidOperationException("DequeueLast called when deque is empty"); } T temp = _items.Tail.Value; _items.RemoveLast(); return temp; }

Метод PeekFirst

• Поведение: Возвращает элемент из начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T PeekFirst() { if (_items.Count == 0) { throw new InvalidOperationException("PeekFirst called when deque is empty"); } return _items.Head.Value; }

Метод PeekLast

• Поведение:
• Сложность: O(1).

public T PeekLast() { if (_items.Count == 0) { throw new InvalidOperationException("PeekLast called when deque is empty"); } return _items.Tail.Value; }

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

public int Count { get { return _items.Count; } }

Пример: реализация стека

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

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

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

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

Public class Stack { Deque _items = new Deque(); public void Push(T value) { _items.EnqueueFirst(value); } public T Pop() { return _items.DequeueFirst(); } public T Peek() { return _items.PeekFirst(); } public int Count { get { return _items.Count; } } }

Заметьте, что вся обработка ошибок теперь лежит на классе Deque , и, кроме того, любая оптимизация очереди также отразится на стеке. Реализация обычной очереди на основе двусторонней настолько проста, что мы оставим ее читателю в качестве упражнения.

Хранение элементов в массиве

Как уже было упомянуто, у реализации очереди с использованием массива есть свои преимущества. Она выглядит простой, но на самом деле есть ряд нюансов, которые надо учесть.

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

При создании очереди у нее внутри создается массив нулевой длины. Красные буквы «h» и «t» означают указатели _head и _tail соответственно.

Deque deq = new Deque(); deq.EnqueueFirst(1);

Deq.EnqueueLast(2);

Deq.EnqueueFirst(0);

Обратите внимание: индекс «головы» очереди перескочил в начало списка. Теперь первый элемент, который будет возвращен при вызове метода DequeueFirst - 0 (индекс 3).

Deq.EnqueueLast(3);

Массив заполнен, поэтому при добавлении элемента произойдет следующее:

• Алгорим роста определит размер нового массива.
• Элементы скопируются в новый массив с «головы» до «хвоста».
• Добавится новый элемент.

deq.EnqueueLast(4);

Теперь посмотрим, что происходит при удалении элемента:

Deq.DequeueFirst();

Deq.DequeueLast();

Ключевой момент: вне зависимости от вместимости или заполненности внутреннего массива, логически, содержимое очереди - элементы от «головы» до «хвоста» с учетом «закольцованности». Такое поведение также называется «кольцевым буфером».

Теперь давайте посмотрим на реализацию.

Класс Deque (с использованием массива)

Интерфейс очереди на основе массива такой же, как и в случае реализации через связный список. Мы не будем его повторять. Однако, поскольку список был заменен на массив, у нас добавились новые поля - сам массив, его размер и указатели на «хвост» и «голову» очереди.

Public class Deque { T _items = new T; // Количество элементов в очереди. int _size = 0; // Индекс первого (самого старого) элемента. int _head = 0; // Индекс последнего (самого нового) элемента. int _tail = -1; ... }

Алгоритм роста

Когда свободное место во внутреннем массиве заканчивается, его необходимо увеличить, скопировать элементы и обновить указатели на «хвост» и «голову». Эта операция производится при необходимости во время добавления элемента. Параметр startingIndex используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).

Обратите внимание на то, как извлекаются данные, когда приходится переходить в начало массива при проходе от «головы» к «хвосту».

Private void allocateNewArray(int startingIndex) { int newLength = (_size == 0) ? 4: _size * 2; T newArray = new T; if (_size > 0) { int targetIndex = startingIndex; // Копируем содержимое... // Если массив не закольцован, просто копируем элементы. // В противном случае, копирует от head до конца, а затем от начала массива до tail. // Если tail меньше, чем head, переходим в начало. if (_tail < _head) { // Копируем _items.._items в newArray..newArray[N]. for (int index = _head; index < _items.Length; index++) { newArray = _items; targetIndex++; } // Копируем _items.._items в newArray.. for (int index = 0; index <= _tail; index++) { newArray = _items; targetIndex++; } } else { // Копируем _items.._items в newArray..newArray[N] for (int index = _head; index <= _tail; index++) { newArray = _items; targetIndex++; } } _head = startingIndex; _tail = targetIndex - 1; } else { // Массив пуст. _head = 0; _tail = -1; } _items = newArray; }

Метод EnqueueFirst

• Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst .
• Сложность:

public void EnqueueFirst(T item) { // Проверим, необходимо ли увеличение массива: if (_items.Length == _size) { allocateNewArray(1); } // Так как массив не заполнен и _head больше 0, // мы знаем, что есть место в начале массива. if (_head > 0) { _head--; } else { // В противном случае мы должны закольцеваться. _head = _items.Length - 1; } _items[_head] = item; _size++; if (_size == 1) { // Если мы добавили первый элемент в пустую // очередь, он же будет и последним, поэтому // нужно обновить и _tail. _tail = _head; } }

Метод EnqueueLast

• Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast .
• Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.

public void EnqueueLast(T item) { // Проверим, необходимо ли увеличение массива: if (_items.Length == _size) { allocateNewArray(0); } // Теперь, когда у нас есть подходящий массив, // если _tail в конце массива, нам надо перейти в начало. if (_tail == _items.Length - 1) { _tail = 0; } else { _tail++; } _items[_tail] = item; _size++; if (_size == 1) { // Если мы добавили последний элемент в пустую // очередь, он же будет и первым, поэтому // нужно обновить и _head. _head = _tail; } }

Метод DequeueFirst

• Поведение: Удаляет элемент с начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T DequeueFirst() { if (_size == 0) { throw new InvalidOperationException("The deque is empty"); } T value = _items[_head]; if (_head == _items.Length - 1) { // Если head установлен на последнем индексе, переходим к началу массива. _head = 0; } else { // Переходим к следующему элементу. _head++; } _size--; return value; }

Метод DequeueLast

• Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T DequeueLast() { if (_size == 0) { throw new InvalidOperationException("The deque is empty"); } T value = _items[_tail]; if (_tail == 0) { // Если tail установлен на начало массива, переходим к концу. _tail = _items.Length - 1; } else { // Переходим к предыдущему элементу. _tail--; } _size--; return value; }

Метод PeekFirst

• Поведение: Возвращает элемент с начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T PeekFirst() { if (_size == 0) { throw new InvalidOperationException("The deque is empty"); } return _items[_head]; }

Метод PeekLast

• Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

public T PeekLast() { if (_size == 0) { throw new InvalidOperationException("The deque is empty"); } return _items[_tail]; }

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

public int Count { get { return _size; } }

Продолжение следует

Вот мы и закончили четвертую часть нашего цикла статей. В ней мы рассмотрели стеки и очереди. В следующий раз мы перейдем к бинарным деревьям поиска.

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

Теория

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

Стек (англ. 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 ; #include ; 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");//ставим на паузу }

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

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

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

Теги: Добавить метки

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

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

Концептуально, структура данных — стек очень проста: она позволяет добавлять или удалять элементы в определенном порядке. Каждый раз, когда добавляется элемент, он попадает на вершину стека, единственный элемент, который может быть удален из стека — элемент, который находится на вершине стека. Таким образом, стек, как принято говорить, «первым пришел, последним ушел — FILO» или «последним пришел, первым ушел — LIFO». Первый элемент, добавленный в стек будет удален из него в последнюю очередь.

Так в чем же дело? Зачем нам нужны стеки? Как мы уже говорили, стеки — удобный способ организации вызовов функций. В самом деле, «стек вызовов» это термин, который часто используют для обозначения списка функций, которые сейчас либо выполняются, либо находятся в режиме ожидания возвращаемого значения других функций.

В некотором смысле, стеки являются частью фундаментального языка информатики. Когда вы хотите реализовать очередь типа — «первый пришел, последним ушел», то имеет смысл говорить о стеках с использованием общей терминологии. Кроме того, такие очереди участвуют во многих процессах, начиная от теоретических компьютерных наук, например функции push-down и многое другое.

Стеки имеют некоторые ассоциируемые методы:

• Push — добавить элемент в стек;
• Pop — удалить элемент из стека;
• Peek — просмотреть элементы стека;
• LIFO — поведение стека,
• FILO Equivalent to LIFO

Этот стек был реализован с шаблонами, чтобы его можно было использовать практически для любых типов данных. Причем размер стека определяется динамически, во время выполнения программы. В стек добавлена также дополнительная функция: peek() , которая показывает n-й элемент от вершины стека.

#ifndef STACK_H #define STACK_H #include // для assert #include #include // для setw template class Stack { private: T *stackPtr; // указатель на стек const int size; // максимальное количество элементов в стеке int top; // номер текущего элемента стека public: Stack(int = 10); // по умолчанию размер стека равен 10 элементам Stack(const Stack &); // конструктор копирования ~Stack(); // деструктор inline void push(const T &); // поместить элемент в вершину стека inline T pop(); // удалить элемент из вершины стека и вернуть его inline void printStack(); // вывод стека на экран inline const T &Peek(int) const; // n-й элемент от вершины стека inline int getStackSize() const; // получить размер стека inline T *getPtr() const; // получить указатель на стек inline int getTop() const; // получить номер текущего элемента в стеке }; // реализация методов шаблона класса STack // конструктор Стека template Stack::Stack(int maxSize) : size(maxSize) // инициализация константы { stackPtr = new T; // выделить память под стек top = 0; // инициализируем текущий элемент нулем; } // конструктор копирования template Stack::Stack(const Stack & otherStack) : size(otherStack.getStackSize()) // инициализация константы { stackPtr = new T; // выделить память под новый стек top = otherStack.getTop(); for(int ix = 0; ix < top; ix++) stackPtr = otherStack.getPtr(); } // функция деструктора Стека template Stack::~Stack() { delete stackPtr; // удаляем стек } // функция добавления элемента в стек template inline void Stack::push(const T &value) { // проверяем размер стека assert(top < size); // номер текущего элемента должен быть меньше размера стека stackPtr = value; // помещаем элемент в стек } // функция удаления элемента из стека template inline T Stack::pop() { // проверяем размер стека assert(top > 0); // номер текущего элемента должен быть больше 0 stackPtr[--top]; // удаляем элемент из стека } // функция возвращает n-й элемент от вершины стека template inline const T &Stack::Peek(int nom) const { // assert(nom <= top); return stackPtr; // вернуть n-й элемент стека } // вывод стека на экран template inline void Stack::printStack() { for (int ix = top - 1; ix >= 0; ix--) cout << "|" << setw(4) << stackPtr << endl; } // вернуть размер стека template inline int Stack::getStackSize() const { return size; } // вернуть указатель на стек (для конструктора копирования) template inline T *Stack::getPtr() const { return stackPtr; } // вернуть размер стека template inline int Stack::getTop() const { return top; } #endif // STACK_H

Шаблон класса Stack реализован в отдельном *.h файле, да, именно реализован, я не ошибся. Все дело в том, что и интерфейс шаблона класса и реализация должны находиться в одном файле, иначе вы увидите список ошибок похожего содержания:

ошибка undefined reference to «метод шаблона класса»

Интерфейс шаблона класса объявлен с 9 по 28 строки. Все методы класса содержат комментарии и, на мой взгляд, описывать их работу отдельно не имеет смысла. Обратите внимание на то, что все методы шаблона класса Стек объявлены как . Это сделано для того, чтобы ускорить работу класса. Так как встроенные функции класса работают быстрее, чем внешние.

Сразу после интерфейса шаблона идет реализация методов класса Стек, строки 32 — 117. В реализации методов класса ничего сложного нет, если знать как устроен стек, шаблоны и . Заметьте, в классе есть два конструктора, первый объявлен в строках 32-33, — это конструктор по умолчанию. А вот конструктор в строках 41-5, — это конструктор копирования. Он нужен для того, чтобы скопировать один объект в другой. Метод Peek , строки 80 — 88 предоставляет возможность просматривать элементы стека. Необходимо просто ввести номер элемента, отсчет идет от вершины стека. Остальные функции являются служебными, то есть предназначены для использования внутри класса, конечно же кроме функции printStack() , она вывод элементы стека на экран.

Теперь посмотрим на драйвер для нашего стека, под драйвером я подразумеваю программу в которой тестируется работа класса. Как всегда это main функция, в которой мы и будем тестировать наш шаблон класса Stack . Смотрим код ниже:

#include using namespace std; #include "stack.h" int main() { Stack stackSymbol(5); int ct = 0; char ch; while (ct++ < 5) { cin >> ch; stackSymbol.push(ch); // помещаем элементы в стек } cout << endl; stackSymbol.printStack(); // печать стека cout << "\n\nУдалим элемент из стека\n"; stackSymbol.pop(); stackSymbol.printStack(); // печать стека Stack newStack(stackSymbol); cout << "\n\nСработал конструктор копирования!\n"; newStack.printStack(); cout << "Второй в очереди элемент: "<< newStack.Peek(2) << endl; return 0; }

Создали объект стека, строка 9, размер стека при этом равен 5, то есть стек может поместить не более 5 элементов. Заполняем стек в , строки 13 — 17. В строке 21 выводим стек на экран, после удаляем один элемент из стека, строка 24 и снова выводим содержимое стека, поверьте оно изменилось, ровно на один элемент. Смотрим результат работы программы:

LOTR! | ! | R | T | O | L Удалим элемент из стека | R | T | O | L Сработал конструктор копирования! | R | T | O | L Второй в очереди элемент: T

В строке 28 мы воспользовались конструктором копирования, о том самом, о котором я писал выше. Не забудем про функцию peek() , давайте посмотри на второй элемент стека, строка 33.

На этом все! Стек у нас получился и исправно работает, попробуйте его протестировать, например на типе данных int . Я уверен, что все останется исправно работать.

– Игорь (Администратор)

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

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

Стек (stack) - это метод представления однотипных данных (можно просто называть типом) в порядке LIFO (Last In - First Out, что означает "первый вошел - последний вышел"). Стоит упомянуть, что в русской технике его так же называют "магазином". И речь тут не о продуктовом магазине, а о рожке с патронами для оружия, так как принцип весьма схож - первый вставленный патрон будет использован последним.

Примечание : Стоит знать, что у этого слова могут быть и другие значения. Поэтому если речь не касается компьютеров, то имеет смысл уточнить.

Чтобы лучше понять, приведу жизненный пример. Допустим у вас есть стопка листов. Каждый исписанный лист вы кладете рядом, а каждый следующий поверх остальных. Чтобы достать к примеру, самый первый лист из полученной стопки, вам необходимо вытащить все остальные листы. Вот по этому же самому принципу и устроен stack. То есть, каждый последний добавленный элемент становится верхним и чтобы достать, к примеру, самый первый элемент необходимо вытащить все остальные.

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

В компьютерной сфере стек используется в аппаратных устройствах (например, процессоре), в операционной системе и многих программах. Если рассматривать пример, с которым знаком практически каждый, кто занимался программированием, то без стека не была бы возможна рекурсия, ведь при каждом повторном входе в функцию нужно сохранять текущее состояние на вершине, а при каждом выходе из функции быстро восстанавливать это состояния (то есть, как раз последовательность LIFO). А если копнуть еще глубже, то в принципе весь подход к запуску и выполнению программ устроен на принципе стека, где прежде чем следующая программа, запущенная из основной, будет выполняться, состояние предыдущей заносится в стек, чтобы когда запущенное приложение или подпрограмма закончила выполняться, предыдущая программа нормально продолжила выполняться с места остановки.

Какие операции у stack? Основных операций всего две:

1. Добавление элемента в вершину стека называется push

2. Извлечения верхнего элемента называется pop

Но, так же периодически можно встретить реализацию операции чтения верхнего элемента без его извлечения - называется peek .

Как организуется стек? Обычно стек реализуется двумя вариантами:

1. С помощью массива и переменной, которая указывает на ячейку с вершиной стека

2. С помощью связанных списков

У каждого из этих 2-х вариантов есть свои плюсы и минусы. Например, связанные списки более безопасны в плане применения, так как каждый добавляемый элемент помещается в динамически созданную структуру (нет проблем с количеством элементов - нет дырок безопасности, позволяющих свободно перемещаться в памяти программы). Однако, в плане хранения и быстроты использования они менее эффективны (требуют дополнительное место для хранения указателей; разбросаны в памяти, а не расположены друг за другом, как в массивах).

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

Теги: Стек, стек на си, реализация стека, стек на массиве, динамически растущий стек, стек на односвязном сиске

Стек

С тек – наверное, самая простая структура данных, которую мы будем изучать и которой будем постоянно пользоваться. Стек – это структура данных, в которой элементы поддерживают принцип LIFO (“Last in – first out”): последним зашёл – первым вышел. Или первым зашёл – последним вышел.

Стек позволяет хранить элементы и поддерживает, обычно, две базовые операции:

• PUSH – кладёт элемент на вершину стека
• POP – снимает элемент с вершины стека, перемещая вершину к следующему элементу

Также часто встречается операция PEEK, которая получает элемент на вершине стека, но не снимает его оттуда.

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

Пусть, например, у нас есть стек чисел. Выполним несколько команд. Изначально стек пуст. Вершина стека – указатель на первый элемент, никуда не указывает. В случае си она может быть равна NULL.

Теперь стек состоит из одного элемента, числа 3. Вершина стека указывает на число 3.

Стек состоит из двух элементов, 5 и 3, при этом вершина стека указывает на 5.

Стек состоит из трёх элементов, вершина стека указывает на 7.

Вернёт значение 7, в стеке останется 5 и 3. Вершина будет указывать на следующий элемент – 5.

Вернёт 5, в стеке останется всего один элемент, 3, на который будет указывать вершина стека.

Вернёт 3, стек станет пуст.

Часто сравнивают стек со стопкой тарелок. Чтобы достать следующую тарелку, необходимо снять предыдущие. Вершина стека – это вершина стопки тарелок.

Когда мы будем работать со стеком, возможны две основные и часто встречающиеся ошибки:

• 1. Stack Underflow: Попытка снять элемент с пустого стека
• 2. Stack Overflow: Попытка положить новый элемент на стек, который не может больше расти (например, не хватает оперативной памяти)

Программная реализация

Р ассмотрим три простые реализации стека:

Стек фиксированного размера, построенный на массиве

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

Сначала определяем максимальный размер массива и тип данных, которые будут в нём храниться:

#define STACK_MAX_SIZE 20 typedef int T;

Теперь сама структура

Typedef struct Stack_tag { T data; size_t size; } Stack_t;

Здесь переменная size – это количество элементов, и вместе с тем указатель на вершину стека. Вершина будет указывать на следующий элемент массива, в который будет занесено значение.

Кладём новый элемент на стек.

Void push(Stack_t *stack, const T value) { stack->data = value; stack->size++; }

Единственная проблема – можно выйти за пределы массива. Поэтому всегда надо проверять, чтобы не было ошибки Stack overflow:

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push(Stack_t *stack, const T value) { if (stack->size >= STACK_MAX_SIZE) { exit(STACK_OVERFLOW); } stack->data = value; stack->size++; }

Аналогично, определим операцию Pop, которая возвращает элемент с вершины и переходит к следующему

T pop(Stack_t *stack) { if (stack->size == 0) { exit(STACK_UNDERFLOW); } stack->size--; return stack->data; }

И функция peek, возвращающая текущий элемент с вершины

T peek(const Stack_t *stack) { if (stack->size <= 0) { exit(STACK_UNDERFLOW); } return stack->data; }

Ещё одно важное замечание – у нас нет функции создания стека, поэтому необходимо вручную обнулять значение size

Вспомогательные функции для печати элементов стека

Void printStackValue(const T value) { printf("%d", value); } void printStack(const Stack_t *stack, void (*printStackValue)(const T)) { int i; int len = stack->size - 1; printf("stack %d > ", stack->size); for (i = 0; i < len; i++) { printStackValue(stack->data[i]); printf(" | "); } if (stack->size != 0) { printStackValue(stack->data[i]); } printf("\n"); }

Заметьте, что в функции печати мы использует int, а не size_t, потому что значение len может стать отрицательным. Функция печатает сначала размер стека, а потом его содержимое, разделяя элементы символом |

Проверка

Stack_t stack; stack.size = 0; push(&stack, 3); printStack(&stack, printStackValue); push(&stack, 5); printStack(&stack, printStackValue); push(&stack, 7); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); _getch();

Рассмотрим также ситуации, когда есть ошибки использования. Underflow

Void main() { Stack_t stack; stack.size = 0; push(&stack, 3); pop(&stack); pop(&stack); _getch(); }

Void main() { Stack_t stack; size_t i; stack.size = 0; for (i = 0; i < 100; i++) { push(&stack, i); } _getch(); }

Динамически растущий стек на массиве

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

Стек будет состоять из указателя на данные, размера массива (максимального), и числа элементов в массиве. Это число также будет и указывать на вершину.

Typedef struct Stack_tag { T *data; size_t size; size_t top; } Stack_t;

Для начала понадобится некоторый начальный размер массива, пусть он будет равен 10

#define INIT_SIZE 10

Алгоритм работы такой: мы проверяем, не превысило ли значение top значение size. Если значение превышено, то увеличиваем размер массива. Здесь возможно несколько вариантов того, как увеличивать массив. Можно прибавлять число, можно умножать на какое-то значение. Какой из вариантов лучше, зависит от специфики задачи. В нашем случае будем умножать размер на число MULTIPLIER

#define MULTIPLIER 2

Максимального размера задавать не будем. Программа будет выпадать при stack overflow или stack underflow. Будем реализовывать тот же интерфейс (pop, push, peek). Кроме того, так как массив динамический, сделаем некоторые вспомогательные функции, чтобы создавать стек, удалять его и чистить.

Во-первых, функции для создания и удаления стека и несколько ошибок

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t* createStack() { Stack_t *out = NULL; out = malloc(sizeof(Stack_t)); if (out == NULL) { exit(OUT_OF_MEMORY); } out->size = INIT_SIZE; out->data = malloc(out->size * sizeof(T)); if (out->data == NULL) { free(out); exit(OUT_OF_MEMORY); } out->top = 0; return out; } void deleteStack(Stack_t **stack) { free((*stack)->data); free(*stack); *stack = NULL; }

Всё крайне просто и понятно, нет никаких подвохов. Создаём стек с начальной длиной и обнуляем значения.

Теперь напишем вспомогательную функцию изменения размера.

Void resize(Stack_t *stack) { stack->size *= MULTIPLIER; stack->data = realloc(stack->data, stack->size * sizeof(T)); if (stack->data == NULL) { exit(STACK_OVERFLOW); } }

Здесь, заметим, в случае, если не удалось выделить достаточно памяти, будет произведён выход с STACK_OVERFLOW.

Функция push проверяет, вышли ли мы за пределы массива. Если да, то увеличиваем его размер

Void push(Stack_t *stack, T value) { if (stack->top >= stack->size) { resize(stack); } stack->data = value; stack->top++; }

Функции pop и peek аналогичны тем, которые использовались для массива фиксированного размера

T pop(Stack_t *stack) { if (stack->top == 0) { exit(STACK_UNDERFLOW); } stack->top--; return stack->data; } T peek(const Stack_t *stack) { if (stack->top <= 0) { exit(STACK_UNDERFLOW); } return stack->data; }

Проверим

Void main() { int i; Stack_t *s = createStack(); for (i = 0; i < 300; i++) { push(s, i); } for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); } deleteStack(&s); _getch(); }

Напишем ещё одну функцию, implode, которая уменьшает массив до размера, равного числу элементов в массиве. Она может быть использована тогда, когда уже известно, что больше элементов вставлено не будет, и память может быть частично освобождена.

Void implode(Stack_t *stack) { stack->size = stack->top; stack->data = realloc(stack->data, stack->size * sizeof(T)); }

Можем использовать в нашем случае

For (i = 0; i < 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }

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

У неё есть недостаток, связанный с методом увеличения потребляемой памяти. При умножении в 2 раза (в нашем случае) требуется мало обращений к памяти, но при этом каждое последующее увеличение может привести к ошибке, особенно при маленьком количестве памяти в системе. Если же использовать более щадящий способ выделения памяти (например, каждый раз прибавлять по 10), то число обращений увеличится и скорость упадёт. На сегодня, проблем с размером памяти обычно нет, а менеджеры памяти и сборщики мусора (которых нет в си) работают быстро, так что агрессивное изменение преобладает (на примере, скажем, реализации всей стандартной библиотеки языка Java).

Реализация стека на односвязном списке

Ч то такое односвязный список, . Коротко: односвязный список состоит из узлов, каждый из которых содержит полезную информацию и ссылку на следующий узел. Последний узел ссылается на NULL.

Никакого максимального и минимального размеров у нас не будет (хотя в общем случае может быть). Каждый новый элемент создаётся заново. Для начала определим структуру узел

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag { T value; struct Node_tag *next; } Node_t;

Функция вставки первого элемента проста: создаём новый узел. Указатель next кидаем на старый узел. Далее указатель на вершину стека перекидываем на вновь созданный узел. Теперь вершина стека указывает на новый узел.

Void push(Node_t **head, T value) { Node_t *tmp = malloc(sizeof(Node_t)); if (tmp == NULL) { exit(STACK_OVERFLOW); } tmp->next = *head; tmp->value = value; *head = tmp; }

Функция pop берёт первый элемент (тот, на который указывает вершина), перекидывает указатель на следующий элемент и возвращает первый. Здесь есть два варианта – можно вернуть узел или значение. Если вернём значение, то придётся удалять узел внутри функции

Node_t* pop1(Node_t **head) { Node_t *out; if ((*head) == NULL) { exit(STACK_UNDERFLOW); } out = *head; *head = (*head)->next; return out; }

T pop2(Node_t **head) { Node_t *out; T value; if (*head == NULL) { exit(STACK_UNDERFLOW); } out = *head; *head = (*head)->next; value = out->value; free(out); return value; }

Теперь вместо проверки на длину массива везде используется проверка на равенство NULL вершины стека.

Простая функция peek

T peek(const Node_t* head) { if (head == NULL) { exit(STACK_UNDERFLOW); } return head->value; }

Итерирование достаточно интересное. Просто переходим от одного узла к другому, пока не дойдём до конца

Void printStack(const Node_t* head) { printf("stack >"); while (head) { printf("%d ", head->value); head = head->next; } }

И ещё одна проблема – теперь нельзя просто посмотреть размер стека. Нужно пройти от начала до конца и посчитать все элементы. Например, так

Size_t getSize(const Node_t *head) { size_t size = 0; while (head) { size++; head = head->next; } return size; }

Конечно, можно хранить размер отдельно, можно обернуть стек со всеми данными ещё в одну структуру и т.д. Рассмотрим всё это при более подробном изучении списков.