# 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: LRUAlso Linear Queue is generally used to implement other algorithms, majorly

**Sliding window**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.

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