Стеки і черги STL

Напевно, жодна структура даних не застосовується в компютерній індустрії так широко, як стек Операційні системи побудовані на цій простій структурі даних, і напевно кожен програміст неодноразово отримував радісне повідомлення про переповнення стека в своїй програмі

STL пропонує вам готову реалізацію і стека, і черги Стек є як би

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

У C + + стек і черга зазвичай реалізуються у вигляді звязного списку Багато програмістів на зорі свого навчання програмуванню писали такі структури, так що докладно розглядати їх в даній книзі ми не будемо Використовуючи реалізацію, запропоновану в STL, ви отримуєте дві переваги перед своїм власним стеком (або чергою), заснованим на звязковому списку По-перше, код в STL ретельно перевірявся і тому швидше за все буде працювати без помилок Навіть якщо в ньому і знайдеться помилка, то вона буде виправлена, і нова версія бібліотеки буде безкоштовно поширена і інтегрована в різноманітні середовища розробки (включаючи Borland CBuilder) По-друге (що більш важливо), внутрішня структура даних може змінитися в STL, але при цьому прототипи функцій залишаться такими ж, так що ви можете спокійно писати програму, що використовує стек або черга, не турбуючись про те, що в майбутньому їх внутрішня реалізація може змінитися

Давайте розглянемо, що за методи є у класів stack (стек) і queue (черга), а потім трохи поговоримо про їх використання У табл 56 наведені основні методи класу stack в STL

Таблиця 56 Важливі методи класу stack

Вказує, чи є елементи (FALSE) чи ні (TRUE) у стеку

Повертає кількість елементів в стеку

Повертає елемент з верхівки стека, але не видаляє його

Додає елемент на верхівку стека (або черги)

Забирає верхній елемент з стека (черги)

Повертає елемент, що знаходиться в голові черзі, не видаляючи його

Повертає елемент, що знаходиться в хвості черги (доданий останнім), але залишити його

Копіює стек або черга в обєкт такого ж типу

Дозволяє програмісту вказати тип даних, що містяться в стеку (черги) і структуру, що використовується для зберігання елементів

Як ви бачите з попередньої таблиці, стек і черга не є самостійними структурами даних в STL, а будуються на інших структурах, таких як список і дек <$ FДек (deque) - це позашлюбний нащадок стека і черги, тобто структура, в якій можна додавати елементи як на початок, так і в кінець списку, і відповідно забирати їх з будь-якого боку. Грудень є класичним прикладом, коли зручно застосовувати множинне спадкування в мові C + +. - Прямуючи. перев.> (deque), яким цілком вистачає функціональності для реалізації таких речей

Одне важливе зауваження щодо стека і черги: для цих структур немає поняття ітератора Ви не можете використовувати ітератор, щоб ходити по стеку або черги, вам замість це потрібно використовувати методи push і pop додавання та видалення елементів

Давайте подивимося на простенький приклад програми, що використовує стек

#include &ltstdioh&gt

#include &ltstringh&gt

#include &ltstdlibh&gt

#include &ltstack&gt

#include &ltstring&gt

#include &ltlist&gt

int main(int argc, char **argv)

{

std::stack&lt std::string, std::list&ltstd::string&gt &gt stringStack

/ / Запхати всі аргументи командного рядка в стек

for  (int i=1 i&ltargc ++i)

{

stringStackpush(argv[i])

}

/ / Тепер вийняти в зворотному порядку

while  (stringStackempty() )

{

std::string s = stringStacktop() printf(&quot%s\n&quot, sc_str() ) stringStackpop()

}

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&lt std::string, std::list&ltstd::string&gt&gt  stringStack

Ніколи так не робіть Зївши такий рядок, компілятор поскаржиться на цілу купу помилок і видасть вам гору імен Проблема в тому, що в мові C (і, відповідно, C + +) символ >> є оператором зсуву вправо Коли у вас виходять дивні помилки в коді з шаблонами, перевірте, що у вас між двома кутовими дужками поставлені прогалини Це все говорить про помилку (принаймні, недоробку) в дизайні системи шаблонів в C + +, а не про помилку в компіляторі

Джерело: Теллес М – Borland C + + Builder Бібліотека програміста – 1998

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*