# Queue

### Stack (LIFO)

```java
Deque<> stack = new ArrayDeque<>();
```

Method Summary: empty(), peek(), pop(), push(E item), search(Object o)

\
offer(0)=offerLast(0):\
push(0)=\
push == addFirst\
pop == removeFirst

### FIFO

```java
 LinkedList<Integer> fifo = new LinkedList();
 Queue<Integer> fifo = new LinkedList();
```

add,offer (add tail)\
peek (peek head)\
remove,poll (remove head)

### Heap

#### Priority Queue

```java
Arrays.sort(intervals, (u1,u2) -> u1.start-u2.start);
//may overflow
PriorityQueue<Interval> heap=new PriorityQueue<>(intervals.length,(a,b)->a.end-b.end);
//no overflow
PriorityQueue<Interval> heap=new PriorityQueue<>((a,b)->a.val<b.val?-1:1);

PriorityQueue<Trie> result = new PriorityQueue<>((a, b) -> {
        if (a.time != b.time) return b.time - a.time;
        return a.word.compareTo(b.word);
    });

PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
    @Override
    public int compare(ListNode o1,ListNode o2){
        if (o1.val<o2.val)
            return -1;
        else if (o1.val==o2.val)
            return 0;
        else 
            return 1;
    }
});
```

#### Time Complexity of Priorityqueue

remove() -> This is to remove the head/root, it takes O(logN) time.\
remove(Object o) -> This is to remove an arbitrary object. Finding this object takes O(N) time, and removing it takes O(logN) time.

#### Heap + Map

1. sort by key &#x20;

   TreeSet(), can also find ceiling(E e), floor(E e) &#x20;
2. sort by value &#x20;

   \`\`\`java

   Map.Entry entry = new AbstractMap.SimpleEntry(#,#);

   Map map = new HashMap<>();

   PriorityQueue> pq = new PriorityQueue<>(a,b->a.getValue()-b.getValue());

//add Map.Entry to hashmap first and then priority queue for(Map.Entry entry: map.entrySet()){ pq.add(entry); } pq.addAll(map.entrySet());

````
---
### List of List
```java
List<List<Integer>> res = new ArrayList<>();//correct
List<List<Integer>> res = new ArrayList<List<>>();//Wrong
````

## Reverse linked list within a range

### Example

```java
1 -> 2 -|> 3 -> 4 -> 5 -|> 6, input: node 2, nodeNum = 3, return: node 6
1 -> 2 -|> 5 -> 4 -> 3 -|> 6
```

### Solution

```java
public ListNode reverse(ListNode preHead, int nodeNum) {
    // @input: reverse the nodeNum of nodes after preHead
    // @return: the first node right of the reversed area or null
    ListNode preNode = preHead.next;
    if(preNode == null) return null;
    ListNode curNode = preNode.next;
    if(nodeNum==0) return preNode;
    if(nodeNum==1) return curNode;
    for(int i=0; i<nodeNum-1 && curNode!=null; i++) {
        ListNode tmp = curNode.next;
        curNode.next = preNode;
        preNode = curNode;
        curNode = tmp;
    }
    preHead.next.next = curNode;
    preHead.next = preNode;
    return curNode;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://psyshell.gitbook.io/coding/coding-notes/style-java/queue.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.