1. Опашката може да се дефинира като подреден списък, който позволява операциите за вмъкване да се изпълняват в единия край, наречен ЗАДНА и операции за изтриване, които трябва да бъдат извършени в друг извикан край ПРЕДНА .
2. Опашката се нарича списък „Първи влезли, първи излезли“.
3. Например хората, чакащи на опашка за железопътен билет, образуват опашка.
Приложения на Queue
Поради факта, че опашката изпълнява действия на принципа първи влязъл, първи излязъл, което е доста справедливо за подреждането на действията. Има различни приложения на опашките, разгледани по-долу.
- Опашките се използват широко като списъци на чакащи за един споделен ресурс като принтер, диск, процесор.
- Опашките се използват при асинхронно прехвърляне на данни (където данните не се прехвърлят с еднаква скорост между два процеса), напр. тръби, файл IO, гнезда.
- Опашките се използват като буфери в повечето приложения като MP3 медиен плейър, CD плейър и др.
- Опашката се използва за поддържане на списъка за изпълнение в медийните плейъри, за да се добавят и премахват песните от списъка за изпълнение.
- Опашките се използват в операционните системи за обработка на прекъсвания.
Сложност
| Структура на данни | Времева сложност | Космическа пълнота | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Средно аритметично | Най-лошото | Най-лошото | |||||||
| Достъп | Търсене | Вмъкване | Изтриване | Достъп | Търсене | Вмъкване | Изтриване | ||
| Опашка | i(n) | i(n) | аз (1) | аз (1) | На) | На) | О(1) | О(1) | На) |