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

Начнём рассмотрение этих структур данных с наиболее простых, т.е. с очередей.


1. Очереди

В общем случае, очередь – это линейный список, доступ к элементам которого происходит по принципу F I F O (First In and First Out – первым пришел и первым ушел).


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


Области применения очередей могут быть разделены на две группы – системное применение и прикладное. К применению очередей в системных целях относятся:

Прикладное применение:


Одним из примеров очереди является машина Тьюринга. Более простым механическим примером является труба с текущей только в одном направлении жидкостью.


Классификация очередей. По архитектуре очереди делятся на линейные и кольцевые (циклические). По количеству позиций записи и считывания – на простые и приоритетные. Кроме того существует специальный вид очереди – двухвходовая очередь или дек (DEQue – Double Ended Queue; queue – очередь).


На практике очереди могут реализовываться при помощи одномерных массивов или свЯзных списков, что хорошо иллюстрирует различие между логическим и физическим уровнями структур данных (массив на физическом уровне является очередью на логическом).


Ниже приведёны примеры процедур занесения и извлечения для линейной очереди на языках Паскаль и Си++.


Программа работы с линейной очередью на языке Паскаль

Programm Queue_Test;
var
 q:array[0..30] of Integer; (* Глобальный массив, на котором и строится очередь *)

 qnext, (* Индекс занесения *)
  qindex, (* Индекс извлечения *)
  qlength:Integer; (* Длина очереди *)

procedure qstore(i:Integer); (* Процедура записи в очерель *)
begin
 if (qnext+1)<qlength then
 begin
  qnext:=qnext+1;
  q[qnext]:=i
 end
 else
  writeln('Мест нет')
end;

function qretrieve():Integer; (* Функция считывания из очереди *)
begin
 if qindex=qnext then
 begin
  writeln('Очередь пуста');
  qretrieve:=0;
 end
 else
 begin
  qindex:=qindex+1;
  qretrieve:=q[qindex]
 end;
end;

Функция qretrieve() извлекает из очереди первый элемент; хранившиеся в этом элементе данные "разрушаются". Если из очереди удалены все элементы, она становится пустой. На самом деле qretrieve() в этом примере не разрушает информацию, но информацию можно считать удаленной, так как дальнейший доступ к ней невозможен.


Программа с результатами её выполнения

begin   Содержимое очереди
qlength:=30;      
qnext:=0;
qindex:=0;
qstore(1);1
qstore(2);2 1
qstore(3);3 2 1
qretrieve();{возвращает 1}      3 2
qstore(4);4 3 2
qretrieve();{возвращает 2}4 3
qretrieve();{возвращает 3}4
qretrieve();{возвращает 4}Очередь пуста
end.

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



Аналогичная программа на языке Си++

#include <iostream>
using namespace std;

int q[30];
int qnext=0,qindex=0,qlength=30;

// Занесение элемента в очередь.
void Insert(int i)
{
 if(qnext+1 == qlength)
 {
  cout << "Мест нет!\n";
  return;
 }
 qnext++; // Смещение позиции записи
 q[qnext]=i; // Ввод данных
}

// Извлечение элемента из очереди.
int Retrieve()
{
 if(qindex == qnext)
  {
  cout<<"Очередь пуста.\n";
  return 0;
 }
 qindex++; // Смещение позиции считывания
 return q[qindex]; // Считывание
}

int main()Результат  Содержимое очереди
{
 Insert(1);  1
 Insert(2);  2 1
 Insert(3);  3 2 1
 cout<<Retrieve()<<endl;// Возвр. 1  3 2
 Insert(4);  4 3 2
 cout<<Retrieve()<<'\n';// Возвр. 2  4 3
 cout<<Retrieve()<<endl;// Возвр. 3  4
 return 0;
}

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


Кольцевая очередь

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


Программа работы с кольцевой очередью на языке Паскаль

Programm Queue_Test2;
var
 q:array[0..30] of Integer;
 qnext,qindex,qlength:Integer;

procedure qstore(i:Integer);
begin
 if (qnext+1)<>qlength then
 begin
  q[qnext]:=i;
  qnext:=qnext+1;
  if qnext=qlength then
   qnext:=0        (* Циклический переход *)
 end
 else
  writeln('Мест нет')
end;

function qretrieve():Integer;
begin
 if qindex=qlength then
  qindex:=0;        (* Циклический переход *)
 if qindex=qnext then
 begin
  writeln('Очередь пуста');
  qretrieve:=0;
 end
 else
 begin
  qretrieve:=q[qindex];
  qindex:=qindex+1
 end;
end;

Индексы сохранения qnext и извлечения qindex циклически возвращаются к началу массива (т.е. к 0). В такую очередь можно поместить любое количество элементов (если они не только помещаются, но и извлекаются из очереди).


Если qindex на 1 больше qnext – очередь заполнена и запись новых элементов невозможна, пока не будут прочитаны элементы, хранящиеся в очереди в данный момент. Если qindex равен qnext – очередь пуста. В остальных случаях существует место для помещения по крайней мере еще одного элемента.


begin   Содержимое очереди
qlength:=30;      
qnext:=0;
qindex:=0;
qstore(1);1
qstore(2);2 1
qstore(3);3 2 1
qretrieve();{возвращает 1}      3 2
qstore(4);4 3 2
qretrieve();{возвращает 2}4 3
qretrieve();{возвращает 3}4
qretrieve();{возвращает 4}Очередь пуста
end.

Аналогичная программа на языке Си++

// Циклическая очередь.
// Занесение элемента в очередь.
void Insert_c(int i)
{
 if(qnext+1 == qindex || (qnext+1 == qlength && !qindex))
 {
  cout<<"Мест нет!\n";
  return;
 }
 q[qnext]=i; // Запись
 qnext++; // Смещение позиции записи
 if(qnext==qlength)
  qnext=0; // Циклический переход.
}

// Извлечение элемента из очереди.
int Retrieve_c()
{
 if(qindex == qlength)
  qindex=0; // Циклический переход.
 if(qindex == qnext)
 {
  cout<<"Очередь пуста.\n";
  return 0;
 }
 qindex++; // Смещение позиции считывания
 return q[qindex-1]; // Считывание
}

Более короткие варианты этих же процедур

const int maxN=15;
int N=maxN+1,head=N,tail=0; // размер, "голова" и "хвост"
int q[maxN+1]; // Очередь

void Ins(int i)
{
  q[tail++]=i; // Смещение и запись
  tail=tail%N; // Циклический переход
}

int Ret()
{
  head=head%N; // Циклический переход
  return q[head++]; // Смещение и чтение
}

Именно кольцевая очередь используется на практике, в том числе в качестве буферной памяти клавиатуры. Часто при зацикливании программ в операционных системах MS-DOS или Windows вводимые с клавиатуры и поступающие в её буфер данные не считываются из этого буфера – очередь переполняется. Индикацией этого события является звуковой сигнал.


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


Приоритетная очередь

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


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


Дек

Дек или двухвходовая очередь отличается от обычной очереди тем, что данные в такой очереди могут "перемещаться" (физически или виртуально) в обоих направлениях; "голова" дека одновременно является его "концом" и наоборот.


Контрольные вопросы


1. Что представляет собой очередь?
2. Какие известны виды очередей?
3. На основе каких структур данных могут организовываться очереди?
4. Какой характер имеет операция считывания для очередей?
5. Какими свойствами обладают очереди?
6. Каким недостатком обладает простая очередь? Каков способ борьбы с этим недостатком?
7. Чем отличается приоритетная очередь от простой?
8. К каким структурам данных относятся очереди?
9. Что представляет собой дек?
10. Какой метод доступа к элементам используется в очередях? Опишите особенности этого метода.
11. Какие операции над элементами характерны для очередей?
12. Перечислите основные отличия очереди от массива.
13. Для решения каких задач применяются очереди?
14. В чем преимущества циклической очереди? Чем она отличается от простой очереди?
15. К каким позициям очереди возможен доступ при записи и чтении информации?


Тест для самопроверки

< Назад | Вперед >

Хостинг от uCoz