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(), який перевіряє чи черга пуста;
метод GetN() – повертає кількість елементів у черзі;
метод 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

⇑

Зв’язані теми

Стек. Способи реалізації. Операції над стеком. Приклад реалізації стеку у вигляді динамічного масиву

⇑

BestProg