რიგი (FIFO) და დეკი

რიგი მაღაზიის სალაროსთან მდგარი ხალხია. ახალი ელემენტები ბოლოში დგება, გადის კი სათავიდან. ვინც ყველაზე დიდხანს ელოდა, პირველი ემსახურება: „პირველი მოვიდა, პირველი წავიდა“ (FIFO).

C++-ში: #include <queue> და queue<int> q;. ფუნქციები სტეკისას ჰგავს:

• push(x): x-ის დამატება ბოლოში;
• pop(): სათავის ელემენტის წაშლა (არაფერს აბრუნებს);
• front() / back(): უძველესი / უახლესი ელემენტის წაკითხვა;
• size(), empty().

ყველა O(1)-ია. როგორც სტეკში, ცარიელ რიგზე front() ან pop() განუსაზღვრელი ქცევაა.

დეკი (ორბოლოიანი რიგი, #include <deque>) იძლევა push_front, push_back, pop_front და pop_back ოპერაციებს, ყველას O(1)-ში, და ინდექსით წვდომასაც d[i]. მას შეუძლია იყოს სტეკი, რიგი ან ორივე ერთად.

ორი კლასიკური გამოყენება:

• მცოცავი ფანჯრის მინიმუმი: დეკში ინდექსები ზრდადი მნიშვნელობებით ინახება; სათავეს ვაგდებთ, როცა ფანჯრიდან გადის, ბოლოს კი ვაგდებთ, სანამ ახალ ელემენტზე მეტია. ეს მონოტონური სტეკია, რომელსაც მეორე ბოლოშიც აქვს გასასვლელი.
• 0-1 BFS: გრაფებში, სადაც წიბოების წონა 0 ან 1-ია, 0-წიბოსთვის წვეროს წინ ვდებთ, 1-წიბოსთვის კი ბოლოში.

შიგნიდან std::queue და std::stack ნაგულისხმევად დეკზე აგებული თხელი გარსებია.