Чарга - Вікіпэдыя

# Чарга

### Зьвесткі зь Вікіпэдыі — вольнай энцыкляпэдыі.

Чарга - працэс, арганізаваны згодна прынцыпу FIFO (first in – first out): першы прыйшоў – першы выйшаў. Такая арганізацыя найбольш пашыраная пры абслугоўваньні кліентаў: той хто раней прыйшоў, атрымае паслугу раней. У праграмаваньні чарга - структура дадзеных, што мадэлюе такія працэсы. Сярод усіх элемэнтаў чаргі выдзяляюцца два: першы і апошні.

## [рэдагаваць] Апэрацыі

Асноўныя апэрацыі ў чарзе:

- push: дадаць элемэнт у хвост (пасьля апошняга) чаргі. Колькасьць элемэнтаў у чарзе павялічваецца на 1. Калі памер чаргі абмежаваны, гэтая апэрацыя можа выклікаць памылку overflow – перапаўненьне.
- pop: атрымаць першы элемэнт. Колькасьць элемэнтаў памяньшаецца на 1. Першым элемэнтам становіцца той, што дагэтуль быў другім (калі такі быў). Гэтая апэрацыя магчымая толькі калі ў чарзе быў прынамсі адзін элемэнт.

Дадатковыя, службовыя апэрацыі:

- isEmpty: праверка, ці ёсьць элемэнты ў чарзе. Рэзультат: ісьціна, калі ў чарзе няма элемэнтаў.
- isFull: праверка, ці запоўненая чарга. Рэзультат: ісьціна, калі ў чаргу больш нельга дадаць ніводнага элемэнта.
- clear: ачысьціць чаргу (выдаліць усе элемэнты).
- size: атрымаць памер чаргі (колькасьць элемэнтаў).
- top: атрымаць верхні элемэнт.

## [рэдагаваць] Рэалізацыі чаргі

Рэалізацыя чаргі можа быць зроблена праз масіў ці сьпіс.

### [рэдагаваць] Праз масіў

Для захаваньня элемэнтаў чаргі рэзэрвуецца масіў пэўнага памеру і дзьве зьменных, якія зьмешчаюць індэкс першага элемэнта і памер (даўжыню) чаргі. Прыведзеныя тут альгарытмы і кавалкі коду напісаныя на wikicode, які прапануецца ў якасьці псэўдакоду для напісаньня артыкулаў.

    record queue
    {
      object[0..N-1] data;
      int top = 0;
      int size = 0;
    }

Апэрацыя push павялічвае памер чаргі, а pop павялічвае індэкс першага элемэнту і зьмяньшае памер чаргі.

      function queue.push( object element )
      {
         if ( size < N )
         {
            data[ (top + size) mod N] = element;
            size++;
         }
         else
            throw queue.overflow;
      }

      function queue.pop()
      {
         if ( size > 0 )
         {
           var object element = data[top];
           top = ( top + 1 ) mod N;
           size--;
           return element;
         }
         else
            throw queue.underflow;
      }

Функцыі top і size вяртаюць значэньні адпаведных зьменных, функцыя clear абнуляе іх.

Прыклад ужываньня

    var int a;
    var queue q = new queue();

    q.push(3);
    q.push(4);

    a = q.pop(); // a == 3

### [рэдагаваць] Празь сьпіс

У гэтым выпадку выкарыстоўваецца просты аднабаковы сьпіс, які зьмяшчае элемэнты чаргі і дзьве зьменныя, што захоўваюць спасылкі на першы і апошні элемэнты сьпіса.

      record list
      {
         object head;
         list tail;
      }

      record queue
      {
         list top;
         list last;
      }

Апэрацыя push стварае новы элемэнт сьпісу, і дадае яго ў канец чаргі, пасьля бягучага апошняга. pop вяртае бягучы першы элемэнт і рухае спасылку пачатковага элемэнта на другі:

      function queue.push( object element )
      {
         var list newElement = new list();
         newElement.head = element;
         newElement.tail = null;
         if ( top == null )
         {
            top = newElement;
            last = newElement;
         }
         else
         {
            last.tail = newElement;
            last = newElement;
         }
      }

      function queue.pop()
      {
         if ( top == null )
            throw queue.underflow;
         var object first = top.head;
         top = top.tail;
         return first;
      }

Прыклад ужываньня

    var int a;
    var queue q = new queue();

    q.push(3);
    q.push(4);

    a = q.pop(); // a == 3

## [рэдагаваць] Прымяненьні чаргі

Чэргі ўжываецца ў альгарытмах, што мадэлююць працэсы, арганізаваны згодна прынцыпу FIFO. Напрыклад, пры апрацоўцы клявіатуры: коды націснутых клявіш зьмяшчаюцца ў чаргу; працэсар кампутара мае чаргу каманд, пакуль выконваецца першая, у канец чаргі з памяці дадаюцца наступныя; праграмы, што пабудаваныя на апрацоўцы падзей (event driven, кіраваныя падзеямі) маюць чаргу, дзе захоўваюцца зьвесткі пра новыя падзеі пакуль выконваецца рэакцыя на першую падзею. Мова праграмаваньня Oroogu выкарыстоўвае чаргу як адзіную структуру дадзеных.

## [рэдагаваць] Глядзі таксама

Дрэва, Масіў, Стэк, Сьпіс

Атрымана з «http://be.wikipedia.org../../../%D1%87/%D0%B0/%D1%80/%D0%A7%D0%B0%D1%80%D0%B3%D0%B0.html»

Катэгорыя: Структуры дадзеных

##### Views

- Артыкул
- Гутаркі
- Бягучая вэрсія

##### Пошук

##### На іншых мовах

- Deutsch
- English
- Français
- 日本語