Concept

Definition

• 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?

• Note that since queue = DLL as we can access both ends. All DLL questions are basically queue questions.
  eg: LRU

• Also Linear Queue is generally used to implement other algorithms, majorly

  • Sliding window

    • https://leetcode.com/problems/number-of-recent-calls/

    • https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/

    • Note that we may also use unordered_set/map to implement the same . In Fact this is the preferred method.

  • Level order traversal

  • BFS

• To do things in order of arrival

  • https://www.interviewbit.com/problems/first-non-repeating-character-in-a-stream-of-characters/

  • LRU is also a similar example

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>{

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

• When to use?

  • Maintain elements in sorted fashion while iterating (Similar to a Set).

  • Difference is that you are only maintaining top K elements OR Reduce space complexity to O(k) OR Reduce time complexity to N log K.

    • https://leetcode.com/problems/kth-largest-element-in-an-array/

    • https://www.interviewbit.com/problems/magician-and-chocolates/

  • Note that: All priority queue questions are basically set questions. Even the O(K) questions can be done using a set of size K.

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 !!