Ссылочная реализация очереди с помощью циклического списка

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

Рис.2.8. Реализация очереди на основе циклического списка

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

Очереди с приоритетами

В реальных задачах часто возникает необходимость организации очередей, принцип работы которых отличен от FIFO. Порядок выборки элементов в них определяется приоритетами элементов. Приоритет — это некоторое числовое значение, связанное с элементами очереди, в простейшем случае, это может быть само значение элемента. При выборке элемента из очереди каждый раз выбирается элемент с наибольшим приоритетом.

Различают два способа реализации очередей с приоритетами.

1. Очереди с приоритетным включением. В этом случае очередь всё время поддерживается упорядоченной, т.е. каждый новый элемент помещается в то место очереди, которое определяется его приоритетом.

2. Очереди с приоритетным исключением. Новые элементы помещаются в конец очереди, при исключении элемента отыскивается элемент с максимальным приоритетом.

Реализация очередей с приоритетами на базе отсортированных массивов или списков используется при небольшом количестве элементов такой очереди. При небольшом количестве приоритетов может использоваться так называемый корзинный способ. Наиболее удобной формой реализации больших очередей с приоритетами является реализация с помощью частично упорядоченных деревьев.

Пример программы с использованием очереди

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

Пример. Лабиринт представляет собой клетчатое поле NxM клеток, некоторые из них пустые, другие закрашены - через них проходить нельзя. За один шаг можно перейти из текущей клетки в одну из свободных соседних. Требуется найти длину кратчайший путь из левого верхнего угла в правый нижний. Лабиринт считывается из текстового файла input. txt, где в первой строке записаны числа N и M (через пробел), а в каждой из последующих N строк находятся M символов информации о клетках лабиринта. При этом символ пробела обозначает пустую клетку, символ 'x' - закрашенную. Результат работы программы выводится на экран.

Идея решения состоит в следующем («метод волны»). Для начала определим тип элементов очереди как структуру из трёх полей — координаты клетки и число шагов до неё от левого верхнего угла:

struct cell

{ int x,y,l;

};

typedef cell type_of_data;

После чтения информации о лабиринте создаем очередь и помещаем в нее первый элемент с координатами левого верхнего угла и числом шагов 0.

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

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

 

#include <fstream.h>

#include "queue.h"

main() {

ifstream fi("input.txt");

int N,M;

fi>>N>>M; fi.get(); //Считывание размеров лабиринта

char s[100]; int a[10][10], i, j;

for (i=0; i<N; i++) { //Чтение информации о клетках

fi.getline(s,100);

for (j=0; j<M; j++) {

    if (s[j]=='.') a[i][j]=0;

    else a[i][j]=1;

}

}

queue q; // Очередь абсцисс, ординат и длин путей

cell c;

// Заносим в очередь первую клетку:

c.x=0; c.y=0; c.l=0; q.enqueue(c);

int len;

while (!q.isnull())

{c=q.gethead(); q.dequeue();

i=c.y; j=c.x; len=c.l;

if ((i==N-1)&&(j==M-1)) break; // Путь найден

// Проверяем соседние с (i,j) клетки:

 c.l++; //увеличиваем путь на 1

if((i>0)&&(!a[i-1][j])){c.y--; q.enqueue(c); c.y++;}

if((i<N-1)&&(!a[i+1][j])){c.y++;q.enqueue(c);c.y--;}

if((j>0)&&(!a[i][j-1])){c.x--; q.enqueue(c); c.x++;}

if((j<M-1)&&(!a[i][j+1])){c.x++;q.enqueue(c);c.x--;}

a[i][j]=1;

}

if((i==N-1)&&(j==M-1))cout<<"Длина кратч. пути"<<len;

else {

q.makenull();

cout<<"Путь в лабиринте не найден.";

}

cin.get(); return 0;

}

 

Стеки и очереди являются частными случаями более универсальной структуры данных— линейных списков.