Стек - это феномен программирования и естественное решение. Стек сразу пришел в компьютерное дело и стал таким «родным», как будто именно с него все начиналось.

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

На заре начала: процессор, память и стек

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

• адрес = значение;
• индекс = значение.

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

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

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

Суть и понятие стека

Процессор и память - основные конструктивные элементы компьютера. Процессор исполняет команды, манипулирует адресами памяти, извлекает и изменяет значения по этим адресам. На языке программирования все это трансформируется в переменные и их значения. Суть стека и понятие last in first out (LIFO) остается неизменным.

Аббревиатура LIFO уже не используется так часто, как раньше. Вероятно потому, что списки трансформировались в объекты, а очереди first in first out (FIFO) применяются по мере необходимости. Динамика типов данных потеряла свою актуальность в контексте описания переменных, но приобрела свою значимость на момент исполнения выражений: тип данного определяется в момент его использования, а до этого момента можно описывать что угодно и как угодно.

Так, стек - что это такое? Теперь вы знаете, что это вопрос неуместный. Ведь без стека нет современного программирования. Любой вызов функции - это передача параметров и адреса возврата. Функция может вызвать другую функцию - это опять передача параметров и адреса возврата. Наладить механизм вызова значений без стека - это лишняя работа, хотя достижимое решение, безусловно, возможное.

Многие спрашивают: "Стек - что это такое?". В контексте вызова функции он состоит из трех действий:

• сохранения адреса возврата;
• сохранения всех передаваемых переменных или адреса на них;
• вызова функции.

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

Свойства стека

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

Характерные свойства стека - это его размер и длина элементов. На уровне процессора все определяется разрядностью, адресацией памяти и физикой доступа к ней. Интересная особенность и традиция: стек растет вниз, то есть в сторону уменьшения адресов памяти, а память программ и данных - вверх. Это обычно, но не обязательно. Здесь важен смысл - пришел последним, а ушел первым. Это удивительно простое правило позволяет строить интересные алгоритмы работы прежде всего на языках высокого уровня. Теперь вы не будете спрашивать, стек - что это такое.

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

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

Массивы, коллекции, списки, очереди... Стек!

Часто люди задают вопрос: "Стек - что это такое?". "Программирование" и "систематизация" - интересные понятия: они не синонимы, но так тесно связаны. Программирование прошло очень быстро такой длительный путь, что достигнутые вершины кажутся идеальными. Скорее всего, это не так. Но очевидно другое.

Идея стека стала привычной не только на уровне различных языков программирования, но и на уровне их конструкций и возможностей по созданию типов данных. Любой массив имеет push и pop, а понятия "первый и последний элементы массива" стали традиционными. Раньше были просто элементы массива, а сегодня есть:

• элементы массива;
• первый элемент массива;
• последний элемент массива.

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

Особенно примечательно, что популярные языки программирования не имеют конструкции stack. Но они предоставляют его идею разработчику в полном объеме.

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

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

Стек

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

Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека - это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.

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

Куча

Куча - это хранилище памяти, также расположенное в ОЗУ, которое допускает динамическое выделение памяти и не работает по принципу стека: это просто склад для ваших переменных. Когда вы выделяете в куче участок памяти для хранения переменной, к ней можно обратиться не только в потоке, но и во всем приложении. Именно так определяются глобальные переменные. По завершении приложения все выделенные участки памяти освобождаются. Размер кучи задаётся при запуске приложения, но, в отличие от стека, он ограничен лишь физически, и это позволяет создавать динамические переменные.

Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями - это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.

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

Стек - это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (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; } }

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

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

При освоении программирования, рано или поздно, возникает вопрос: "Что такое стек? ".
Наиболее наглядным способом объяснения я считаю программу на языке ассемблера (не пугайтесь), которая просто добавляет данные в стек.

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

Зачем все это нужно?

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

Как это работает?

Давайте разберем работу со стеком на примере контроллеров семейства MSP430. Я выбрал их только из-за того что у меня оказалась установленной среда для работы с ними.
В MSP430 стек основан на предекрементной схеме. Т.е. перед тем как вы записываете данные в стек он уменьшает адрес вершины стека (верхней тарелки). Бывает также постдекрементный/постинкрементный (вычитание/добавление вершины стека происходит после записи данных) и прединкрементный (перед записью адрес вершины увеличивается).
Если стек увеличивает свой адрес при записи данных, говорят о стеке растущем вверх, если же уменьшает - вниз.
За хранения адреса вершины стека отвечает регистр SP.

Как видите адрес вершины по умолчанию у нас 0x0A00.

Рассмотрим вот такую программу:

PUSH #0123h ; Помещение числа 0123h на вершину стека (TOS) ; копируем данные из памяти MOV.W &0x0A00, R5 MOV.W &0x09FE, R6 ; пишем еще два числа PUSH #9250h PUSH #0000h ; выводим данные из стека POP R8 POP R9 POP R10

Что делает эта программа?

Командой PUSH мы помещаем данные 0123h в стек. Казалось бы этой командой мы запишем 0123h в память по адресу 0x0A00, но мы ведь помним, что стек у нас предекрементный. Поэтому сначала адрес уменьшается на 2 (0x0A00 - 2 = 0x09FE) и в ячейку с полученным адресом записываются данные.

Вот так выглядела память изначально:

После выполнения команды PUSH (красным выделены изменения):

Итак данные записались.
Проверим так ли это выполнив две команды пересылки (mov). Сначала получим данные из ячейки 0x0A00 и запишем их в регистр R5, а затем запишем в регистр R6 данные из ячейки 0x09FE.
После этого в регистрах будет данные:

При выполнении команд POP вершина стека будет увеличиваться на 2 при каждой команде, а в регистры R8-10 попадут данные: 0x0000, 0x9250 и 0x0123 соответственно.
При добавлении других данные память (которая все еще содержит данные, выведенные из стека) будет заполнена новыми значениями.

Проиллюстрировать работу со стеком можно так (слева на право):

Изначально адресом стека был 0x0A00, в нем хранились 0000. При выполнении PUSH верхушкой стека стала ячека ниже (с адресом 0x09FE) и в неё записались данные. С каждой следующей командой верхушка находиться ниже в памяти.
При выполнении команды POP картина обратная.

Жду ваши вопросы в комментариях.

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

Теория

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

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

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

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

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

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