Очередь представляет собой линейный список, доступ к элементам которого осуществляется по принципу 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 << "nнет памяти для очереди"; exit(1);

}

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

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

}

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

template <class Qtype>

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

{

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

{

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

       return;

}

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

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

}

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

template <class Qtype>

Qtype queue <Qtype> :: qretrieve()

{

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

{

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

       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()<<" n";//выведет 100

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

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

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 << "nнет памяти для очереди"; 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 << "nОчередь переполнена"; 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 << "nОчередь пуста"; 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()<<" n";//выведет 100

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

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

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 << "nНет памяти для стека";

       exit(1);

}

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

}

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

template <class Stype>

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

{

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

{

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

       return;

}

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

}

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

template <class Stype>

Stype stack <Stype>:: pop()

{

if(tos == 0)

{

cout << "nСтек пуст"; 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()<<"n";// вывод числа 20

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

return 0;

}

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

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

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