C++. Очередь. Особенности реализации. Способы реализации очереди. Представление очереди как динамического массива

Очередь. Особенности реализации. Способы реализации очереди. Представление очереди в виде динамического массива


Содержание


1. Структура данных «очередь». Особенности реализации очереди

Очередь – это динамическая структура данных которая состоит из набора элементов которые размещены последовательно друг за другом. При этом добавление элементов осуществляется с одной стороны, а удаление (вытягивание) – с другой стороны.
Очередь работает по принципу FIFO (First In — First Out), то есть «первым пришел – первым вышел». На рисунке 1 отображен принцип работы очереди.

Динамическая структура данных "очередь"

Рисунок 1. Динамическая структура данных «очередь»

Одной из особенностей очереди есть то, что в очереди часть последовательных элементов может быть занята на данный момент времени (рисунок 2).

Очередь, в которой часть элементов занята на данный момент времени

Рисунок 2. Очередь, в которой часть элементов занята на данный момент времени

В повседневной жизни использование очереди встречается довольно часто, например:

  • очередь в магазине;
  • очередь документов на печать на принтере;
  • последовательность операторов в алгоритме которые выполняются друг за другом;
  • другие случаи.

 

2. Виды очередей

Различают следующие виды очередей:

  • простая очередь;
  • кольцевая очередь. В такой очереди элемент, который выходит с начала очереди, будет помещен в ее конец;
  • очередь с приоритетами. В такой очереди элементы размещаются по их приоритетам (весовым коэффициентам). Первым из очереди выходит элемент с наивысшим приоритетом.

Любой вид очереди может иметь ограничение по размеру (количество элементов в очереди).

 

3. Способы реализации очереди

В программе очередь можно реализовывать в виде:

  • статического массива с ограничением на размер в очереди;
  • динамического массива;
  • односвязного списка;
  • двусвязного списка.

 

4. Кольцевая очередь

В кольцевой очереди элемент, который выходит (удаляется) из очереди помещается в ее конец (рисунок 3).

Кольцевая очередь

Рисунок 3. Кольцевая очередь

На рисунке 4 изображена работа кольцевой очереди в случае, когда часть элементов занята.

Кольцевая очередь. Случай когда часть элементов занята

Рисунок 4. Кольцевая очередь. Случай когда часть элементов занята

Примеры кольцевой очереди:

  • движение трамваев по круговому маршруту;
  • очередь событий для их обработки в Windows.

 

5. Очередь с приоритетами. Способы реализации

В очереди с приоритетами первым выходит (удаляется) тот элемент, который имеет наивысший приоритет. В очереди с приоритетами каждому элементу ставится в соответствие приоритет (весовой коэффициент).

Очередь с приоритетами может быть реализована одним из двух способов:

  • очередь с приоритетным включением. В этом случае элемент, который добавляется в очередь, сразу размещается в ней в соответствии с его приоритетом (рисунок 5). При удалении, этот элемент просто вытягивается с конца очереди;
  • очередь с приоритетным исключением. В этом случае новый элемент просто добавляется в конец очереди. А вытягивание элемента из очереди осуществляется по его приоритету, то есть вытягивается элемент с наивысшим приоритетом (рисунок 6).

Очередь с приоритетным включением. Добавление нового элемента в соответствии с его приоритетом

Рисунок 5. Очередь с приоритетным включением.
Добавление нового элемента в соответствии с его приоритетом

Очередь с приоритетным исключением. Элемент добавляется в конец очереди, вытягивается в соответствии с приоритетом

Рисунок 6. Очередь с приоритетным исключением.
Элемент добавляется в конец очереди, вытягивается в соответствии с приоритетом



 

6. Пример реализации очереди в виде динамического массива

В примере объявляется шаблонный класс Queue, реализующий очередь в виде динамического массива для некоторого обобщенного типа T.

В классе реализованы следующие поля и методы:

  • целочисленная внутренняя переменная count – количество элементов в очереди;
  • внутренняя переменная p – указатель на тип T. Этот указатель есть массивом данных образующих очередь. Элемент массива с индексом 0 есть началом очереди. Элемент с индексом count-1 есть конец очереди;
  • конструктор по умолчанию;
  • конструктор копирования Queue(const Queue&);
  • оператор копирования operator=(const Queue&);
  • метод push() – добавляет элемент в конец очереди;
  • деструктор;
  • метод pop() – вытягивает первый элемент из очереди;
  • метод GetItem() – читает первый элемент из очереди не вытягивая его;
  • метод clear() – очищает очередь;
  • метод IsEmpty() – проверяет пустая ли очередь;
  • метод Get() – возвращает количество элементов в очереди;
  • метод print() – выводит очередь на экран.

Программный код класса следующий:

#include <iostream>
#include <new>
using namespace std;

// Динамическая структура данных "очередь"
template <typename T>
class Queue
{
private:
  T* p; // динамический массив
  int count; // количество элементов в очереди

public:
  // конструктор по умолчанию
  Queue()
  {
    count = 0; // очередь пустая
  }

  // конструктор копирования
  Queue(const Queue& obj)
  {
    // скопировать obj в текущий объект
    count = obj.count;

    try {
      // попытка выделить память для p
      p = new T[count];
      // заполнить значениями
      for (int i = 0; i < count; i++)
        p[i] = obj.p[i];
    }
    catch (bad_alloc e)
    {
      // если память не выделена, то вывести текст ошибки
      cout << e.what() << endl;
      count = 0; // создать пустую очередь
    }
  }

  // добавить элемент в очередь
  void push(T item)
  {
    T* p2; // объявить дополнительный указатель
    p2 = p; // перенаправить дополнительный указатель на p

    try {
      // попытка выделить новый фрагмент памяти для p, но на 1 больше
      p = new T[count + 1];

      // скопировать данные из участка на который указывает p2 (старые данные)
      // в участок, на который указывает p
      for (int i = 0; i < count; i++)
        p[i] = p2[i];

      // скопировать последний элемент
      p[count] = item;

      // увеличить количество элементов на 1
      count++;

      // освободить предварительно выделенную память
      if (count > 1)
        delete[] p2;
    }
    catch (bad_alloc e)
    {
      // если память не выделена
      cout << e.what() << endl; // вывести сообщение об ошибке

      // вернуть старый указатель на p
      p = p2;
    }
  }

  // вытянуть первый элемент из очереди
  T pop()
  {
    if (count == 0)
      return 0;

    // заполнить элемент, который вытягивается из очереди
    T item;

    item = p[0];

    // сформировать новый участок памяти, который на 1 меньше
    try {
      T* p2;

      // попытка выделить пам'ять
      p2 = new T[count - 1];

      count--; // уменьшить количество элементов в очереди

      // p=>p2
      for (int i = 0; i < count; i++)
        p2[i] = p[i + 1]; // копируются все кроме первого элемента

      // освободить участок, на который указывает p
      if (count > 0)
        delete[] p;

      // перенаправить p на p2
      p = p2;

      // вернуть item
      return item;
    }
    catch (bad_alloc e)
    {
      // если память не выделилась, то вернуть 0
      cout << e.what() << endl;
      return 0;
    }
  }

  // операторная функция operator=(),
  // реализует присваивание объектов типа Queue
  Queue& operator=(const Queue& obj)
  {
    T* p2; // указатель на дополнительную память

    try {
      // попытка выделить новый участок памяти для p2
      p2 = new T[obj.count];

      // если память выделена успешно,
      // можно освобождать предварительно выделенную память для p
      if (count > 0)
        delete[] p;

      // скопировать obj в текущий объект
      p = p2; // перенаправить p на p2
      count = obj.count;

      // заполнить значениями
      for (int i = 0; i < count; i++)
        p[i] = obj.p[i];
    }
    catch (bad_alloc e)
    {
      // если память не выделилась, то вывести соответствующее сообщение
      cout << e.what() << endl;
    }
    return *this; // вернуть текущий объект
  }

  // деструктор
  ~Queue()
  {
    if (count > 0)
      delete[] p;
  }

  // взять первый элемент из очереди не вытягивая его
  T GetItem()
  {
    if (count > 0)
      return p[0];
    else
      return 0;
  }

  // очистка очереди
  void clear()
  {
    if (count > 0)
    {
      delete[] p;
      count = 0;
    }
  }

  // проверка существования элементов в очереди
  bool IsEmpty()
  {
    return count == 0;
  }

  // количество элементов в очереди
  int GetN()
  {
    return count;
  }

  // метод, выводящий очередь
  void print(const char* objName)
  {
    cout << "Object: " << objName << endl;
    for (int i = 0; i < count; i++)
      cout << p[i] << "\t";
    cout << endl;
    cout << "---------------------" << endl;
  }
};

void main()
{
  Queue<int> Q1;
  Q1.print("Q1");

  Q1.push(5);
  Q1.print("Q1");

  Q1.push(8);
  Q1.push(11);
  Q1.push(17); // Q1 = {5,8,11,17}
  Q1.print("Q1");

  int d;
  d = Q1.GetItem();
  cout << "d = " << d << endl;

  Q1.print("Q1");

  Queue<int> Q2 = Q1;
  Q2.print("Q2");

  Queue<int> Q3;
  Q3 = Q1 = Q2;
  Q1.push(333);
  Q2.push(555);

  Q1.print("Q1");
  Q2.print("Q2");
  Q3.print("Q3");

  Q2.clear();
  if (Q2.IsEmpty())
    cout << "OK" << endl;
  else
    cout << "NO" << endl;

  cout << "n = " << Q3.GetN() << endl;
}

Результат выполнения программы

Object: Q1

---------------------
Object: Q1
5
---------------------
Object: Q1
5 8 11 17
---------------------
d = 5
Object: Q1
5 8 11 17
---------------------
Object: Q2
5 8 11 17
---------------------
Object: Q1
5 8 11 17 333
---------------------
Object: Q2
5 8 11 17 555
---------------------
Object: Q3
5 8 11 17
---------------------
OK
n = 4

 


Связанные темы