Queue - Data Structure

Queue - Data Structure


2 min read



  • Linear data structure where operations are performed in First In First Out (FIFO) order.

  • FIFO: push_back, pop_front.

  • Time Complexity:

    • Access -> at O(n).

    • Deletion at O(1).

    • Searching -> O(n)

    • Insertion -> O(1)

  • For all implementation purposes: queue = list

    • It gives four operations: push_back, pop_back, pop_front, push_front

Where to use the linear queue?

Priority queue / Heap

  • Maintain elements in a sorted tree.

    • Push: O(log n)

    • Top/Pop: O(1)

    • Construction: O(N)

    • Two variants:

      • Min heap

      • Max heap

  • Can be implemented using

  • Priority queue data structure: https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/

  • Using a set since the definition ~= Set

    • begin() -> Priority queue top

    • erase() -> Priority queue pop

    • Use multiset if duplicate elements are allowed

    • Custom comparator if reverse ordering is required

bool lex_compare(const int64_t &a, const int64_t &b) 
    stringstream s1,s2;
    s1 << a;
    s2 << b;
    return s1.str() < s2.str();
set<int64_t, lex_compare> s;
class MyNameComp implements Comparator<Empl>{

    public int compare(Empl e1, Empl e2) {
        return e1.getName().compareTo(e2.getName());
TreeSet<Empl> nameComp = new TreeSet<Empl>(new MyNameComp());

So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.

Thank you, Have a nice day !!