3.2. параметризованные очереди и стеки

Очередь представляет собой линейный список, доступ к элементам которого осуществляется по принципу FIFO («первым вошел – первым вышел»).

Рассмотрим две функции обслуживания очереди: qstore() и qretrieve(). Функция qstore() помещает элемент в конец очереди, а функция qretrieve() извлекает из очереди первый элемент и возвращает его значение.

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

// очередь элементов типа Qtype

#include <conio.h>                    //библиотека консольного ввода-вывода

#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 <Qtype>:: queue(int size)

{

   size++; // размер на 1 больше

   q = new Qtype[size]; //выделим память

   if(!q) //если не удалось выделить память

   {

               cout << " нет памяти для очереди"; exit(1);

}

length = size;   //длина очереди          

sloc = rloc = 0; // начало и конец очереди

}

// запись в очередь

template <class Qtype>

void queue <Qtype>:: qstore(Qtype i)

{

   if(sloc+1 == length) //если нельзя сместить указатель на конец

   {

               cout << "Очередь переполнена ";

               return;

}

sloc++; //смещаем указатель

q[sloc] = i; //записываем элемент

}

// чтение и удаление из очереди

template <class Qtype>

Qtype queue <Qtype> :: qretrieve()

{

   if(rloc == sloc) //если указатель на конец равен указателю на начало

   {

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

               return 0;

}

rloc++; return q[rloc];

}

// пример использования очереди

main()

{

   clrscr();                                    //очистка экрана

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

   queue <double> c(10);            //одна очередь с числами с плавающей точкой

   a.qstore(100);

   a.qstore(200);

   b.qstore(300);

   b.qstore(400);

   cout<<"Первый элемент очереди а "<<a.qretrieve()<<" ";//выведет 100

   cout<<"Второй элемент очереди а "<<a.qretrieve()<<" "; // выведет 200

   cout << a.qretrieve() << " "; // "очередь пуста"

   c.qstore(-1);

   c.qstore(-2);

   cout<<"Первый элемент очереди с "<<c.qretrieve()<<" "; //выведет -1

   return 0;

}

Результат работы программы

Первый элемент очереди а 100

Второй элемент очереди а 200

Очередь пуста 0

Первый элемент очереди с –1

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

Приведём текст программы, имеющей те же самые результаты, что и в предыдущем примере, но использующей в своей работе циклическую очередь.

// очередь элементов типа Qtype

#include <conio.h>                    //библиотека консольного ввода-вывода

#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 <Qtype>:: queue(int size)

{

   size++; // размер на 1 больше

   q = new Qtype[size]; //выделим память

   if(!q) //если не удалось выделить память

   {

               cout << " нет памяти для очереди"; exit(1);

}

length = size;   //длина очереди          

sloc = rloc = 0; // начало и конец очереди

}

// запись в очередь

template <class Qtype>

void queue <Qtype>::qstore(Qtype i) // добавление

{

if((sloc+1 == rloc) || (sloc+1 == length) && !rloc)

   {

               cout << " Очередь переполнена"; return;

}

q[sloc] = i; sloc++;

if(sloc == length) sloc = 0;         // циклический список

}

// чтение и удаление из очереди

template <class Qtype>

Qtype queue <Qtype>:: qretrieve()

{

   if(rloc == length) rloc = 0;

   if(rloc == sloc)

   {

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

}

rloc++;

return q[rloc-1];

}

// пример использования очереди

main()

{

   clrscr();                                    //очистка экрана

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

   queue <double> c(10);            //одна очередь с числами с плавающей точкой

   a.qstore(100);

   a.qstore(200);

   b.qstore(300);

   b.qstore(400);

   cout<<"Первый элемент очереди а "<<a.qretrieve()<<" ";//выведет 100

   cout<<"Второй элемент очереди а "<<a.qretrieve()<<" "; // выведет 200

   cout << a.qretrieve() << " "; // "очередь пуста"

   c.qstore(-1);

   c.qstore(-2);

   cout<<"Первый элемент очереди с "<<c.qretrieve()<<" "; //выведет -1

   return 0;

}

Результат работы программы

Первый элемент очереди а 100

Второй элемент очереди а 200

Очередь пуста 0

Первый элемент очереди с –1

Стек представляет собой линейный список, доступ к элементам которого осуществляется по принципу LIFO («последним вошел – первым вышел»).        

Две основные операции традиционно называются pop() (извлечение) и push() (добавление).        

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

//программа, использующая стек       

#include <conio.h>                    //библиотека консольного ввода-вывода

#include <iostream.h>               //библиотека потокового ввода-вывода

#include <stdlib.h>       //стандартная библиотека

template <class Stype>

class stack         //класс стека

{

   Stype *s;                     // массив, содержащий элементы стека

   int tos;                         // число записанных элементов

   int length;                    // размер стека

public:

   stack(int size);        // конструктор

   ~stack() {delete [] s;} // освобождение памяти

   void push(Stype i);     // запись элемента в стек

   Stype pop();            // извлечение элемента из стека

};

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

template <class Stype>

stack <Stype>:: stack(int size)

{

   s = new Stype[size];    // захват памяти

   if(!s)               // если s=0

   {

               cout << " Нет памяти для стека";

               exit(1);

}

length = size; tos = 0;    // вершина стека

}

// запись объекта в стек

template <class Stype>

void stack <Stype>:: push(Stype i)

{

   if(tos == length)          //если длина стека - максимум

   {

               cout << " Стек переполнен";

               return;

}

s[tos++] = i;                   //сохраняем элемент в стеке

}

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

template <class Stype>

Stype stack <Stype>:: pop()

{

   if(tos == 0)

{

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

}

return s[--tos];                //получение элемента из стека

}

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

main()

{

   stack <int>        a(10); // стек целых чисел

   stack <double> b(10);     // стек чисел с плавающей точкой

   clrscr();                                      // очистка экрана

   a.push(10);               // запись в стек a

   b.push(-1);               // запись в стек b

   a.push(20);               // запись в стек a

   cout <<"Последний элемент стека а "<< a.pop()<<" ";// вывод числа 20

   cout <<"Последний элемент стека b "<< b.pop();      // вывод числа -1

   return 0;

}

Результат работы программы

Последний элемент стека а 20

Последний элемент стека b -1