881357. Queue Push & Pop
Queue Push & Pop
Summary
Implement a queue data structure with push and pop operations. The queue should have a fixed capacity, and when it's full, new elements can be added only if the oldest element is removed first.
Detailed Explanation
The problem requires us to implement a queue data structure that has two primary operations: push and pop. A queue is a First-In-First-Out (FIFO) data structure, meaning that the first element added to the queue will be the first one to be removed. Our queue also has a fixed capacity, which means that when it's full, we can only add new elements if the oldest element is removed first.
To solve this problem, we can use an array-based implementation of a queue. Here's a step-by-step breakdown of our solution:
- Initialize the queue with a fixed capacity
size. - The
pushoperation adds an element to the end of the queue. - If the queue is full (i.e., its size is equal to the capacity), we need to remove the oldest element from the front of the queue before adding the new element.
- The
popoperation removes the oldest element from the front of the queue.
Here's a simple ASCII art diagram illustrating our queue:
| E1 | E2 | ... | Ek-1 | Ek |
+---+
^ (front)
|
+---+
Queue
In this diagram, E1 to Ek-1 represent the elements in the queue, and Ek is the oldest element at the front of the queue. The ^ symbol indicates the front of the queue.
The time complexity of our solution is O(1) for both push and pop operations, since we only need to check if the queue is full or not. The space complexity is O(size), where size is the capacity of the queue.
Optimized Solutions
Java
class Queue {
private int size;
private int front;
private int rear;
private Object[] elements;
public Queue(int capacity) {
size = 0;
front = 0;
rear = 0;
elements = new Object[capacity];
}
public void push(Object element) {
if (size == elements.length) {
// Remove oldest element from the front
elements[front] = null;
front = (front + 1) % elements.length;
}
elements[rear] = element;
rear = (rear + 1) % elements.length;
size++;
}
public Object pop() {
if (size == 0) {
return null; // Queue is empty
}
Object element = elements[front];
front = (front + 1) % elements.length;
size--;
return element;
}
}