Прикладное программирование

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
// Университет ИТМО
/////////////////////////////////////////////////////////////////////////////
#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
// Университет ИТМО
/////////////////////////////////////////////////////////////////////////////
#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)