Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Пример 1. Hиже приводится пример программы, заносящей в очередь 10 символов, набранных на клавиатуре пользователем
|
|
Hиже приводится пример программы, заносящей в очередь 10 символов, набранных на клавиатуре пользователем, и выдающей их на экран в той же последовательности. В ней используются следующие процедуры:
- процедура AddEl(val: real) используется для добавления к очереди нового элемента val;
- процедура GetDelEl(var val: real) используется для удаления из очереди элемента val.
Program queue; Type Tptr=^TElem; {Тип указателя на элемент очереди } TElem= record { Тип элемента очереди: } inf: char; { информационная часть } link: Tptr { соединительная часть } end; Var begq, endq: Tptr; { Указатели на начало и конец очереди } value: char; i: byte; Procedure AddEl(val: char); { Процедура добавления элемента } Var p: tptr; { Вспомогательный указатель } begin new (p); p^.inf: =val; p^.link: =nil; if endq= nil then begq: =p else endq^.link: =p; endq: =p end; Procedure GetDelEl(var val: char); { Процедура удаления элемента } var p: TPtr; { Вспомогательный указатель } begin val: =begq^.inf; p: =begq; begq: =p^.link; if begq= nil then endq: =nil; dispose (p) end; begin new (begq); { Создание указателей на начало и конец очереди } new (endq); begq: = nil; { Установление указателей на nil } endq: = nil; for i: =1 to 10 do begin writeln (' введите символ'); readln (value); addel(value); end; i: =1; while begq< > nil do begin getdelel(value); writeln (i, '-й символ - ', value); inc(i) endend.
Пример 2. Сформировать две очереди по 5 элементов. Объединить очереди в одну, в которой элементы исходных очередей чередуются (начиная с первого элемента первой очереди).
Дек
Дональд Кнут ввел понятие усложненной очереди, которая называется дек (от англ. deq - double ended queue, т.е. очередь с двумя концами).
Определение: Дек - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка.
В каждый момент времени у дека доступны как первый, так и последний элемент, причем добавлять и удалять элементы можно и в начале, и в конце дека.
Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.
Дек удобнее представлять двусвязным (разнонаправленным) линейным списком.
Операции над деком:
- включение элемента справа;
- включение элемента слева;
- исключение элемента справа;
- исключение элемента слева;
- определение размера;
- очистка.
Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.
Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Как правило, вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки.
Примером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.
|
|