МЕНЮ
Гостевая книга
Форум
КАК ОРГАНИЗОВАТЬ ОЧЕРЕДЬ
Что такое очередь? Очередь (в нашем привычном понимании) - это толпа
людей, стоящих друг за другом, ожидающих купить какую-нибудь крутую
вещь. И в компьютере очередь - это тоже толпа данных, стоящих
друг за другом. В отличие от стека, в котором кто последний зашел,
тот первый вышел - в очереди все наоборот - кто первый зашел - тот
и выйдет первым - ему не придется ждать остальных. А вот кто зашел
последним - тот и выйдет последним - ему придется подождать, пока
выйдут остальные.
Если мы положим в очередь числа 3,4,5, то получится что-то вроде такого:
И выйдут они, соответственно, так же - 3,4,5. Как зашли, так и выйдут
Как вы понимаете, очередь тоже поддерживает две операции - PUSH и POP -
положить в очередь и достать из очереди. Но тут есть проблема -
в человеческой очереди когда человек сделал "то, за чем он в очереди",
то есть купил товар и ушел - очередь сдвигается за ним и становится
на его место. Это конечно можно сделать и на компьютере, но это
ДОЛГО. Сдвигать очередь после извлечения каждого числа это очень
медленно.
Но ведь если не сдвигать - и первый, и последний элемент очереди
будут постепенно сдвигаться все дальше и дальше? Вот смотрите:
Поместили в очередь элемент 1 - он на первом месте
Поместили в очередь элемент 2 - он на втором месте
Поместили в очередь элемент 3 - он на третьем месте
Удалили элемент из очереди. Какой? Первый пришедший - то есть элемент 1. У нас первое место освободилось, а 2 и 3 заняты.
Удалили элемент из очереди. Какой? Следующий пришедший - то есть элемент 2. У нас второе место освободилось, а третье занято.
Видите - у нас уже первые два места пусты. А заполнятся ли они еще? Нет!
Ведь если мы будем удалять элементы из очереди - они дадут только еще больше
пустых элементов. А если добавлять - они добавятся в конец очереди - то есть
на места 4,5,6,..., но на места 1 и 2 не встанут.
А если мы захотим миллиард раз добавить и удалить один элемент? Очередь
будет настолько сдвинута вправо, что никакой памяти не хватит! Что же делать?
Все очень просто! Нужно закольцевать очередь! То есть если мы добавляем
элемент в очередь - а места в очереди нет - то новый элемент становится
в начало очереди (но мы конечно помним что он вовсе не первый, хоть и
в начале). А если наоборот - мы доудаляли элементы до конца - то также
переходим в начало и начинаем удалять оттуда.
Пример: Очередь размером 3 элемента
Поместили в очередь элемент 1 - он на первом месте
Поместили в очередь элемент 2 - он на втором месте
Поместили в очередь элемент 3 - он на третьем месте
Удалили элемент из очереди. Какой? Первый пришедший - то есть элемент 1. У нас первое место освободилось, а 2 и 3 заняты.
Удалили элемент из очереди. Какой? Следующий пришедший - то есть элемент 2. У нас второе место освободилось, а третье занято.
Поместили в очередь элемент 4 - он на первом месте. Почему? Потому что должен бы быть на четвертом. Но в очереди всего 3 элемента - значит он перемещается в начало - на место уже удаленных элементов. Теперь у нас есть элемент на месте 3, а за ним элемент на месте 1.
Удалили элемент из очереди. Какой? Следующий пришедший - то есть элемент 3. Освободилось третье место, но осталось первое.
Удалили элемент из очереди. Какой? Следующий пришедший - то есть элемент 1. Все. Очередь пуста. Но! Обратите внимание что хоть она и пуста - следующий элемент будет сразу вторым - так как считается, что первый мы удалили и туда никто встать не может (пока очередь опять не переполнится).
Теперь собственно должно стать понятно как реализовать очередь. У нас должно быть два указателя - один на начало очереди (на элемент который уйдет следующим) - "голова", другой на конец очереди (элемент, который уйдет последним) - "хвост".
Чтобы поместить элемент в очередь - нужно увеличить хвост. Если он вышел за границы очереди - поместить его снова в начало. И поместить элемент на новое место
Чтобы удалить элемент из очереди - нужно взять элемент, на который указывает голова, а далее УВЕЛИЧИТЬ голову (обратите внимание - все только увеличивается). Если она тоже вышла за границы очереди - тоже передвинуть в начало.