Очереди

Очередь – это связный список, закон построения которого следующий: новый элемент всегда ставится в конец списка, а удаление элемента происходит из его начала [4, 32]. Таким образом, очередь является структурой данных, которые организованы по принципу FIFO (First In, First Out) – «Первый пришел – первый вышел». Чтобы не ограничивать максимальное число элементов в очереди, очередь может быть реализована в виде однонаправленного списка. В этом случае объекты очереди имеют такую же структуру, как и объекты однонаправленного списка. Часть полей описывает характеристики конкретного объекта и есть поле типа указатель, которое содержит адрес следующего в очереди элемента.

С очередью связаны два указателя. Один содержит адрес объекта, находящегося в начале очереди, а другой хранит адрес последнего объекта очереди. Первый из них назовем begin, а второй end.

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

struct ochered {

int number; // Номер задания

int count; // Объем задания

ochered *next; // Указатель на следующий элемент

};

Задания добавляются в очередь и удаляются из очереди.

Файл “ stdafx.h”

#pragma once

#define WIN32_LEAN_AND_MEAN

#include <stdio.h>

#include <tchar.h>

#include <iostream>

using namespace std;

Файл “Och.h”

struct ochered

{

int number; // Номер задания

int count; // Объем задания

ochered *next; // Указатель на следующий элемент

};

// Прототип функции постановки задания в очередь:

void add_ochered(ochered **begin, ochered **end, int nn, int dl);

// Прототип функции удаления задания из очереди:

void del_ochered(ochered **begin, ochered **end);

// Прототип функции печати содержимого очереди:

void print_ochered(ochered *begin);

Файл “Och.cpp”

#include "stdafx.h"

#include "Och.h"

void add_ochered(ochered **begin, ochered **end, int nn, int dl)

{

ochered *new_el;

// Создание нового элемента:

new_el=new ochered;

(*new_el).number=nn;

(*new_el).count=dl;

(*new_el).next=NULL;

if(*begin==NULL)

{

// Очередь пуста.Элемент добавляется как единственный:

(*begin)=(*end)=new_el;

return;

}

// Добавление нового элемента в очередь:

(**end).next=new_el;

(*end)=new_el;

}

void del_ochered(ochered **begin, ochered **end)

{

ochered *ptr;

ptr=*begin;

if(*begin==NULL)

{

// Очередь пуста:

cout<<"Очередь пуста";

return;

}

// Передвигается начало очереди:

(*begin)=(**begin).next;

// Освобождается место удаляемого элемента:

delete ptr;

}

void print_ochered(ochered *begin)

{

ochered *ptr=begin;

cout<<" Номер задания | Его длина"<<'\n';

while(ptr!=NULL)

{

cout.width(12);

cout<<(*ptr).number;

cout.width(18);

cout<<(*ptr).count<<'\n';

ptr=(*ptr).next;

}

}

//L11_2.cpp

#include "stdafx.h"

#include "Och.h"

int _tmain()

{

ochered *begin, *end;

int nn,dl;

setlocale(LC_CTYPE,"rus");

begin=end=NULL;

// Постановка задания в очередь:

cout<<"Введите номер задания и его длину ";

cin>>nn>>dl;

cout<<"Если хотите прекратить ввод введите номер и длину нулевыми\n";

do

{

add_ochered(&begin, &end, nn, dl);

cout<<"Введите номер задания и его длину ";

cin>>nn>>dl;

}while(nn!=0);

print_ochered(begin);

// Удаляется задание из очереди:

del_ochered(&begin, &end);

print_ochered(begin);

cin.get();

cin.get();

return 0;

}

Результат выполнения программы листинга 11.2 представлен на рис. 11.7.

Рис. 11.7. Результат работы программы листинга 11.2

Стеки

Стек – это связный список, закон построения которого следующий: новый элемент всегда ставится в начало списка, удаление элемента также происходит из его начала [4, 32]. Место, куда помещаются и из которого извлекаются элементы стека, называется вершиной. Таким образом, стек является структурой данных, которые организованы по принципу LIFO (Last In, First Out) – «Последний пришел – первый вышел».

Стек можно реализовать различными способами. Например, элементы стека можно разместить в массиве, либо реализовать стек в виде односвязного списка [32]. Рассмотрим реализацию стека в виде списка. В этом случае объекты стека имеют такую же структуру, как и объекты однонаправленного списка. Часть полей описывает характеристику конкретного объекта и есть поле типа указатель, которое содержит адрес следующего в стеке элемента.

Листинг 11.3. В программе создается стек для проверки правильности расстановок скобок в тексте, содержащимся в файле «input.txt» (рис. 11.7). Будем считать, что есть скобки трех видов – круглые, квадратные и фигурные.

Последовательность скобок считается правильной если [4]:

1. Это элементарная последовательность: (), {}, []

2. Пусть S – это правильно построенная последовательность. Тогда последовательности (S), {S} и [S] – правильно построенные.

3. Пусть S и R правильно построенные последовательности. Тогда последовательность SR – правильно построенная.

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

Содержимое файла “input.txt”

Рис. 11.8. Информация, находящаяся в файле «input.txt»

//L11_3.cpp

#include <fstream>

#include <iostream>

using namespace std;

struct stek

{

char c;

stek*next;

};

stek* add_stek(stek*, char); // Прототип функции добавления элемета в стек

stek* del_stek(stek*); // Прототип функции удаления элемета из стека

int main()

{

char nc[3]={'(','{','['}, kc[3]={')','}',']'}, c;

int i;

setlocale(LC_CTYPE,"russian");

stek *top=NULL;

ifstream ff("input.txt");

c=ff.get();

while(!ff.eof())

{

for(i=0;i<3;i++)

if(c==nc[i])

{

top=add_stek(top, c);

break;

}

for(i=0; i<3; i++)

{

if(c==kc[i])

break;

}

if(i<3 && top!=NULL)

{

if(top->c==nc[i])

top=del_stek(top);

else

{

if(top->c!=nc[i])

{

cout<<"Последовательность построена неправильно\n";

return 0;

}

}

}

else

if(i<3 && top==NULL)

{

cout<<"Последовательность построена неправильно\n";

return 0;

}

c=ff.get();

}

ff.close();

if(top!=NULL)

cout<<"Последовательность построена неправильно\n";

else

cout<<"Последовательность построена правильно\n";

return 0;

}

stek* add_stek(stek *top, char c)

{

stek *new_el;

new_el=new stek;

new_el->c=c;

new_el->next=NULL;

if(top==NULL)

top=new_el;

else

{

new_el->next=top;

top=new_el;

}

return top;

}

stek* del_stek(stek *top)

{

stek *tmp;

tmp=top;

top=top->next;

delete tmp;

return top;

}

Результат выполнения программы листинга 11.3 приведен на рис. 11.9.

Рис. 11.9. Результат работы программы листинга 11.3

Листинг 11.4. В программе создаются структуры очереди и стека, хранящие символ. В файле «input.txt» хранится текст (рис. 11.10). Преобразовать его следующим образом: сначала должны идти цифры в том порядке, в котором они встречаются в файле «input.txt», а затем латинские буквы в обратном порядке, чем в файле «input.txt». Для решения этой задачи считываемые цифры следует помещать в очередь, а латинские буквы в стек. Далее необходимо извлечь информацию из очереди, а затем из стека.

Содержимое файла “input.txt”

Рис. 11.10. Информация, находящаяся в файле «input.txt»

//L11_4.cpp

#include <fstream>

#include <iostream>

using namespace std;

struct ochered

{

char c;

ochered *next; // Указатель на следующий элемент

};

// Прототип функции постановки в очередь:

void add_ochered(ochered **begin, ochered **end, char nc);

// Прототип функции удаления из очереди:

void del_ochered(ochered **begin, ochered **end);

struct stek

{

char c;

stek *next; // Указатель на следующий элемент

};

// Прототип функции постановки в стек:

stek* add_stek(stek *top, char nc);

// Прототип функции удаления из стека:

stek* del_stek(stek*);

// Прототип функции печати содержимого очереди:

void print_och(ochered *begin, char *sn);

// Прототип функции печати содержимого стека:

void print_stek(stek *top, char *sn);

void add_ochered(ochered **begin, ochered **end, char nc)

{

ochered *new_el;

new_el=new ochered; // Создание нового элемента

(*new_el).c=nc;

(*new_el).next=NULL;

if(*begin==NULL) // Очередь пуста.Элемент вносится как единственный

{

(*begin)=(*end)=new_el;

return;

}

// Внесение нового элемента в очередь:

(**end).next=new_el;

(*end)=new_el;

}

void del_ochered(ochered **begin, ochered **end)

{

ochered *ptr;

ptr=*begin;

if(*begin==NULL) // Очередь пуста

{

cout<<"Очередь пуста";

return;

}

// Передвигается начало очереди:

(*begin)=(**begin).next;

// Освобождается память, выделенная для удаляемого элемента:

delete ptr;

}

void print_och(ochered *begin, char *sn)

{

ofstream ff(sn);

ochered *ptr=begin;

while(ptr!=NULL)

{

ff<<(*ptr).c;

ptr=(*ptr).next;

}

}

stek* add_stek(stek *top, char c)

{

stek* new_el;

new_el=new stek; // Создание нового элемента

new_el->c=c;

new_el->next=NULL;

if(top==NULL) // Стек пуст.Элемент вносится как единственный

top=new_el;

else

{

// Внесение нового элемента в стек:

new_el->next=top;

top=new_el;

}

return top;

}

stek*del_stek(stek *top)

{

stek *tmp;

tmp=top;

if(top==NULL) // Стек пуст

{

cout<<"Стек пуст";

return NULL;

}

// Передвигается начало стека:

top=top->next;

// Освобождается память, выделенная для удаляемого элемента:

delete tmp;

return top;

}

void print_stek(stek *top, char *sn)

{

ofstream ff(sn,ios::app);

stek *ptr=top;

while(ptr!=NULL)

{

ff<<(*ptr).c;

ptr=(*ptr).next;

}

}

int main()

{

ifstream ff("input.txt");

char cc[81];

int i;

ochered *begin,*end;

stek *top;

begin=end=NULL;

top=NULL;

ff.getline(cc, 80);

while(!ff.eof())

{

for(i=0; cc[i]!='\0'; i++)

{

if(cc[i]>='A' && cc[i]<='z')

top=add_stek(top, cc[i]);

else

if(cc[i]>='0'&&cc[i]<='9')

add_ochered(&begin, &end, cc[i]);

}

ff.getline(cc, 80);

}

ff.close();

char so[8]="out.txt";

print_och(begin, so);

print_stek(top, so);

return 0;

}

Результат выполнения программы листинга 11.4 приведен на рис. 11.11.

Рис. 11.11. Результат работы программы листинга 11.4