Очередь

← →
default © (2006-10-09 15:21) [0]

во всех источниках в которых написано про реализацию очереди оперируют понятиями голова очереди и хвост очереди
это порождает проблему состоящую в том, что одним и тем же значениям головы и хвоста очереди может соответствовать как пустая очередь так и полностью заполненная
обо всём этом можно прочитать по ссылке
http://www.webfile.ru/1142965
но если оперировать понятиями голова очереди и длина очереди(что вполне ествественно) проблема неоднозначности не возникает
почему не используют нигде в литературе этот подход и говорят о высосанной из пальца проблеме?
вот пример(по аналогии с примером приведённом по ссылке)
type QUEUE = record elements: array[1..maxlength] of elementtype; front, length: integer; end; function addone ( i: integer ): integer; begin return((i mod maxlength) + 1) end; { addone } procedure MAKENULL ( var Q: QUEUE ); begin Q.front:= 1; Q.length:= 0 end; function FRONT ( var Q: QUEUE ); begin if Q.length = 0 then error("Очередь пустая") else return(Q.elements[Q.front]) end; procedure ENQUEUE ( x: elementtype; var Q: QUEUE ); begin if Q.length = maxlength then error("Очередь полная") else begin Q.elements[addone(Q.front+Q.length-1)]:= x; Inc(Q.length) end; end; procedure DEQUEUE ( var Q: QUEUE ); begin if Q.length = 0 then error("Очередь пустая") else Q.front:= addone(Q.front) end;

← →
Сергей М. © (2006-10-09 15:28) [1]

> голова очереди и хвост очереди
> это порождает проблему

Это не порождает никаких проблем.

← →
default © (2006-10-09 15:29) [2]

Сергей М. © (09.10.06 15:28) [1]
прочитайте по ссылке сначала

← →
Сергей М. © (2006-10-09 15:31) [3]

зачем читать то что высосано из пальца ?

← →
Sandman29 © (2006-10-09 15:38) [4]

default © (09.10.06 15:21)

Там очередь реализована не массивом, а списком (динамической структурой). Длина очереди не поможет быстро перейти к ее концу. Совсем не поможет.

← →
default © (2006-10-09 15:39) [5]

Сергей М. © (09.10.06 15:31) [3]
то есть Вы мне на слово верите не хотите для начала понять в чём там дело прочитав по ссылке?:)

← →
default © (2006-10-09 15:39) [6]

Sandman29 © (09.10.06 15:38) [4]
массивом там реализована, читайте внимательнее!!!

← →
Сергей М. © (2006-10-09 15:41) [7]

> default © (09.10.06 15:39) [5]
>
> Сергей М. © (09.10.06 15:31) [3]
> не хотите

Не хочу.
Потому что никакой проблемы не существует.

← →
default © (2006-10-09 15:42) [8]

Sandman29 © (09.10.06 15:38) [4]
не будем пока трогать динамические очереди, будем смотреть что написано по ссылке и что написал я, пока речь только об этом
хотя с динамическими очередями никаких проблем нет...всё то же самое почти что...

← →
Игорь Шевченко © (2006-10-09 15:46) [9]

default © (09.10.06 15:21)

Источник в студию.

← →
default © (2006-10-09 15:48) [10]

"Структуры данных и алгоритмы"
Ахо, Хопкрофт, Ульман

← →
Sandman29 © (2006-10-09 15:48) [11]

default © (09.10.06 15:42) [8]

Я загрузил, почитал первые 2 странички, наткнулся на картинку с динамическими очередями. Разбирать глюки реализации динамической очереди статическим массивом у меня нет желания :)

← →
default © (2006-10-09 15:51) [12]

Sandman29 © (09.10.06 15:48) [11]
нету там никаких глюков
от того примера к динамическим очередям перейти очень просто

← →
sniknik © (2006-10-09 15:57) [13]

> одним и тем же значениям головы и хвоста очереди может соответствовать как пустая очередь так и полностью заполненная
такого не бывает, буфер клавиатуры в dos был таким образом реализован, и ничего неоднозначного там не было, одинаковые значения головы и хвоста означали чтото одно (пустоту или заполненность), второе состояние характеризовалось тем что значения рядом, т.е. "хвост" прежде чем сдвигаться проверял "а не на ту же позицию сдвиг на котором голова?", если на ту то переполнение.
(могу ошибиться, возможно было наоборот, но там все было очень логично и оптимально для работы... надо смотреть если захочется подробностей)

sniknik © (09.10.06 15:57) [13]
всё-таки хотелось бы чтобы Вы сначала по ссылке прочитали
по ссылке проблема неоднозначности решается использованием для элементов очереди maxlength-1 элемент массива
(вводить дополнительные переменные не стали)
вообщем там всё написано это...

>но если оперировать понятиями голова очереди и длина очереди
В абстрактных структурах данных - очередь, стек, список - нет понятия "длина" (хотя она и может быть введена в конкретных реализациях), что позволяет более широко применять обобщенные методы (пример, может и глупый - файл на чтение с Eof как список)

Состояние очереди Empty устанавливается изначально и при операциях извлечения, а Full - только при операции добавления, так что проблем нет.

MBo © (09.10.06 16:05) [15]

> Состояние очереди Empty устанавливается изначально и при
> операциях извлечения, а Full - только при операции добавления,
> так что проблем нет.

проблема есть, по ссылке посмотрите?

> В абстрактных структурах данных - очередь, стек, список
> - нет понятия "длина" (хотя она и может быть введена в конкретных
> реализациях), что позволяет более широко применять обобщенные
> методы (пример, может и глупый - файл на чтение с Eof как
> список)

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

ОК, не сразу тебя понял.
Использование Tail (Rear), думаю, идет по привычке, по аналогии со списками, а твоя реализация для случая массивов кажется вполне разумной.

MBo © (09.10.06 17:53) [17]
вот я тоже кроме привычки причины не вижу
в .NET классе Queue, есть внутренние переменные голова, хвост, размер(то же что и длина очереди)
подумал, что без переменной хвост код был бы менее наглядным/быстрым
посмотрел места где используется переменная хвост - их оказалось очень немного и там можно смело обойтись головой/длиной

вернее не так

> посмотрел места где используется переменная хвост - их оказалось
> очень немного и там можно смело обойтись головой/длиной

-->
мест, где использование голова/длина вместо хвоста идёт с потерей наглядности мало, 2-3

Очередь Найти похожие ветки