Структуры данных: общее понятие, реализация. Простейшие структуры данных: очередь, стек. Использование стека и обратная польская запись.  Что такое стек

Шаблон класса 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 . Я уверен, что все останется исправно работать.

(англ. last in - first out , «последним пришёл - первым вышел»).

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

В некоторых языках (например, Lisp , Python ) стеком можно назвать любой список, так как для них доступны операции pop и push. В языке C++ стандартная библиотека имеет класс с реализованной структурой и методами . И т. д.

Программный стек

Организация в памяти

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

Но также часто стек располагается в одномерном массиве с упорядоченными адресами. Такая организация стека удобна, если элемент информации занимает в памяти фиксированное количество слов, например, 1 слово. При этом отпадает необходимость хранения в элементе стека явного указателя на следующий элемент стека, что экономит память. При этом указатель стека (Stack Pointer , - SP ) обычно является регистром процессора и указывает на адрес головы стека.

Предположим для примера, что голова стека расположена по меньшему адресу, следующие элементы располагаются по нарастающим адресам. При каждом вталкивании слова в стек, SP сначала уменьшается на 1 и затем по адресу из SP производится запись в память. При каждом извлечении слова из стека (выталкивании) сначала производится чтение по текущему адресу из SP и последующее увеличение содержимого SP на 1.

При организации стека в виде однонаправленного списка значением переменной стека является указатель на его вершину - адрес вершины. Если стек пуст, то значение указателя равно NULL.

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

struct stack { char * data ; struct stack * next ; };

Операции со стеком

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push ), удаление элемента (pop ) и чтение головного элемента (peek ) .

При проталкивании (push ) добавляется новый элемент, указывающий на элемент, бывший до этого головой. Новый элемент теперь становится головным.

При удалении элемента (pop ) убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент). При этом значение убранного элемента возвращается.

void push ( STACK * ps , int x ) // Добавление в стек нового элемента { if ( ps -> size == STACKSIZE ) // Не переполнен ли стек? { fputs ( "Error: stack overflow \n " , stderr ); abort (); } else { ps -> items [ ps -> size ++ ] = x ; } } int pop ( STACK * ps ) // Удаление из стека { if ( ps -> size == 0 ) // Не опустел ли стек? { fputs ( "Error: stack underflow \n " , stderr ); abort (); } else { return ps -> items [ -- ps -> size ]; } }

Область применения

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

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

Идея стека используется в стековой машине среди стековых языков программирования .

Применение стека упрощает и ускоряет работу программы, так как идет обращение к нескольким данным по одному адресу.

Аппаратный стек

До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на адрес головы стека в области физической оперативной памяти, причём под хранение данных в стеке необходимо зарезервировать нужное количество ячеек памяти (очевидно, что стек в ПЗУ , естественно, не может быть организован). Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищённом режиме работы процессора сегмент состояния задачи содержит четыре селектора сегментов стека (для разных уровней привилегий), но в каждый момент используется только один стек .

Примечания

1. Машина Тьюринга: Введение (неопр.) . Проверено 12 февраля 2013.

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

Метод 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).

Метод Count

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

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

Двусторонняя очередь (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).

Метод EnqueueLast

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

Метод DequeueFirst

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

Метод DequeueLast

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

Метод PeekFirst

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

Метод PeekLast

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

Метод Count

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

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

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

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

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

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

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.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 .
• Сложность:

Метод 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).

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

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