Стеки и очереди — это два контейнера в 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(), то следующий элемент (в данном случае 1) будет удален, что приведет к пустому стеку:
- top: возвращает самый верхний элемент стека.
- empty: проверяет, пуст стек или нет.
- size: возвращает размер стека, т.е. количество элементов в стеке.
Ниже приведен пример реализации стека для лучшего понимания операций:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <stack> using namespace std; void printStack(stack <int> stk) { while (!stk.empty()) { cout << '\t' << stk.top(); stk.pop(); } cout << '\n'; } int main () { stack <int> oddstk; oddstk.push(1); oddstk.push(3); oddstk.push(5); oddstk.push(7); oddstk.push(9); cout << "The stack is : "; printStack(oddstk); cout << "\nSize of stack: " << oddstk.size(); cout << "\nTop of stack: " << oddstk.top(); cout << "\noddstk.pop() : "; oddstk.pop(); printStack(oddstk); cout<<"\nAnother pop(): "; oddstk.pop(); printStack(oddstk); return 0; } |
Вывод данных:
|
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, которая создает стек. Она также показывает стек после двух последовательных операций извлечения.
Таким образом, вы увидели стек и его операции в 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)».
Теперь очередь выглядит так, как показано ниже:
Как видно выше, элементы помещаются в очередь сзади.
Теперь давайте выполним операцию с myqueue.
| myqueue.pop(); |
Итак, как мы видим, при вызове pop() элемент в начале очереди удаляется. Это означает, что первый элемент, входящий в очередь, является первым элементом, который выходит из очереди.
- front: эта функция возвращает ссылку на первый элемент очереди.
- back: back возвращает ссылку на последний элемент в очереди.
- empty: проверяет, пуста ли очередь.
- size: возвращает размер очереди, т.е. количество элементов в очереди.
Ниже приведен пример программы, демонстрирующий операции, используемые контейнером queue:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <queue> using namespace std; void printQueue(queue <int> myqueue) { queue <int> secqueue = myqueue; while (!secqueue.empty()) { cout << '\t' << secqueue.front(); secqueue.pop(); } cout << '\n'; } int main() { queue <int> myqueue; myqueue.push(2); myqueue.push(4); myqueue.push(6); myqueue.push(8); cout << "The queue myqueue is : "; printQueue(myqueue); cout << "\nmyqueue.size() : " << myqueue.size(); cout << "\nmyqueue.front() : " << myqueue.front(); cout << "\nmyqueue.back() : " << myqueue.back(); cout << "\nmyqueue.pop() : "; myqueue.pop(); printQueue(myqueue); return 0; } |
Вывод данных:
| 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.
С Уважением, МониторБанк