> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/queue.md).

# Queue

## 1.Introduction 

* Add the end of queue and remove elements from the beginning of the queue (**F**irst **I**n **F**irst **O**ut)
* Enqueue: Adding a new element to the end of the queue
* Dequeue: Removing an element from the beginning of a queue
* Peek
* Offer: Adding to a queue if space is available

## 2.The complexity

* Enqueue, dequeue, isEmpty, isFull: O(1)
* space complexity: O(N)

## 3.Where can stacks be used

* Customer service hotline, calls are assigned to representatives in the order that they are received
* Queueing jobs to be printed
* Any order processing systems like in e-commerce websites or bank transaction systems 

## 4.Implement a queue using two stacks

* [x]  [232. Implement Queue using Stacks](https://jenhsuan.gitbook.io/algorithm/leetcode/232.-implement-queue-using-stacks)​

### Forward stack

* Use a forward stack used to push the enqueue elements
  * Enqueue operations are always performed on the forward stack
* Enqueue requires moving all elements to the forward stack and pushing the last element in I.E. the top

### Reverse stack

* The reverse stack holds the elements in reverse order from the forward stack
  * Dequeue operations are always performed on the reverse stack
* Dequeue requires moving all elements to the reverse track and popping the last element in I.E. the top

### Performance and complexity

* All enqueues and then dequeues ate O(1) - if only one of these operations are performed
* O(m)

```
public class QueueBuiltWithTwoStacks<T> {
    private Stack<T> forwardStack = new Stack();
    private Stack<T> reverseStack = new Stack();
    
    public QueueBuiltWithTwoStacks() {
    }
    
    public boolean isEmpty() {
        return forwardStack.isEmpty() && forwardStack.isEmpty();
    }
    
    public boolean isFull() {
        return forwardStack.isFull() || forwardStack.isFull();
    }
    
    public void enqueue(T data) throws Queue.QueueOverflowException {
        if (isFull()) {
            throw new QueueOverflowException();
        }
        
        try {
            if (forwardStackStack.isEmpty()) {
                while (!reverseStack.isEmpty()) {
                    forwardStack.push(reverseStack.pop());
                }
            }
            forwardStack.push(data);
        } catch(Stack.StackOverflowException | Stack.StackUnderflowException se) {
            throw new Queue.QueueOverflowException
        }
    }
    
    public T dequeue throws Queue.QueueUnderflowException {
        if (isEmpty()) {
            throw new QueueUnderflowException();
        }
        
        try {
            if (reverseStack.isEmpty()) {
                while (!forwardStack.isEmpty()) {
                    reverseStack.push(reverseStack.pop());
                }
            }
            return reverseStack.push(data);
        } catch(Stack.StackOverflowException | Stack.StackUnderflowException se) {
            throw new Queue.QueueUnderflowException
        }
    }
    
}
```

## 5.The circular queue

```
public class Queue<T> {
    private static final int SPECIAL_EMPTY_VALUE = -1;
    private static int MAX_SIZE = 40;
    private T[] elements;
    
    private int headIndex = SPECIAL_EMPTY_VALUE;
    private int tailIndex = SPECIAL_EMPTY_VALUE;
    public class Queue<T>(Class<T> clazz) {
        elements = (T[]) Array.newInstance(class, MAX_SIZE);
    }
    
    public boolean isEmpty() {
        return headIndex == SPECIAL_EMPTY_VALUE;
    }
    
    public boolean isFull() {
        int nextIndex = (tailIndex + 1) % elements.length;
        return nextIndex == headIndex;
    }
    
    public void enqueue(T data) throws QueueOverflowException {
        if (isFull()) {
            throw new QueueOverflowException();
        }
        tailIndex = (tailIndex + 1) % elements.length;
        elements[tailIndex] = data;
        
        if (headIndex == SPECIAL_EMPTY_VALUE) {
            headIndex = tailIndex;
        }
    }
    
    public void dequeue(T data) throws QueueUnderflowException {
        if (isFull()) {
            throw new QueueUnderflowException();
        }
        
        T data = elements[headIndex];
        
        if (headIndex == tailIndex) {
            headIndex = SPECIAL_EMPTY_VALUE;
        } else {
            headIndex = (headIndex + 1) % elements.length;
        }
        
        return data;
    }
}
```