Authored by Tony Feng
Created on March 22nd, 2022
Last Modified on March 23rd, 2022
Understanding Queues
Main Concepts
- Queue is an abstract data structure that is similar to stacks. Unlike stacks, a queue is open at both ends.
- First In First Out (FIFO)
Different Types
- Singly-ended Queue (All queues mentioned in this file are this type.)
- Doubly-ended Queue
Operations
- Access - O(N)
- Search - O(N)
- Insert - O(1)
- A queue can only be inserted from the rear.
- Delete - O(1)
- A queue can only be removed from the front.
Queue Implementation in Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
# Create
queue = deque()
# Add an element - O(1)
queue.append(1)
queue.append(2)
queue.append(3) # [1,2,3]
# Get the head of the queue - O(1)
head = queue[0]
# Remove the head of the queue - O(1)
head = queue.popleft()
# Get the size of the queue - O(1)
length = len(queue)
# Traverse the queue - O(N)
while len(queue) != 0:
tmp = queue.popleft()
print(tmp)
|
Queue Implementation in Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
// Create
Queue<Integer> q = new LinkedList<>();
// Add - O(1)
q.add(1);
q.add(2);
q.add(3);
// Get the head of the queue - O(1)
int elem = q.peek(); // 1
// Remove the head of the queue - O(1)
int id = q.poll(); // 1
// Get the size of the queue - O(1)
int len = q.size()
// Traverse the queue - O(N)
while (!q.isEmpty()) {
int tmp = q.poll()
System.out.println(tmp)
}
|
Reference