Follow

Follow

Geeky Girl
·Dec 7, 2022·

# 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

• 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

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

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