Double-Ended Queue Algorithm
Initialize
1. Create a deque with size `capacity`.
2. Maintain:
- `front` pointer initialized to `-1` (empty).
- `rear` pointer initialized to `-1` (empty).
- `size` initialized to `0`.
Push to Front (`push_front(x)`)
1. Check if deque is full:
- If `size == capacity`, return "Deque is full".
2. If deque is empty (`size == 0`):
- Set `front = rear = 0`.
3. Otherwise:
- Update `front = (front - 1 + capacity) % capacity`.
4. Insert `x` at `front`.
5. Increment `size`.
Push to Rear (`push_back(x)`)
1. Check if deque is full:
- If `size == capacity`, return "Deque is full".
2. If deque is empty (`size == 0`):
- Set `front = rear = 0`.
3. Otherwise:
- Update `rear = (rear + 1) % capacity`.
4. Insert `x` at `rear`.
5. Increment `size`.
Pop from Front (`pop_front()`)
1. Check if deque is empty:
- If `size == 0`, return "Deque is empty".
2. Remove the element at `front`.
3. If deque becomes empty after removal (`size == 1`):
- Reset `front = rear = -1`.
4. Otherwise:
- Update `front = (front + 1) % capacity`.
5. Decrement `size`.
Pop from Rear (`pop_back()`)
1. Check if deque is empty:
- If `size == 0`, return "Deque is empty".
2. Remove the element at `rear`.
3. If deque becomes empty after removal (`size == 1`):
- Reset `front = rear = -1`.
4. Otherwise:
- Update `rear = (rear - 1 + capacity) % capacity`.
5. Decrement `size`.
Peek Front (`peek_front()`)
1. Check if deque is empty:
- If `size == 0`, return "Deque is empty".
2. Return the element at `front`.
Peek Rear (`peek_back()`)
1. Check if deque is empty:
- If `size == 0`, return "Deque is empty".
2. Return the element at `rear`.
Check if Empty (`is_empty()`)
1. Return `size == 0`.
Check if Full (`is_full()`)
1. Return `size == capacity`.
Traversal (`traverse()`)
1. Check if deque is empty:
- If `size == 0`, return "Deque is empty".
2. Initialize `i = front` and loop `size` times:
- Print or store `deque[i]`.
- Update `i = (i + 1) % capacity`.
Example Implementation in Python
class Deque:
def __init__(self, capacity):
self.capacity = capacity
self.size = 0
self.front = -1
self.rear = -1
self.data = [None] * capacity
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == self.capacity
def push_front(self, x):
if self.is_full():
print("Deque is full")
return
if self.is_empty():
self.front = self.rear = 0
else:
self.front = (self.front - 1 + self.capacity) % self.capacity
self.data[self.front] = x
self.size += 1
def push_back(self, x):
if self.is_full():
print("Deque is full")
return
if self.is_empty():
self.front = self.rear = 0
else:
self.rear = (self.rear + 1) % self.capacity
self.data[self.rear] = x
self.size += 1
def pop_front(self):
if self.is_empty():
print("Deque is empty")
return None
result = self.data[self.front]
if self.size == 1:
self.front = self.rear = -1
else:
self.front = (self.front + 1) % self.capacity
self.size -= 1
return result
def pop_back(self):
if self.is_empty():
print("Deque is empty")
return None
result = self.data[self.rear]
if self.size == 1:
self.front = self.rear = -1
else:
self.rear = (self.rear - 1 + self.capacity) % self.capacity
self.size -= 1
return result
def peek_front(self):
if self.is_empty():
print("Deque is empty")
return None
return self.data[self.front]
def peek_back(self):
if self.is_empty():
print("Deque is empty")
return None
return self.data[self.rear]
def traverse(self):
if self.is_empty():
print("Deque is empty")
return
i = self.front
for _ in range(self.size):
print(self.data[i], end=" ")
i = (i + 1) % self.capacity
print()
# Example Usage
deque = Deque(5)
deque.push_back(10)
deque.push_front(20)
deque.push_back(30)
deque.traverse() # Output: 20 10 30
deque.pop_front()
deque.traverse() # Output: 10 30
Example Implementation in Python
class Deque:
def __init__(self, capacity):
self.capacity = capacity
self.size = 0
self.front = -1
self.rear = -1
self.data = [None] * capacity
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == self.capacity
def push_front(self, x):
if self.is_full():
print("Deque is full")
return
if self.is_empty():
self.front = self.rear = 0
else:
self.front = (self.front - 1 + self.capacity) % self.capacity
self.data[self.front] = x
self.size += 1
def push_back(self, x):
if self.is_full():
print("Deque is full")
return
if self.is_empty():
self.front = self.rear = 0
else:
self.rear = (self.rear + 1) % self.capacity
self.data[self.rear] = x
self.size += 1
def pop_front(self):
if self.is_empty():
print("Deque is empty")
return None
result = self.data[self.front]
if self.size == 1:
self.front = self.rear = -1
else:
self.front = (self.front + 1) % self.capacity
self.size -= 1
return result
def pop_back(self):
if self.is_empty():
print("Deque is empty")
return None
result = self.data[self.rear]
if self.size == 1:
self.front = self.rear = -1
else:
self.rear = (self.rear - 1 + self.capacity) % self.capacity
self.size -= 1
return result
def peek_front(self):
if self.is_empty():
print("Deque is empty")
return None
return self.data[self.front]
def peek_back(self):
if self.is_empty():
print("Deque is empty")
return None
return self.data[self.rear]
def traverse(self):
if self.is_empty():
print("Deque is empty")
return
i = self.front
for _ in range(self.size):
print(self.data[i], end=" ")
i = (i + 1) % self.capacity
print()
# Example Usage
deque = Deque(5)
deque.push_back(10)
deque.push_front(20)
deque.push_back(30)
deque.traverse() # Output: 20 10 30
deque.pop_front()
deque.traverse() # Output: 10 30
