Стеки и очереди в STL

Стеки и очередиСтеки и очереди — это два контейнера в STL, которые очень просты по своей природе. Это простейшие контейнеры, имеющие широкое применение в программировании.

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

Stack

Контейнер стека в STL — это разновидность контейнерных адаптеров. Он используется для репликации структуры данных стека в C++. Контейнер стека — это набор элементов, в который элементы вставляются с одного конца и также удаляются с того же конца.

Эта общая точка добавления и удаления известна как «Вершина стека».

Графическое представление стека показано ниже:

Схема стека

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

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

Чтобы реализовать контейнер стека, нам нужно включить заголовок <stack> в нашу программу:

#include<stack>

Общий синтаксис объявления для контейнера стека:

stack<objectType> stackName;

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

Далее давайте обсудим различные операции, которые поддерживает контейнер стека в STL.

  • push: операция push используется для вставки элемента в стек. Эта операция всегда добавляет элементы на вершину стека.

Рассмотрим пустой стек mystack типа integer:

Пустой стек

Далее добавим в стек элемент 1:

Читать также:  Переменные в С++

Добавление в стек

Затем мы добавляем элемент 3 в стек:

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

Согласно представлению, в результате операции push элемент добавляется на вершину стека. После каждой операции push размер стека увеличивается на 1.

  • pop: операция pop используется для удаления элемента из стека. Удаляется элемент, на который указывает вершина стека. В результате операции извлечения размер стека уменьшается на 1.

Давайте посмотрим, как выглядит операция pop. Рассмотрим стек mystack, как показано выше, в котором мы уже поместили 2 элемента:

Операция pop

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

Вызов pop выполняется

Если мы снова вызовем pop(), то следующий элемент (в данном случае 1) будет удален, что приведет к пустому стеку:

Вызовем pop()

  • top: возвращает самый верхний элемент стека.
  • empty: проверяет, пуст стек или нет.
  • size: возвращает размер стека, т.е. количество элементов в стеке.

Ниже приведен пример реализации стека для лучшего понимания операций:

Вывод данных:

The stack is :             9             7             5             3             1
Size of stack:             5
Top of stack:             9
oddstk.pop():             7             5             3             1
Another pop () :             5             3             1

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

Читать также:  Типы наследования в C++

Таким образом, вы увидели стек и его операции в STL. Далее в этой статье вы увидите подробную реализацию еще одного простого контейнера STL, который называется «Queue» (очередь).

Queue

Очередь — это еще один контейнер в STL, очень простой и полезный. Данный контейнер — это копия структуры данных очереди в C++. В отличие от стека, в контейнере очереди есть два конца, т.е. передний и задний.

Элементы добавляются в очередь в конце, а удаляются из начала очереди. Как правило, очередь использует тип расположения FIFO (первый вошел, первый вышел).

Чтобы реализовать контейнер очереди в программе, мы должны включить заголовок <queue> в код:

#include <queue>

Общий синтаксис объявления очереди:

queue<objectType> queue_name;

Мы объявляем контейнер очереди следующим образом:

Queue<int> myqueue;

Операции с очередью

Теперь мы рассмотрим различные операции, поддерживаемые очередью.

  • push: Функция push добавляет элемент в конец очереди.
  • pop: Функция pop удаляет первый элемент очереди, т.е. элемент в начале очереди.

Давайте разберемся с функциями push и pop.

Рассмотрим пустую очередь, объявленную выше myqueue. Мы помещаем в очередь четное число 2 с помощью операции:

myqueue.push(2);

Теперь очередь будет выглядеть так:

Очередь

Затем мы добавляем «4» в очередь с вызовом «myqueue.push(4)».

Читать также:  Книга «Управление электронными устройствами на C++»

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

Очередь2

Как видно выше, элементы помещаются в очередь сзади.

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

myqueue.pop();

Очередь

Итак, как мы видим, при вызове pop() элемент в начале очереди удаляется. Это означает, что первый элемент, входящий в очередь, является первым элементом, который выходит из очереди.

  • front: эта функция возвращает ссылку на первый элемент очереди.
  • back: back возвращает ссылку на последний элемент в очереди.
  • empty: проверяет, пуста ли очередь.
  • size: возвращает размер очереди, т.е. количество элементов в очереди.

Ниже приведен пример программы, демонстрирующий операции, используемые контейнером queue:

Вывод данных:

The queue myqueue is :            2           4             6            8
myqueue.size() : 4
myqueue.front() : 2
myqueue.back() : 8
myqueue.pop() :        4            6            8

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

Итог

На этом мы подошли к концу данной статьи по стекам и очередям. Как уже было сказано, это самые простые контейнеры, которые есть в STL. Другой вариант контейнера очереди известен как «Приоритетная очередь».

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

С Уважением, МониторБанк

Добавить комментарий