Understanding Queues in Programming
A queue is a fundamental data structure in computer science that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Think of it like a line of people waiting for a service - the first person to join the line is the first to be served.
Basic Operations
Queues support two primary operations:
- Enqueue: Add an element to the back of the queue.
- Dequeue: Remove the front element from the queue.
Additionally, queues often include these helper operations:
- Front or Peek: View the front element without removing it.
- isEmpty: Check if the queue is empty.
- Size: Get the number of elements in the queue.
Implementation in Java
Here's a basic implementation of a queue in Java using a LinkedList:
import java.util.LinkedList;
public class Queue<T> {
private LinkedList<T> queue;
public Queue() {
queue = new LinkedList<>();
}
public void enqueue(T item) {
queue.addLast(item);
}
public T dequeue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
return queue.removeFirst();
}
public T front() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
return queue.getFirst();
}
public boolean isEmpty() {
return queue.isEmpty();
}
public int size() {
return queue.size();
}
}
Implementation in C++
Here's a similar implementation in C++ using a deque:
#include <deque>
#include <stdexcept>
template <typename T>
class Queue {
private:
std::deque<T> queue;
public:
void enqueue(T item) {
queue.push_back(item);
}
T dequeue() {
if (isEmpty()) {
throw std::runtime_error("Queue is empty");
}
T item = queue.front();
queue.pop_front();
return item;
}
T front() {
if (isEmpty()) {
throw std::runtime_error("Queue is empty");
}
return queue.front();
}
bool isEmpty() {
return queue.empty();
}
int size() {
return queue.size();
}
};
Common Interview Problems
1. Implement Stack using Queues
Problem: Implement a last-in-first-out (LIFO) stack using only two queues.
Java Solution:
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
private Queue<Integer> q1;
private Queue<Integer> q2;
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
public void push(int x) {
q2.offer(x);
while (!q1.isEmpty()) {
q2.offer(q1.poll());
}
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
}
public int pop() {
if (empty()) {
throw new IllegalStateException("Stack is empty");
}
return q1.poll();
}
public int top() {
if (empty()) {
throw new IllegalStateException("Stack is empty");
}
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
}
C++ Solution:
#include <queue>
#include <stdexcept>
class MyStack {
private:
std::queue<int> q1;
std::queue<int> q2;
public:
MyStack() {}
void push(int x) {
q2.push(x);
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
std::queue<int> temp = std::move(q1);
q1 = std::move(q2);
q2 = std::move(temp);
}
int pop() {
if (empty()) {
throw std::runtime_error("Stack is empty");
}
int val = q1.front();
q1.pop();
return val;
}
int top() {
if (empty()) {
throw std::runtime_error("Stack is empty");
}
return q1.front();
}
bool empty() {
return q1.empty();
}
};
Explanation: In both implementations, we use two queues to simulate a stack. When pushing an element, we add it to the empty queue (q2) and then transfer all elements from q1 to q2. This reverses the order of elements, making the most recently added element at the front of q1. For pop and top operations, we simply work with q1.
2. Design Circular Queue
Problem: Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO principle and the last position is connected back to the first position to make a circle.
Java Solution:
class MyCircularQueue {
private int[] data;
private int front;
private int rear;
private int size;
public MyCircularQueue(int k) {
data = new int[k];
front = -1;
rear = -1;
size = 0;
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
if (isEmpty()) {
front = 0;
}
rear = (rear + 1) % data.length;
data[rear] = value;
size++;
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
if (size == 1) {
front = -1;
rear = -1;
} else {
front = (front + 1) % data.length;
}
size--;
return true;
}
public int Front() {
if (isEmpty()) {
return -1;
}
return data[front];
}
public int Rear() {
if (isEmpty()) {
return -1;
}
return data[rear];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == data.length;
}
}
C++ Solution:
class MyCircularQueue {
private:
vector<int> data;
int front;
int rear;
int size;
public:
MyCircularQueue(int k) : data(k), front(-1), rear(-1), size(0) {}
bool enQueue(int value) {
if (isFull()) {
return false;
}
if (isEmpty()) {
front = 0;
}
rear = (rear + 1) % data.size();
data[rear] = value;
size++;
return true;
}
bool deQueue() {
if (isEmpty()) {
return false;
}
if (size == 1) {
front = -1;
rear = -1;
} else {
front = (front + 1) % data.size();
}
size--;
return true;
}
int Front() {
if (isEmpty()) {
return -1;
}
return data[front];
}
int Rear() {
if (isEmpty()) {
return -1;
}
return data[rear];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == data.size();
}
};
Explanation: In both implementations, we use an array to implement the circular queue. The front and rear pointers keep track of the first and last elements. When we reach the end of the array, we wrap around to the beginning using the modulo operator. This allows us to use the array space efficiently.
3. Sliding Window Maximum
Problem: Given an array nums and a sliding window of size k moving from the very left of the array to the very right, return the maximum element in each window.
Java Solution:
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] r = new int[n-k+1];
int ri = 0;
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
// remove numbers out of range k
if (!q.isEmpty() && q.peek() < i - k + 1) {
q.poll();
}
// remove smaller numbers in k range as they are useless
while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
q.pollLast();
}
// q contains index... r contains content
q.offer(i);
if (i >= k - 1) {
r[ri++] = nums[q.peek()];
}
}
return r;
}
}
C++ Solution:
#include <vector>
#include <deque>
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> dq;
for (int i = 0; i < nums.size(); i++) {
// Remove indices that are out of the current window
if (!dq.empty() && dq.front() == i - k) {
dq.pop_front();
}
// Remove indices of all elements smaller than the current one
while (!dq.empty() && nums[dq.back()] < nums[i]) {
dq.pop_back();
}
dq.push_back(i);
// If we have a window of size k, add to results
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
};
Explanation: In both Java and C++ solutions, we use a deque (double-ended queue) to solve this problem efficiently. The deque stores indices of numbers in the current window. We maintain the deque so that it always contains the indices of the maximum element at the front. As we slide the window, we remove indices that are out of the window range and smaller elements that are no longer useful. This allows us to find the maximum in each window in O(1) time, resulting in an overall O(n) solution.
These problems demonstrate the versatility of queues in solving various computational problems, especially those involving ordered processing and sliding window techniques.