Опашка (абстрактен тип данни): Разлика между версии
Редакция без резюме |
мРедакция без резюме |
||
Ред 3: | Ред 3: | ||
Структурата опашка и поведението на нейните елементи произхождат от ежедневната човешка дейност. Например опашка от хора, чакащи на каса за билети. Опашката има начало и край. Новодошлите хора застават последни на опашката и изчакват докато постепенно се придвижат към началото. Когато стигнат до самото начало на опашката си купуват билет и напускат опашката. Други примери за опашка са документи, чакащи да бъдат принтирани или ескалатор превозващ хора. |
Структурата опашка и поведението на нейните елементи произхождат от ежедневната човешка дейност. Например опашка от хора, чакащи на каса за билети. Опашката има начало и край. Новодошлите хора застават последни на опашката и изчакват докато постепенно се придвижат към началото. Когато стигнат до самото начало на опашката си купуват билет и напускат опашката. Други примери за опашка са документи, чакащи да бъдат принтирани или ескалатор превозващ хора. |
||
== Статична реализация == |
== Статична реализация == |
||
[[Файл:QUEUE-STATIC.jpg|рамка|вдясно|Схема на структурата опашка, добавяне и извличане на елементи.]] |
|||
[[Файл:QUEUE-STATIC.jpg]] |
|||
Статичната опашка се реализира с помощта на [[Масив (програмиране)|масив]]. В даден момент началото и краят на опашката сочат към определени индекси от масива. Когато се добавя нов елемент той се поставя на индекса след края на опашката и краят вече сочи към новия елемент. Когато се премахва началото на опашката, елементът на началния индекс се изтрива и началото започва да сочи към следващия индекс. По този начин с добавяне и извличане на елементи от опашката тя се движи към края на масива. В даден момент краят на опашката достига до последния индекс на масива и се оказва, че размерът на масива не е достатъчен въпреки, че опашката не запълва всичките му елементи. За да се реши този проблем при следващото добавяне на елемент в края на опашката, той се поставя на началния индекс на масива. По този начин се свързват началото и края на масива, и опашката може да обикаля безкрайно в него. Ако дължината на опашката (броя на елементите в нея) стане равна на предварително заделения брой на елементи в масива няма да могат да бъдат добавяни нови елементи. Това налага копиране на опашката в нов масив с по-голям размер. |
Статичната опашка се реализира с помощта на [[Масив (програмиране)|масив]]. В даден момент началото и краят на опашката сочат към определени индекси от масива. Когато се добавя нов елемент той се поставя на индекса след края на опашката и краят вече сочи към новия елемент. Когато се премахва началото на опашката, елементът на началния индекс се изтрива и началото започва да сочи към следващия индекс. По този начин с добавяне и извличане на елементи от опашката тя се движи към края на масива. В даден момент краят на опашката достига до последния индекс на масива и се оказва, че размерът на масива не е достатъчен въпреки, че опашката не запълва всичките му елементи. За да се реши този проблем при следващото добавяне на елемент в края на опашката, той се поставя на началния индекс на масива. По този начин се свързват началото и края на масива, и опашката може да обикаля безкрайно в него. Ако дължината на опашката (броя на елементите в нея) стане равна на предварително заделения брой на елементи в масива няма да могат да бъдат добавяни нови елементи. Това налага копиране на опашката в нов масив с по-голям размер. |
||
== Динамична реализация == |
== Динамична реализация == |
Версия от 08:52, 23 август 2013
Опашка в програмирането е вид абстрактна структура от данни и е представител на абстрактните типове данни (АТД). Опашките спадат към линейните (списъчни) структури от данни, заедно със списъците и стековете. Опашката представлява крайно, линейно множество от елементи, при което елементи се добавят само най-отзад и се извличат само най-отпред. Абстрактната структура опашка изпълнява условието "първият влязъл първи излиза" (FIFO: First-In-First-Out). Това означава, че след като е добавен един елемент в края на опашката, той ще може да бъде извлечен (премахнат), чак когато бъдат премахнати всички елементи преди него и то в реда, в който са добавени. Структурата опашка и поведението на нейните елементи произхождат от ежедневната човешка дейност. Например опашка от хора, чакащи на каса за билети. Опашката има начало и край. Новодошлите хора застават последни на опашката и изчакват докато постепенно се придвижат към началото. Когато стигнат до самото начало на опашката си купуват билет и напускат опашката. Други примери за опашка са документи, чакащи да бъдат принтирани или ескалатор превозващ хора.
Статична реализация
Статичната опашка се реализира с помощта на масив. В даден момент началото и краят на опашката сочат към определени индекси от масива. Когато се добавя нов елемент той се поставя на индекса след края на опашката и краят вече сочи към новия елемент. Когато се премахва началото на опашката, елементът на началния индекс се изтрива и началото започва да сочи към следващия индекс. По този начин с добавяне и извличане на елементи от опашката тя се движи към края на масива. В даден момент краят на опашката достига до последния индекс на масива и се оказва, че размерът на масива не е достатъчен въпреки, че опашката не запълва всичките му елементи. За да се реши този проблем при следващото добавяне на елемент в края на опашката, той се поставя на началния индекс на масива. По този начин се свързват началото и края на масива, и опашката може да обикаля безкрайно в него. Ако дължината на опашката (броя на елементите в нея) стане равна на предварително заделения брой на елементи в масива няма да могат да бъдат добавяни нови елементи. Това налага копиране на опашката в нов масив с по-голям размер.
Динамична реализация
Примери за използване на опашка
Източници
- ↑ http://en.wikipedia.org/wiki/Queue_(abstract_data_type)
- ↑ Наков, Светлин, Веселин Колев и колектив. Въведение в програмирането със C#. Велико Търново, Фабер, 2011. ISBN 978-954-400-527-6. с. 1116.