Fronta je jedním ze základních datových typů a slouží k ukládání a výběru dat takovým způsobem, aby prvek, který byl uložen jako první, byl také jako první vybrán. Tomuto principu se říká FIFO - first in, fist out. Opačný přístup - LIFO - last in, first out - používá datový typ zásobník.
Speciálním případem fronty je tzv. prioritní fronta, ve které mohou prvky s vyšší prioritou předbíhat na výstupu ty s nižší prioritou.
Typické operace
Fronta
- addLast (enqueue) – Vloží prvek do fronty.
- deleteFirst (poll, dequeue) – Získá a odstraní první prvek (hlavu) fronty.
- getFirst (peek) – Získá první prvek fronty.
- isEmpty – Dotaz na prázdnost fronty.
- size – Vrátí počet obsažených prvků.
Využití
Fronta má v informatice široké využití, toto jsou některé příklady:
- Synchronizační primitivum
- Operátor roura (pipe) - komunikace mezi procesy v operačních systémech
- Kruhový buffer - vyrovnávací paměť pro datové toky
Kód
01./**02. * Fronta - implementovana jako spojovy seznam03. */04.public class Queue {05. private Node first;06. private Node last;07. private int size;08. public Queue() {09. this.size = 0;10. }11. 12. /**13. * Prida na konec fronty prvek - asymptoticka sloztitost O(1)14. * @param i prvek k vlozeni15. */16. public void addLast(int i) {17. Node n = new Node(i);18. if(getSize() == 0) {19. this.first = n;20. this.last = n;21. } else {22. this.last.next = n;23. this.last = n;24. }25. size++; 26. }27. 28. /**29. * Odebere z fronty prvni prvek - asymptoticka sloztitost O(1)30. * @return prvni prvek31. */32. public int deteteFirst() {33. if(getSize() == 0) throw new IllegalStateException("Fronta je prazdna");34. int value = first.value;35. first = first.next;36. size--;37. return value;38. }39. /**40. * Vrati prvni prvek fronty 41. * @return prvni prvek42. */43. public int getFirst() {44. if(getSize() == 0) throw new IllegalStateException("Fronta je prazdna");45. return first.value;46. }47. /**48. * Getter na delku49. * @return delka fronty50. */51. public int getSize() {52. return size;53. }54. 55. /**56. * Dotaz pra prazdnost57. * @return true, pokud je fronta prazdna58. */59. public boolean isEmpty() {60. return this.size == 0;61. }62. 63. /**64. * Klasicka toString metoda, vraci textovou reprezentaci objektu65. * @return textova reprezentace objektu66. */67. @Override68. public String toString() {69. StringBuilder builder = new StringBuilder();70. Node curr = first;71. for(int i = 0; i < this.size; i++) {72. builder.append(curr.value).append(" ");73. curr = curr.next;74. }75. return builder.toString();76. } 77. 78. /**79. * Vnitrni reprezentace prvku80. */81. private class Node {82. private int value;83. private Node next;84. private Node(int value) {85. this.value = value;86. }87. } 88.}