# 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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/queue.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.