Главная » C++, C++ Builder » Стеки и очереди STL

0

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

STL   предлагает   вам   готовую   реализацию   и   стека,   и   очереди.   Стек   является   как   бы

«односторонней» очередью, то есть вы можете помещать (push) элементы на верхушку стека и брать (pop) элементы с верхушки стека.  С другой стороны, очереди позволяют добавлять элементы в начало списка («голова» очереди)и забирать элементы с другого конца («хвост» очереди). Стек часто называют структурой вида LIFO (Last In First Out), так как элемент, добавленный последним в стек командой push, будет являться первым, извлеченным из стека командой pop. Соответственно, очередь — это структура FIFO (First In First Out): элемент, добавленный в очередь первым, будет первым же из нее и извлечен.

В C++ стек и очередь обычно реализуются в виде связного списка. Многие программисты на заре своего обучения программированию писали такие структуры, так что подробно рассматривать их в данной книге мы  не будем. Используя реализацию, предложенную в STL, вы получаете два преимущества перед своим собственным стеком (или очередью), основанным на связном списке. Во-первых, код в STL тщательно проверялся и поэтому скорее всего будет работать без ошибок. Даже если в нем и найдется ошибка, то она будет исправлена, и новая версия библиотеки будет бесплатно распространена и интегрирована в разнообразные среды разработки (включая Borland CBuilder). Во-вторых (что более важно), внутренняя структура данных может измениться в STL, но при этом прототипы функций останутся такими же, так что вы можете спокойно писать программу, использующую стек или очередь, не беспокоясь о том, что в будущем их внутренняя реализация может измениться.

Давайте рассмотрим, что за методы есть у классов stack (стек) и queue (очередь), а затем немного поговорим об их использовании. В табл. 5.6 приведены основные методы класса stack в STL.

Таблица 5.6 Важные методы класса stack

empty

Указывает, есть ли элементы(FALSE) или нет (TRUE) в стеке

size

Возвращает количество элементов в стеке

top

Возвращает элемент с верхушки стека, но не удаляет его

push

Добавляет элемент на верхушку стека (или очереди)

pop

Забирает верхний элемент из стека (очереди)

front

Возвращает элемент, находящийся в голове очереди, не удаляя его

back

Возвращает элемент, находящийся в хвосте очереди (добавленный последним), не удаляя его

operator=

Копирует стек или очередь в объект такого же типа

constructor

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

Как вы видите из предыдущей таблицы, стек и очередь  не  являются  самостоятельными структурами данных в STL, а строятся на других структурах, таких как список и дек <$FДек (deque) — это внебрачный потомок стека и очереди, то есть структура, в которой можно добавлять элементы как в начало, так и в конец списка, и соответственно забирать их с любой стороны. Дек является классическим примером, когда удобно применять множественное наследование в языке C++. — Примеч. перев.>(deque), которым вполне хватает функциональности для реализации таких вещей.

Одно важное замечание относительно стека и очереди: для этих структур нет понятия итератора. Вы не можете использовать итератор, чтобы ходить по стеку или очереди, вам вместо это нужно использовать методы push и pop для добавления и удаления элементов.

Давайте посмотрим на простенький пример программы, использующей стек.

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stack>

#include <string>

#include <list>

int main(int argc, char **argv)

{

std::stack< std::string, std::list<std::string> > stringStack;

// Запихать все аргументы командной строки в стек

for  (int i=1; i<argc; ++i)

{

stringStack.push(argv[i]);

}

// Теперь вынуть в обратном порядке

while  (!stringStack.empty() )

{

std::string s = stringStack.top(); printf("%s\n", s.c_str() ); stringStack.pop();

}

return 0;

}

Как видите, программа просто берет набор аргументов командной строки и печатает их в обратном порядке. Так что, если вы запустите программу следующей командой  (в  командной строке окна MS-DOS в Windows 95 или NT):

stktest Hello world how are you?

разумеется, если вы сохранили проект как stktest, то вы увидите следующий вывод программы: you?

are how world Hello

Заметьте, что процесс удаления элемента из стека состоит из двух шагов. Во-первых, получить элемент, используя метод top класса stack (который возвращает элемент, не удаляя его при этом), а уже затем удалить элемент из стека методом pop. В отличие от удаления, добавление (метод push) происходит за один шаг.

Замечание про двойные угловые скобки: вы, наверное, заметили, что при описании объектов, использующих STL, частенько приходится писать конструкции, в которых попадается подряд несколько угловых скобок (>). Пример — объект класса stack, для которого требуется второй параметр, тоже шаблонный класс. В результате вы напишете что-нибудь такое:

std::stack< std::string, std::list<std::string>>  stringStack;

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

Источник: Теллес М. – Borland C++ Builder. Библиотека программиста – 1998

По теме:

  • Комментарии