Queue

1.Introduction

• Add the end of queue and remove elements from the beginning of the queue (First In First Out)

• 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

• 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;
    }
}