Динамические структуры данных – очередь

Очередью называется динамическая структура данных, добавление компонента в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу: FIFO (First-In, First-Out) – первый вошел, первый вышел.

Замечание. В очереди доступны два элемента (две позиции): начало очереди и конец очереди. Поместить компонент можно только в конец очереди, а взять элемент только из ее начала (рис. 4). Примером может служить обыкновенная очередь в магазине.

Рис. 4. Очередь и ее организация.

Обычно над очередью выполняется три операции:

- начальное формирование очереди (запись первого компонента);

- добавление компонента в очередь;

- выборка компонента (удаление) из очереди.

Для формирования очереди и работы с ней необходимо иметь три переменные типа указатель, первая из которых определяет начало очереди (ph), вторая - конец очереди (pk), третья – вспомогательная (px), для добавления нового компонента.

Описание компонента очереди и переменных типа указатель имеет следующий вид:

struct pointer

{

int d;

pointer *p;

};

pointer ph, pk, px;

Рассмотрим основные операции при работе с очередью.

1. Формирование очереди.

Начальное формирование очереди выполняется несколькими операторами, позволяющим записать в очередь первый компонент:

- выделение в динамической памяти места под первый компонент стека и запись адреса этого компонента в переменную ph:

*ph = new pointer;

- запись в поле d некоторых данных – D1:

ph->d = D1;

- запись в поле p нулевого адреса (NULL):

ph->p = NULL;

- установка указателя конца очереди (pk) на первый компонент очереди.

После формирования очереди указатели ph и pk указывают на один и то же компонент.

2. Добавление компонента в очередь.

Добавление компонента в очередь осуществляется с конца очереди, при помощи дополнительного указателя – px:

- выделение в динамической памяти места под новый компонент стека и запись адреса этого компонента в переменную px:

*px = new pointer;

- запись в поле d указателя px некоторых данных – D2:

px->d = D2;

- запись в поле p, указателя px, нулевого адреса:

px->p = NULL;

- запись в поле p указателя pk адреса нового компонента, на который указывает переменная px

pk->p = px;

- запись в указатель pk адреса последнего компонента;

pk = px;

Добавление последующих компонентов осуществляется аналогично.

3. Исключение компонентов из очереди.

Для исключения компонента из очереди необходимо выполнить ряд операторов. Пусть к моменту выборки компонентов, в очередь записано три компонента. Исключение компонентов из очереди осуществляется из ее вершины.

- первый оператор осуществляет чтение данных из компонента – вершины очереди:

data = ph->d;

- смещение указателя на вершину стека (ph) на следующий компонент:

ph =ph->p;

Повторив, указанные выше, два действия мы получим последовательно доступ ко всем компонентам очереди. На практике эти два действия составляют тело цикла с предусловием (цикл while), в котором сначала проверяют условие (ph != NULL), а затем, выполняют исключение компонента из стека.

Рассмотрим реализацию этих операций в виде соответствующих функций.

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

#include <conio.h>

#include <stdio.h>

struct pointer //описание структуры компонента очереди

{

int d;

pointer *p;

};

pointer *formoth(int data); //форм. очереди

void doboth (pointer **pk, int d); //добавление в очередь

int iskoth (pointer **ph); //исключение из очереди

//основная функция

void main()

{

clrscr();

int data;

int i=1;

//формирование очереди

printf("формирование очереди\n");

printf("%d компонент ->",i);

scanf("%d",&data);

pointer *ph = formoth (data); //указатель на начало очереди

pointer *pk = ph; //указатель конца очереди

//добавление в очередь

printf("добавление в очередь\n");

do

{ i++;

printf("%d компонент ->",i);

scanf("%d",&data);

doboth (&pk,data); //добавление компонента

}

while (data !=0); //концом ввода является ноль

printf("вывод очереди на экран:\n");

i=0;

while (ph != NULL)

{

i++;

printf("%d компонент -> %d\n",i,iskoth (&ph));

}

getch();

}

//--------------------------------------

//формирование первого элемента

pointer *formoth(int d)

{

pointer *px = new pointer;

px->d = d; px->p = NULL;

return px;

}

//добавление элемента

void doboth (pointer **pk, int d)

{

pointer *px = new pointer;

px->d = d;

px->p = NULL;

(*pk)->p = px;

(*pk) = px;

}

//--исключение из очереди-------------------

int iskoth (pointer **ph)

{

int d=(*ph)->d;

(*ph)=(*ph)->p;

return d;

}