Вы здесь

Линейные(связные) списки.Очередь

Исходный код на C++: 

Теория

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

Представление очереди в графическом виде.
Рис 1 Представление очереди в графическом виде.

Очередь имеют несколько стандартных функций push(затолкнуть элемент), pop(вытолкнуть элемент), clean(удалить все элементы), view(просмотр элементов). Рассмотрим перечисленные функции более подробно. Функция push выполняет несколько операций:
1)создание нового узла;
2)инициализация информационного поля;
3)инициализация ссылочного поля;
4)если новый элемент является единственным, то оба заголовка ссылаются на него (если элемент один, то он первый и последний). В противном случае следующий элемент за последним новый (Last->next=a), а новый элемент последний (Last=a). Добавим новое значение в очередь (push 4). После операции push линейный список содержит один элемент (рис. 2).

Добавление нового значения
Рис 2. Добавление нового значения.

Добавим ещё несколько значений (push 6 и push 7). Очередь содержит три элемента (рис. 3) в следующей последовательности.

Добавление новых значений
Рис 3. Добавление новых значений

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

Выталкивание элемента из списка
Рис 4. Выталкивание элемента из списка

Функция view пробегает по всем элементам и выводит в консоль значение информационного поля. Функция clean удаляет все элементы в списке и присваивает заголовкам пусто (first=null и last=null). После данной операции список возвращается в исходное состояние.

Программная реализация

struct node //описание структуры
{
newtp data;
node *next;
} *First=NULL,*Last=NULL;
void push(newtp val)//добавить узел в очередь
{
node *a=new node;
a->data=val;
a->next=NULL;
if(First==NULL)//если это первый элемент то и превый и последний указывают на него
Last=First=a;
else
{
Last->next=a;
Last=a;
}
}
newtp pop()//вытолкнуть узел из очереди
{
if(First==NULL) return (newtp)0;// спсок пуст
node *a=First;
newtp val=a->data;
First=a->next;
if(First==NULL)Last=NULL;//в списке всего один элемент
delete a;
return val;
}
void clean()//удалить все элементы из очереди
{
for(node *a=First;a!=NULL;a=a->next) delete a;
First=Last=NULL;
}
void view()//просмотр элементов очереди
{
for(node *a=First;a!=NULL;a=a->next) printf ("Value=%d \n",(int)a->data);
}