3.5. Очереди и стек
3.5.1. Двусторонняя очередь deque (пример 3.5)
Двусторонняя очередь deque - очень похожа на vector: так же как и vector,
она является последовательностью, которая поддерживает произвольный доступ
к элементам. Главное что отличает deque от vector - это то, что deque также
поддерживает вставку и удаление в начало последовательности за постоянное
время. Кроме того, deque не имеет функций-членов аналогичных функциям-членам
vector capacity() и reserve(), и не предоставляет никаких гарантий на допустимость
итератора, который ассоциирован с его функциями-членами.
Пример работы с двусторонней очередью:
/////////////////////////////////////////////////////////////////////////////
// Программирование на языке высокого уровня. Основы языка С++
// Пример 3.5. Пример работы с контейнером deque
//
// http://aco.ifmo.ru/el_books/programming
// Университет ИТМО
/////////////////////////////////////////////////////////////////////////////
#include <iostream> // подключение библиотеки ввода-вывода
#include <deque> // подключение описания deque
#include <iterator> // подключение описания итераторов, нужно для использования ostream_iterator
using namespace std; // подключение стандартного пространства имен для использования библиотек
/////////////////////////////////////////////////////////////////////////////
void main()
{
deque<int> Q; // объявление контейнера
// вставка в конец, Q = 3
Q.push_back(3);
// вставка в начало, Q = 1 3
Q.push_front(1);
// вставка перед 1-м элементом, Q = 1 2 3
Q.insert(Q.begin() + 1, 2);
// изменение второго элемента, Q = 1 2 0
Q[2] = 0;
// вывод всех элементов контейнера при помощи алгоритма copy
copy(Q.begin(), Q.end(), ostream_iterator<int>(cout, " "));
}
///////////////////////////////////////////////////////////////////////////////
Существуют адаптеры очереди (cтек stack и
очередь queue),
которые имеют
методы с одинаковыми именами, но они имеют разное смысловое значение.
3.5.2. Стек stack
Стек stack -- это адаптер очереди, который организует
ее работу по особому правилу: "last in -- first out" (LIFO). Элемент,
который был добавлен последним (push) будет извлечен первым (pop). stack
не предоставляет функция для получения итераторов и их перебора. Можно лишь
проверить, какой элемент находится на вершине стека (top).
Например:
/////////////////////////////////////////////////////////////////////////////
// Программирование на языке высокого уровня. Основы языка С++
// Пример 3.6. Пример работы с контейнером stack
//
// http://aco.ifmo.ru/el_books/programming
// Университет ИТМО
/////////////////////////////////////////////////////////////////////////////
#include <iostream> // подключение библиотеки ввода-вывода
#include <stack> // подключение описания stack
using namespace std; // подключение стандартного пространства имен для использования библиотек
/////////////////////////////////////////////////////////////////////////////
void main()
{
stack<int> s; // объявление контейнера
// добавление в контейнер новых элементов
s.push(8); // s = 8
s.push(7); // s = 7 8
s.push(4); // s = 4 7 8
cout<<s.top()<<endl; // вывод на экран "верхнего" элемента (4)
s.pop(); // удаление из контейнера "верхнего" элемента
cout<<s.top()<<endl; // вывод на экран "верхнего" элемента (7)
s.pop(); // удаление из контейнера "верхнего" элемента
cout<<s.top()<<endl; // вывод на экран "верхнего" элемента (8)
s.pop(); // удаление из контейнера "верхнего" элемента
}
/////////////////////////////////////////////////////////////////////////////
3.5.3. Очередь queue
Очередь queue -- это адаптер очереди, который организует
ее работу по особому правилу: "first in first out" (FIFO). Элемент,
который был добавлен последним (push) будет извлечен последним (pop). queue
не предоставляет функция для получения итераторов и их перебора. Можно лишь
проверить, какой элемент стоит в очереди первым (front).
Изменим предыдущий пример с использование queue:
queue<int> q; // объявление контейнера
// добавление в контейнер новых элементов
q.push(8); // q = 8
q.push(7); // q = 7 8
q.push(4); // q = 4 7 8
cout<<q.front()<<endl; // вывод на экран "переднего" элемента (8)
q.pop(); // удаление из контейнера "переднего" элемента
cout<<q.front()<<endl; // вывод на экран "переднего" элемента (7)
q.pop(); // удаление из контейнера "переднего" элемента
cout<<q.front()<<endl; // вывод на экран "переднего" элемента (4)
|
