Уикипедия

Опашка (абстрактен тип данни): Разлика между версии

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
мРедакция без резюме
lang-en, категория, нови редове ,<br>; форматиране: 13x интервали (ползвайки Advisor.js)
Ред 1:
{{без категория}}
 
[[Файл:QUEUE-FIFO.jpg|рамка|вдясно|Схема на структурата опашка, добавяне и извличане на елементи.]]
'''Опашката''' (англ. ''''{{lang-en|Queue''''}}) в програмирането е вид [[абстрактна структура от данни]] и е представител на абстрактните типове данни ([[АТД]]). Опашките спадат към линейните (списъчни) структури от данни, заедно със [[Списък (програмиране)|списъците]] и [[стек (структура от данни)|стековете]]. Опашката представлява крайно, линейно множество от елементи, при което елементи се добавят само най-отзад (enqueue) и се извличат само най-отпред (dequeue). Абстрактната структура опашка изпълнява условието "първият влязъл първи излиза" (FIFO: First-In-First-Out). Това означава, че след като е добавен един елемент в края на опашката, той ще може да бъде извлечен (премахнат) единствено след като бъдат премахнати всички елементи преди него в реда, в който са добавени.
 
Структурата опашка и поведението на нейните елементи произхождат от ежедневната човешка дейност. Например опашка от хора, чакащи на каса за билети. Опашката има начало и край. Новодошлите хора застават последни на опашката и изчакват докато постепенно се придвижат към началото. Когато стигнат до самото начало на опашката си купуват билет и напускат опашката. Други примери за опашка са документи, чакащи да бъдат отпечатани или ескалатор превозващ хора. По този начин опашката изпълнява функцията на буфер.
 
== Статична реализация ==
[[Файл:QUEUE-STATIC.jpg|рамка|вдясно|Циклично движение на опашка в масив.]]
Статичната опашка се реализира с помощта на [[Масив (програмиране)|масив]]. В даден момент началото и краят на опашката сочат към определени индекси от масива. Когато се добавя нов елемент той се поставя на индекса след края на опашката и краят вече сочи към новия елемент. Когато се премахва началото на опашката, елементът на началния индекс се изтрива и началото започва да сочи към следващия индекс. По този начин с добавяне и извличане на елементи от опашката тя се движи към края на масива. В даден момент краят на опашката достига до последния индекс на масива и се оказва, че размерът на масива не е достатъчен въпреки, че опашката не запълва всичките му елементи. За да се реши този проблем при следващото добавяне на елемент в края на опашката, той се поставя на началния индекс на масива. По този начин се свързват началото и края на масива, и опашката може да обикаля безкрайно в него. В началото индексите за начало и край сочат нулевия елемент. В процеса, ако отново се окажат равни това може да означава две неща:<br />
:- ако равенството се е получило след премахване на елемент, опашката е останала празна.<br />
:- ако равенството се е получило след добавяне на елемент, то опашката е препълнена.<br />
 
В този случай дължината на опашката (броя на елементите в нея)е станала равна на предварително заделения брой на елементи и в масива няма да могат да бъдат добавяни нови елементи. Това налага копиране на опашката в нов масив с по-голям размер.
 
== Динамична реализация ==
[[Файл:QUEUE-DYNAMIC.jpg|рамка|вдясно]]
При динамичната реализация на опашката елементите не се намират в последователни адреси на паметта, както е при реализацията с масиви. При динамичните структури всеки елемент от опашката съдържа две части - обект и указател към следващия елемент. По този начин се образува свързан списък. Известен е адресът на първия елемент в опашката, а адресите на всички останали елементи не са достъпни директно. Достъпът до тях се осъществява като се премине през указателите на всички предшестващи елементи. Последния елемент в опашката има указател, който не сочи към друг елемент, докато не се добави нов елемент накрая. Тогава указателят на елемента, който досега е бил последен започва да сочи към новия елемент. Указателят на новия елемент не сочи към елемент, докато не бъде добавен нов елемент и т.н. В началото на опашката е елементът, който вече може да бъде извлечен. Към този елемент няма насочен указател.
 
Съществува и вариант, при който указателите на елементите сочат и към предишния, и към следващия елемент на опашката(когато съществуват такива). Тогава списъкът е двойно свързан (или двусвързан). Така опашката може при нужда да бъде обхождана и в двете посоки.
 
== Допустими операции с опашки ==
•'''Създаване на празна опашка''' – опашка която не
Line 53 ⟶ 56:
}
 
// Пример 2
for (int i = 0; i < 10; i++)
{
Line 75 ⟶ 78:
Console.ReadKey();
Console.WriteLine("Next element: " + stringQueue.Dequeue()); // извличане на следващия елемент след като е натиснат клавиш
}
}
}
Line 110 ⟶ 113:
Пример за употреба на опашка в [[C++]]
<source lang="cpp">
 
#include <stdio.h>
#include <stdlib.h>
 
#define M 100
 
typedef float ElementType;
 
struct Queue
{
Line 123 ⟶ 126:
ElementType QueueArray[M];
};
 
void pushq(struct Queue *q, ElementType x)
{
Line 144 ⟶ 147:
return q->QueueArray[q->f];
}
 
void main()
{
struct Queue mem = {0, 0}; //създаване на празна опашка
ElementType y = 3.14f;
 
 
int i;
for(i = 1; i <= 99; i++)
pushq(&mem, y+=1.1f);
 
for(i = 1; i <= 99; i++)
printf("%.2f ", popq(&mem));
Line 165 ⟶ 168:
{
}
 
$movies = new MoviesList(); //Създаване на опашката
 
Line 181 ⟶ 184:
* Преслав Наков, Панайот Добриков. [http://www.programirane.org/ Програмиране = ++Алгоритми;]. TopTeam Co., София, 2002. ISBN 954-8905-06-X. с.149.
<references />
 
[[Категория:Програмиране]]
Взето от „https://bg.wikipedia.org/wiki/Опашка_(абстрактен_тип_данни)“.