Читайте также:
|
Очередь – структура данных с двусторонним доступом, хранящая последовательность значений, для которой определены следующие операции:
-очистить очередь (сделать структуру пустой);
-проверить на пустоту;
-добавить элемент в конец;
-взять элемент в начале;
-прочитать первый элемент;
-записать последний элемент.
Операции похожи на те, что были описаны в стеке. Отличие лишь в том, что добавление элемента происходит в конец очереди, а удаление – из ее начала. Структура данных очередь полностью аналогична обыденному пониманию этого слова. Когда человек занимает очередь в магазине, он становится в конец очереди, так и элемент добавляемый в очередь дописывается в ее конец. Когда приходит очередь брать товар, человек берет товар и уходит, так и при извлечении элемент берется из начала очереди.
Про очередь говорят, что она работает по принципу FIFO (First in – first out; первым пришел – первым ушел).
При хранении в массиве уже не хватит двух переменных, как этого было достаточно для стека. Можно обойтись тремя переменными. Безусловно, нужен массив для хранения содержимого очереди. Этот массив будет «свернут в кольцо», то есть элементом следующим за последним элементом массива будет считаться первый элемент массива. Помимо массива можно завести переменные для хранения начала и конца очереди. Но тут встает вопрос, как определить пустоту очереди и ее переполненность (когда все элементы массива заняты очередью, добавление становится невозможным – возникает переполнение). Очередь будет считаться пустой, когда индекс начала на единицу больше индекса конца, но то же самое будет и при очереди, заполнившей весь массив!!!
Для списочного хранения очереди потребуется еще один указатель – на конец очереди. Очередь будет храниться в виде двусвязного списка. Очередь из элементов 7 и 10 будет представлена так:
Деки
Дек – структура данных с двусторонним доступом, хранящая упорядоченное множество значений, для которой определены следующие операции:
-очистить дек (сделать структуру пустой);
-проверить на пустоту;
-добавить элемент в начало;
-добавить элемент в конец;
-взять элемент из начала;
-взять элемент из конца;
-прочитать первый элемент;
-прочитать последний элемент;
-записать первый элемент;
-записать последний элемент.
Как видно, дек содержит операции, описанные выше для стека и очереди. Для представления дека используются те же наборы переменных, что и для очереди.
Наглядно дек можно представить в виде полки с книгами, которые можно доставать и помещать с двух сторон, но нельзя брать и ставить в середине полки.
11)Способы передачи переменных в с++(по значению,по ссылке,по указателю).
Дата добавления: 2015-01-05; просмотров: 112 | Поможем написать вашу работу | Нарушение авторских прав |
|