---
# System prepended metadata

title: Revision - Queue

---

# Revision - Queue
## Introduction
A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. In a Queue, elements are added at the rear and removed from the front.

## Basic Operations
enqueue(element): Adds an element to the rear of the queue.
dequeue(): Removes and returns the element at the front of the queue.
isEmpty(): Checks if the queue is empty.
front(): Returns the element at the front of the queue without removing it.
rear(): Returns the element at the rear of the queue without removing it.

```
int arr[MAX_SIZE];
int frontIndex = -1, rearIndex = -1;

bool isEmpty() {
    return frontIndex == -1 && rearIndex == -1;
}

bool isFull() {
    return rearIndex == MAX_SIZE - 1;
}

void enqueue(int element) {
    if (isFull()) {
        cout << "Queue is full" << endl;
    } else if (isEmpty()) {
        frontIndex = rearIndex = 0;
        arr[rearIndex] = element;
    } else {
        rearIndex++;
        arr[rearIndex] = element;
    }
}

int dequeue() {
    if (isEmpty()) {
        cout << "Queue is empty" << endl;
        return -1;
    } else if (frontIndex == rearIndex) {
        int element = arr[frontIndex];
        frontIndex = rearIndex = -1;
        return element;
    } else {
        int element = arr[frontIndex];
        frontIndex++;
        return element;
    }
}

int front() {
    if (isEmpty()) {
        cout << "Queue is empty" << endl;
        return -1;
    } else {
        return arr[frontIndex];
    }
}

int rear() {
    if (isEmpty()) {
        cout << "Queue is empty" << endl;
        return -1;
    } else {
        return arr[rearIndex];
    }
}
```

## Implementing a Queue with 2 Stacks
We can implement a queue using two stacks. The idea is to use one stack for enqueue operation and the other stack for dequeue operation.

When an element is enqueued, we push it onto the first stack. When an element is dequeued, we first check if the second stack is empty. If it is, we pop all the elements from the first stack and push them onto the second stack. This reverses the order of elements so that the first element in the queue becomes the top element of the second stack. We can then pop the top element from the second stack to dequeue an element.

### Code
```
stack<int> s1; // First stack for enqueue operation
stack<int> s2; // Second stack for dequeue operation
    
void enqueue(int element) {
    s1.push(element);
}

int dequeue() {
    if (s2.empty()) {
        if (s1.empty()) {
            cout << "Queue is empty" << endl;
            return -1;
        } else {
            while (!s1.empty()) {
                int element = s1.top();
                s1.pop();
                s2.push(element);
            }
        }
    }
    int element = s2.top();
    s2.pop();
    return element;
}

bool isEmpty() {
    return s1.empty() && s2.empty();
}

int front() {
    if (s2.empty()) {
        if (s1.empty()) {
            cout << "Queue is empty" << endl;
            return -1;
        } else {
            while (!s1.empty()) {
                int element = s1.top();
                s1.pop();
                s2.push(element);
            }
        }
    }
    return s2.top();
}

int rear() {
    if (s1.empty()) {
        cout << "Queue is empty" << endl;
        return -1;
    }
    return s1.top();
}
```

* Define two stacks: s1 for enqueue operation and s2 for dequeue operation.
* To enqueue an element, push it onto s1.
* To dequeue an element, first check if s2 is empty. If it is, pop all the elements from s1 and push them onto s2. This will reverse the order of elements so that the first element in the queue becomes the top element of s2.
* Pop the top element from s2 to dequeue an element.
* To check if the queue is empty, check if both s1 and s2 are empty.
* To get the front element of the queue, first check if s2 is empty. If it is, pop all the elements from s1 and push them onto s2. Then, return the top element of s2.
* To get the rear element of the queue, simply return the top element of s1.

Note that this solution maintains the order of elements in the queue by reversing the order of elements only when necessary, i.e., when dequeuing an element or getting the front element. This reduces the time complexity of these operations to O(n) in the worst case, where n is the number of elements in the queue.