Skip to main content

Implement Queue using array

Problem​

Implement a Queue using an Array. Queries in the Queue are of the following type:

  • 1 x (a query of this type means pushing 'x' into the queue)
  • 2 (a query of this type means to pop element from queue and print the poped element)

Examples:​

Example 1:

Input:
Q = 5
Queries = 1 2 1 3 2 1 4 2
Output: 2 3
Explanation:
In the first test case for query
1 2 the queue will be {2}
1 3 the queue will be {2 3}
2 poped element will be 2 the
queue will be {3}
1 4 the queue will be {3 4}
2 poped element will be 3

Example 2:

Input:
Q = 4
Queries = 1 3 2 2 1 4
Output: 3 -1
Explanation:
In the second testcase for query
1 3 the queue will be {3}
2 poped element will be 3 the
queue will be empty
2 there is no element in the
queue and hence -1
1 4 the queue will be {4}.
  • Expected Time Complexity: O(1)O(1) for both push() and pop()
  • Expected Auxiliary Space: O(1)O(1) for both push() and pop()

Constraints:​

  • 1≤Q≤1051 ≤ Q ≤ 10^5
  • 0≤x≤1050 ≤ x ≤ 10^5

Solution​

Python​

def __init__(self):
self.q = []

def push(self, x):
self.q.append(x)

def pop(self):
if self.q:
return self.q.pop(0)
else:
return -1

Java​

void push(int x) {
if (rear == arr.length) {
return;
}
arr[rear] = x;
rear++;
}

int pop() {
if (front == rear) {
return -1;
}
int element = arr[front];
for (int i = 0; i < rear - 1; i++) {
arr[i] = arr[i + 1];
}
rear--;
return element;
}

C++​

void MyQueue :: push(int x) {
if ((rear + 1) % 100005 == front) {
return;
}
arr[rear] = x;
rear = (rear + 1) % 100005;
}

int MyQueue :: pop() {
if (front == rear) {
return -1;
}
int element = arr[front];
front = (front + 1) % 100005;

return element;
}

C​

void push(struct MyQueue *queue, int x) {
if ((queue->rear + 1) % MAX_SIZE == queue->front) {
return;
}
queue->arr[queue->rear] = x;
queue->rear = (queue->rear + 1) % MAX_SIZE;
}

int pop(struct MyQueue *queue) {
if (queue->front == queue->rear) {
printf("Queue is empty. Cannot pop element.\n");
return -1;
}
int element = queue->arr[queue->front];
queue->front = (queue->front + 1) % MAX_SIZE;
return element;
}
  • Time Complexity: O(1)O(1) for both push() and pop()
  • Auxiliary Space: O(1)O(1) for both push() and pop()