Implement Queue using Linked List

Problem

Implement a Queue using Linked List. A Query Q is of 2 Types

• 1 x (a query of this type means pushing 'x' into the queue)
• 2 (a query of this type means to pop an element from the 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: n the first testcase
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 2 2 2 1 3 
Output: 2 -1
Explanation: In the second testcase 
1 2 the queue will be {2}
2   poped element will be {2} then
    the queue will be empty. 
2   the queue is empty and hence -1
1 3 the queue will be {3}.

Your task:

Complete the function push() which takes an integer as input parameter and pop() which will remove and return an element(-1 if queue is empty).

• Expected Time Complexity: $O(1)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^5$
• $0<=a[i]<=10^5$

Solution

Python

def __init__(self):
    self.stack1 = []  
    self.stack2 = []     

def push(self, item): 
    self.stack1.append(item)

def pop(self):
    if not self.stack2:  
        while self.stack1:
            self.stack2.append(self.stack1.pop())
    if self.stack2:
        return self.stack2.pop()
    else:
        return -1

Java

public MyQueue() {
    this.front = null;
    this.rear = null;
}

void push(int a) {
    QueueNode newNode = new QueueNode(a);
    if (this.rear == null) {
        this.front = newNode;
        this.rear = newNode;
    } 
    else {
        this.rear.next = newNode;
        this.rear = newNode;
    }
}

int pop() {
    if (this.front == null)
        return -1; 
    int poppedValue = this.front.data;
    this.front = this.front.next;
    if (this.front == null)
        this.rear = null; 
    return poppedValue;
}

C++

void MyQueue:: push(int x) {
    QueueNode* newNode = new QueueNode(x);
    if (rear == nullptr) {
        front = newNode;
        rear = newNode;
    } 
    else {
        rear->next = newNode;
        rear = newNode;
    }
}

int MyQueue :: pop() {
    if (front == nullptr)
        return -1; 
    int poppedValue = front->data;
    QueueNode* temp = front;
    front = front->next;
    delete temp;
    if (front == nullptr)
        rear = nullptr; 
    return poppedValue;      
}

C

void push(struct Queue* q, int k) {
    struct Node* newnode = newNode(k);
    if (q->rear == NULL) {
        q->front = q->rear = newnode;
        return;
    }
    q->rear->next = newnode;
    q->rear = newnode;
}

void pop(struct Queue* q) {
    if (q->front == NULL)
        return -1; 
    struct Node* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL)
        q->rear = NULL;
    free(temp);
}

• Time Complexity: $O(1)$
• Auxiliary Space: $O(1)$