Fronta

Fronta je datová struktura, která uchovává prvky ve stejném pořadí, v jakém byly do fronty vloženy. První prvek v pořadí je tedy prvek, který byl do fronty vložen nejdříve. Toto chování se označuje anglickým akronymem FIFO (first in first out) – kdo dřív přijde, je dřív obsloužen.

Implementace

Fronta pomocí statického pole (Java)

kód v jazyce Java - Zobrazit

  1. /**
  2.  * Jednoduchá fronta realizovaná statickým polem.
  3.  * @author Peter Williams
  4.  * @author Vojtěch Hordějčuk
  5.  * @param <E> třída obsaženého prvku
  6.  */
  7. public class Queue<E>
  8. {
  9.   /**
  10.    * pole s prvky fronty
  11.    */
  12.   private Object[] queue;
  13.   /**
  14.    * počet prvků ve frontě
  15.    */
  16.   private int size;
  17.   /**
  18.    * index, na který se bude vkládat
  19.    */
  20.   private int top;
  21.   /**
  22.    * index, ze kterého se bude mazat
  23.    */
  24.   private int base;
  25.  
  26.   /**
  27.    * Vytvoří novou frontu.
  28.    * @param capacity kapacita fronty
  29.    */
  30.   public Queue(int capacity)
  31.   {
  32.     queue = new Object[capacity];
  33.     size = 0;
  34.     top = 0;
  35.     base = 0;
  36.   }
  37.  
  38.   /**
  39.    * Ověří, zda je fronta prázdná.
  40.    * @return TRUE právě když je fronta prázdná
  41.    */
  42.   public boolean isEmpty()
  43.   {
  44.     return size == 0;
  45.   }
  46.  
  47.   /**
  48.    * Ověří, zda je fronta plná.
  49.    * @return TRUE právě když je fronta plná
  50.    */
  51.   public boolean isFull()
  52.   {
  53.     return size == queue.length;
  54.   }
  55.  
  56.   /**
  57.    * Přidá prvek na konec fronty.
  58.    * @param item vkládaný prvek
  59.    */
  60.   public void enqueue(E item)
  61.   {
  62.     if (isFull())
  63.     {
  64.       throw new RuntimeException("queue overflow");
  65.     }
  66.     queue[top] = item;
  67.     top = (top + 1) % queue.length;
  68.     size++;
  69.   }
  70.  
  71.   /**
  72.    * Vrátí a vyjme prvek na začátku fronty.
  73.    * @return první prvek ve frontě
  74.    */
  75.   @SuppressWarnings("unchecked")
  76.   public E dequeue()
  77.   {
  78.     if (isEmpty())
  79.     {
  80.       throw new RuntimeException("queue underflow");
  81.     }
  82.     Object item = queue[base];
  83.     base = (base + 1) % queue.length;
  84.     size--;
  85.     return (E) item;
  86.   }
  87. }
Fronta pomocí spojového seznamu (Java)

kód v jazyce Java - Zobrazit

  1. /**
  2.  * Dynamická fronta realizována pomocí seznamu.
  3.  * @author Vojtěch Hordějčuk
  4.  */
  5. public class LinkedQueue<E>
  6. {
  7.   /**
  8.    * hlavička fronty
  9.    */
  10.   private Node<E> head;
  11.   /**
  12.    * ocas fronty
  13.    */
  14.   private Node<E> tail;
  15.  
  16.   /**
  17.    * Vytvoří novou frontu.
  18.    */
  19.   public LinkedQueue()
  20.   {
  21.     head = null;
  22.     tail = null;
  23.   }
  24.  
  25.   /**
  26.    * Ověří, zda je fronta prázdná.
  27.    * @return TRUE právě když je fronta prázdná
  28.    */
  29.   public boolean isEmpty()
  30.   {
  31.     return head == null;
  32.   }
  33.  
  34.   /**
  35.    * Přidá prvek na konec fronty.
  36.    * @param item vkládaný prvek
  37.    */
  38.   public void enqueue(E item)
  39.   {
  40.     Node<E> newTail = new Node<E>(item);
  41.  
  42.     if (head == null)
  43.     {
  44.       head = newTail;
  45.       tail = newTail;
  46.     }
  47.     else
  48.     {
  49.       tail.append(newTail);
  50.       tail = newTail;
  51.     }
  52.   }
  53.  
  54.   /**
  55.    * Vrátí a vyjme prvek na začátku fronty.
  56.    * @return první prvek ve frontě
  57.    */
  58.   public E dequeue()
  59.   {
  60.     if (isEmpty())
  61.     {
  62.       throw new RuntimeException();
  63.     }
  64.  
  65.     E headValue = head.getValue();
  66.     head = head.getNext();
  67.     return headValue;
  68.   }
  69.  
  70.   /**
  71.    * Prvek spojového seznamu.
  72.    * @param <E> třída hodnoty
  73.    */
  74.   private static class Node<E>
  75.   {
  76.     private E value;
  77.     private Node<E> next;
  78.  
  79.     protected Node(E value0)
  80.     {
  81.       value = value0;
  82.       next = null;
  83.     }
  84.  
  85.     protected E getValue()
  86.     {
  87.       return value;
  88.     }
  89.  
  90.     protected Node<E> getNext()
  91.     {
  92.       return next;
  93.     }
  94.  
  95.     protected void append(Node<E> next0)
  96.     {
  97.       next = next0;
  98.     }
  99.   }
  100. }

Reference