Инструменты пользователя

Инструменты сайта


examination:ccc:question4

Вопрос №4. Динамические типы данных. Списки (очереди)

Очередь - структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется.

При организации очереди необходимо хранить адрес ее первого и последнего элемента. 0↔0↔0↔ В начальный момент времени, когда очередь пуста, оба этих указателя пусты. При добавлении первого элемента оба указателя начинают ссылаться на него, при добавлении всех последующих указатель в последнем элементе начинает ссылать на новый добавленный элемент и этот элемент помечается последним. Удаление из очереди происходит с начала, при этом элемент, на который ссылается начало очереди, становится новым началом. Очередь, в которой каждый элемент ссылается только на одного соседа, называется односвязной. Очередь, в которой каждый элемент ссылается на обоих соседов, называется двусвязной.

Применение очередей

Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие

examination/ccc/question4.txt · Последние изменения: 2014/01/15 12:13 (внешнее изменение)