Назад | Начало урока | Вперед
Содержание

Глава 02

Вверх

Очереди

Очередь представляет собой линейный список, доступ к элементам
которого осуществляется по принципу FIFO(first-in,first-out).
Таким образом первым из очереди удаляется элемент, помещенный туда первым.
Для очереди этот метод доступа является единственным.
В отличие от массива произвольный доступ к указанному элементу не
допускается.

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

Изучение принципов работы очереди начнем с рассмотрения двух функций

void qstore (Qtype i);
Qtype qretrieve();

Функция void qstore (Qtype i); помещает элемент в конец очереди
а функция Qtype qretrieve();извлекает из очереди первый элемент
и возвращает его значение.
В таблице 2.1 приведены результаты выполнения последовательности
таких операций.(стр52)

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

Посмотрите программу:

Программа sch02_02.cpp

//параметризированный класс очереди

#include<iostream.h>
#include<stdlib.h>

//параметризированный класс очереди
template <class Qtype> class queue
{

Qtype *q;
int sloc,rloc;
int length;
public:
queue(int size);
~queue() {delete [] q;}
void qstore(Qtype i);
Qtype qretrieve();
};

//конструктор очереди
template <class Qtype> queue ::queue(int size)
{

size++;

q=new Qtype[size];
if(!q)
{

cout<<"Nevozmoghno sozdaty ocheredy. \n";
exit(1);
}
length =size;
sloc=rloc=0;
}

//объект помещается в очередь функция qstore()
template <class Qtype> void queue ::qstore (Qtype i)
{

if(sloc+1==length)
{
cout<<"Ocheredy zapolnena.\n";
return;
}
sloc++;
q[sloc]=i;
}

//извлечение объекта из очереди функция qretrieve()
template <class Qtype> Qtype queue ::qretrieve()
{

if(rloc==sloc)
{
cout<<"Ocheredy pusta.\n";
return 0;
}
rloc++;
return q[rloc];
}

main()
{

queue<int> a(5),b(5);//создаем две очереди из целых чисел

a.qstore(100);
b.qstore(200);

a.qstore(300);
b.qstore(400);

cout << a.qretrieve() << " ";
cout << a.qretrieve() << " ";
cout << b.qretrieve() << " ";
cout << b.qretrieve() << endl;

queue<double> c(5),d(5);//создаем две очереди типа double

c.qstore(8.12);
d.qstore(9.99);

c.qstore(-2.00);
d.qstore(0.986);

cout << c.qretrieve() << " ";
cout << c.qretrieve() << " ";
cout << d.qretrieve() << " ";
cout << d.qretrieve() << endl;

return 0;

}

Результат:

100 300 200 400
8.12 -2 9.99 0.986

Анализ:

Каждая очередь содержится в динамически выделяемом массиве, указатель
на который содержит переменная q.

Qtype *q;
q=new Qtype[size];

Размер очереди передается как параметр конструктору класса queue.

queue(int size)

Этот размер хранится членом length структуры queue.

length =size;

Вот этот конструктор:

//конструктор очереди- класса queue

template queue ::queue(int size)
{

size++;

q=new Qtype[size];
if(!q)
{

cout<<"Nevozmoghno sozdaty ocheredy. \n";
exit(1);
}
length = size;
sloc=rloc=0;
}

Обратите внимание, что размер массива, выделяемого в главной программе
для поддержки очереди, превышает размер очереди.

queue a(5),b(5);//создаем две очереди из целых чисел

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

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

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

Вверх

Циклическая очередь

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

Параметризированный класс циклической очереди

#include<iostream.h>
#include<stdlib.h>

//параметризированный класс циклической очереди

template <class Qtype> class queue
{

Qtype *q; //указатель на тип Qtype
int sloc,rloc; //переменные
int length;
public:
queue(int size); //конструктор
~queue() {delete [] q;} //деструктор встроенный
void qstore (Qtype i); //функции
Qtype qretrieve();

};

//конструктор очереди
template <class Qtype> queue <Qtype>::queue(int size)
{

size++;

q=new Qtype[size]; //создали массив в динамической памяти
if(!q)
{

cout<<"Nevozmoghno sozdaty ocheredy. \n";
exit(1);
}
length = size; //длина массива на единицу больше чем длина очереди;сохранить в length
sloc=rloc=0;
}

//объект помещается в очередь
template <class Qtype> void queue <Qtype>::qstore (Qtype i)
{

if(sloc==length || (sloc==length && !rloc))
{
cout<<"Ocheredy zapolnena.\n";
return;
}
q[sloc]=i;
sloc++;
if(sloc==length) sloc = 0; //циклический переход

}

//извлечение объекта из очереди
template <class Qtype> Qtype queue ::qretrieve()
{

if(rloc==length) rloc=0;//циклический переход
if(rloc==sloc)
{
cout << "Ocheredy pusta.\n";
return 0;
}
rloc++;
return q[rloc-1];
}


main()
{

queue a(10);//создаем очередь из чисел типа int
int i;
//демонстрируем работу целочисленной циклической очереди
for(i=0;i<10;i++) a.qstore(i);
cout << a.qretrieve() << endl;
a.qstore(10);
cout << a.qretrieve() << endl;
a.qstore(11);
cout << a.qretrieve() << endl;
a.qstore(12);

for(i=0;i<10;i++) cout << a.qretrieve() << " ";
cout << endl;

queue b(10);//создаем очередь из чисел типа double
//демонстрируем работу циклической очереди
for(i=0;i<10;i++) b.qstore((double)i*1.1);
cout << b.qretrieve() << endl;
b.qstore(10.0);
cout << b.qretrieve() << endl;
b.qstore(11.1);
cout << b.qretrieve() << endl;
b.qstore(12.2);
for(i=0;i<10;i++) cout << b.qretrieve() << " ";

return 0;

}

Вывод программы:
0
1
2
3 4 5 6 7 8 9 10 11 12
0
1.1
2.2
3.3 4.4 5.5 6.6 7.7 8.8 9.9 10 11.1 12.2

В этой версии очередь будет переполнена только в том случае, когда
индекс извлечения, будет на 1 больше чем индекс сохранения. Очередь будет
пуста, когда rloc=sloc .Во всех остальных случаях в очереди будет
оставаться место для ввода еще одного элемента.

Вверх

Стеки

Стек по смыслу противоположен очереди так как использует принцип LIFO.
(last-in,first-out).
Фактически компиляторы С++ используют стек для передачи аргументов
функциям.
Две базовых операции со стеком - сохранение и извлечение по традиции
называют push и pop соответственно. Поэтому чтобы реализовать стек
нужны две функции: push()- которая помещает элемент в стек, и pop() -
которая извлекает элемент из стека. Кроме того для реализации стека
потребуется область памяти, которая будет использоваться в качестве стека.
Для этой цели можно использовать массив, а можно выделить область памяти
с помощью new. Функция извлечения, как и в случае с очередью, удаляет
элемент из списка и уничтожает его содержимое (если только этот
элемент не хранится где-нибудь еще).
Пример работы стека приведен в таблице 2.2 стр 58.

Приведенная ниже программа реализует параметризированный класс стека.

#include<iostream.h>
#include<stdlib.h>

//параметризированный класс стека

template <class Stype> class stack
{

Stype *stck; //указатель на тип Stype
int tos; //переменные
int length;
public:
stack(int size); //конструктор
~stack() {delete [] stck;} //деструктор встроенный

void push (Stype i); //функции
Stype pop();

};

//конструктор стека
template <class Stype> stack <Stype>::stack(int size)
{


stck=new Stype[size]; //создали массив в динамической памяти
if(!stck)
{
cout<<"Nevozmoghno sozdaty stack. \n";
exit(1);
}
length =size; //длина массива на единицу больше чем длина очереди;сохранить в length
tos=0;
}

//объект помещается в стек
template <class Stype> void stack <Stype>::push (Stype i)
{

if(tos==length)
{
cout<<"Stack zapolnen.\n";
return;
}
stck[tos]=i;
tos++;
}

//извлечение объекта из стека
template <class Stype> Stype stack <Stype>::pop()
{

if(tos==0)
{
cout<<"Stack pust.\n";
return 0;
}
tos--;
return stck[tos];
}


main()
{

stack<int> a(10);//создаем стек из чисел типа int
stack<double> b(10);//создаем стек из чисел типа double
stack<char> c(10);//создаем стек из переменных типа char

int i;

//используем стеки типа int И double

a.push(10);
b.push(100.1);
a.push(20);
b.push(10-3.3);

cout << a.pop() << " ";
cout << a.pop() << " ";
cout << b.pop() << " ";
cout << b.pop() << endl;

//демонстрируем работу символьного стека
for(i=0;i<10;i++) c.push((char)'A'+i);
for(i=0;i<10;i++) cout << c.pop();
cout<

return 0;

}

Результат:

20 10 6.7 100.1
JIHGFEDCBA

Стек содержится в динамически выделяемом массиве, указателем на который
является переменная stck. Размер стека передается конструктору класса
стека как параметр. Этот размер содержит переменная-член length.
Переменная-член tos обозначает индекс следующей открытой позиции
стека, которая является его вершиной. Если стек пуст, переменная tos
равна нулю. Если tos больше индекса последнего сохранения, это указывает
на то, что стек заполнен.

Нижеприведенный пример иллюстрирует использование стека при реализации
постфиксного калькулятора.

//простой калькулятор, использующий параметризованный стек

#include
#include

void calculator();

//параметризированный класс стека

template class stack
{

Stype *stck; //указатель на тип Stype
int tos; //переменные
int length;
public:
stack(int size); //конструктор
~stack() {
delete [] stck;
} //деструктор встроенный

void push (Stype i); //функции
Stype pop();

};

//конструктор стека

template stack ::stack(int size)
{

stck = new Stype[size]; //создали массив в динамической памяти
if(!stck)
{
cout<<"Nevozmoghno sozdaty stack. \n";
exit(1);
}
length =size; //длина массива на единицу больше чем длина очереди;сохранить в length
tos=0;
}

//объект помещается в стек

template void stack ::push (Stype i)
{

if(tos==length)
{
cout<<"Stack zapolnen.\n";
return;
}
stck[tos]=i;
tos++;
}

//извлечение объекта из стека

template Stype stack ::pop()
{

if(tos==0)
{
cout<<"Stack pust.\n";
return 0;
}
tos--;
return stck[tos];
}


main()
{

calculator();
return 0;
}

//калькулятор с четыремя действиями арифметики

void calculator()
{

stack calc(100);
double a, b;
char str[80];

cout << "Prosteishiy calculator \n";
cout << " Dlia vyhoda nazhmite 'q' \n";

do {

cout << ":";
cin >> str;
switch(*str) {

case '+' :

a = calc.pop();
b = calc.pop();
cout << a+b << endl;
calc.push(a+b);
break;

case '-' :


a = calc.pop();
b = calc.pop();
cout << b-a << endl;
calc.push(b-a);
break;

case '*' :

a = calc.pop();
b = calc.pop();
cout << a*b << endl;
calc.push(a*b);
break;
case '/' :
a = calc.pop();
b = calc.pop();
if(!a) {
cout << " Delenie na 0 \n";
break;
}
cout << b/a << endl;
calc.push(b/a);
break;

case '.' : // Pokazaty soderzhimoe vershiny steka

a = calc.pop();
calc.push(a);
cout << "Tekushee znachenie v vershine steka : " ;
cout << a << endl;
break;

default:

calc.push(atof(str));
}

} while (*str != 'q');

}

Назад | Начало урока | Вверх | Вперед
Содержание

Hosted by uCoz