Стеки деки очереди c

Стеки деки очереди c

    Переводы , 20 августа 2015 в 17:59

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

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

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

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

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

Ивент перенесён, есть новые даты ( 26 – 27 сентября ) , Новосибирск, беcплатно

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

Класс Stack

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

Метод Push

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

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

Метод Pop

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

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

Метод Peek

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

Метод Count

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

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

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

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

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

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

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

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

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

Очередь

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

Читайте также:  Интернет через спутниковую тарелку триколор отзывы

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

Класс Queue

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

Метод Enqueue

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

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

Метод Dequeue

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

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

Метод Peek

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

Метод Count

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

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

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

Класс Deque

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

Метод EnqueueFirst

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

Метод EnqueueLast

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

Метод DequeueFirst

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

Метод DequeueLast

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

Метод PeekFirst

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

Метод PeekLast

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

Метод Count

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

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

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

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

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

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

Читайте также:  Как нарисовать телефон ребенку

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

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

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

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

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

Добавляем элемент в начало

Добавляем элемент в конец

Добавляем еще один элемент в начало

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

И еще один в конец

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

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

Добавляем значение в конец расширенного массива

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

Удаляем элемент из начала

Удаляем элемент с конца

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

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

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

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

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

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

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

Метод EnqueueFirst

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

Метод EnqueueLast

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

Метод DequeueFirst

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

Метод DequeueLast

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

Метод PeekFirst

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

Метод PeekLast

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

Метод Count

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

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

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

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

(по способу выполнения операции добавления и удаления элементов)

Стек Очередь Дек

Стек — это линейный список с переменной длиной, в котором все операции вставки, удаления и доступа к данным выполняются только на одном из концов списка, называемом вершиной стека.

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

Читайте также:  Настройка каналов на сони бравиа пошаговая инструкция

Очередь — это такой линейный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение — с другой стороны (называемой началом или головой очереди).

Очереди также называют «списками типа FIFO» (First — In — First- Out — «первым пришел — первым исключается»).

В исходном состоянии указатели на начало и на конец указывают на начало области памяти. Равенство этих двух указателей (при любом их значении) является признаком пустой очереди.

Дек (от англ. deq — double ended queue, т.е. очередь с двумя концами), представляет собой структуру данных, в которой можно добавлять и удалять элементы с двух сторон.

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

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

Формы записи арифметического выражения:

Инфиксная — запись, в которой знак арифметической операции расположен между операндами (А+В).

Префиксная — форма записи, в которой знак операции предшествует операндам (+АВ).

Постфиксная — запись, в которой знак операции располагается следом за операндами (АВ+).

Примечание: префиксная форма не является зеркальным отображением постфиксной. Например:

*-AB+CD — префиксная запись;

AB-CD+* — постфиксная запись.

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

Обратная польская запись обладает рядом замечательных свойств, которые превращают ее в идеальный промежуточный язык при трансляции. Во-первых, вычисление выражения, записанного в обратной польской записи, может проводиться путем однократного просмотра, что является весьма удобным при генерации объектного кода программ. Например, выражение (A+B)*(C+D)-E в постфиксной форме будет иметь вид: AB+CD+*E-; вычисление полученного выражения может быть проверено следующим образом:

Дек (deque) представляет двустороннюю очередь, в которой элементы можно добавлять как в начало, так и в конец. Удаление также может идти как с начала, так и с конца.

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

Класс дека будет следующим:

В отличие от класса очереди здесь определены два метода для добавления и два для удаления.

Для добавления в начало очереди переустанавливаем ссылку на переменную head:

Добавление элемента в конец дека вызывает аналогичную переустановку переменной tail:

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

При удалении последнего элемента переустанавливается переменная tail на предпоследний элемент:

Сложность алгоритмов всех методов добавления и удаления из дека составляет O(1) .

Ссылка на основную публикацию
Adblock detector