1. What is pair queue?

  • A queue is a special kind of linear table that can only operate at both ends
  • Tailgate: You can only add elements from the tailgate, usually called joining
  • Opponents: can only remove elements from the head of a team, usually called a team
  • The queue follows the principle of First In First Out, FIFO

2. Interface design and implementation of queue

  • Internal implementations of queues can be implemented using dynamic arrays and linked lists

  • We prefer to use bidirectional lists because queues operate mainly on elements from head to tail

    Public class Queue {private List List = new LinkedList<>(); Public int size() {return list.size(); Public Boolean isEmpty() {return list.isempty (); return list.isempty (); } // Clear elements public void clear() {// Clear elements list.clear(); } public void enQueue(E element) {list.add(element); Return list.remove(0); return list.remove(0); return list.remove(0); } public E front() {return list.get(0); }}

2.1, buckle exercise -232. Stack implementation queue

Interview questions link: leetcode-cn.com/problems/im…

Interview question:

  • Prepare two stacks: Instack holds the pushed elements. OutStack holds the elements from the inStack stack once
  • Pushing is pushing into instack
  • Out of stack: Queue is first in, first out
  • If the outStack is empty, pop all the instack elements one by one, push them to the outStack, and the outStack pops the top element
  • If the outStack is not empty, the outStack pops the top element.

Interview question code implementation

class MyQueue { private Stack<Integer> inStack; private Stack<Integer> outStack; /** Initialize your data structure here. */ public MyQueue() {// Initialize inStack, outStack inStack = new Stack<>(); outStack = new Stack<>(); } public void push(int x) {//inStack instack.push (x); If (outstack.isempty ()){// If (outstack.isempty ()){// If (outstack.isempty ()){ Instack.isempty ()){//inStack pops out of outStack outstack.push (instack.pop ()); Return outstack.pop (); return outstack.pop (); If (outstack.isempty ()){// If (outstack.isempty ()){// If (outstack.isempty ()){// If (outStack. Instack.isempty ()){//inStack pops out of outStack outstack.push (instack.pop ()); }} return outstack.peek (); Return instack.isempty () &&outStack.isempty (); return instack.isempty () &&outStack.isempty (); }}Copy the code

3. Double-endian queue

  • A double-ended queue is a queue that can be added and deleted at both the head and tail of the queue

  • Implementation of a double-ended queue:

    Public class Deque {private List List = new LinkedList<>(); Public int size() {return list.size(); } public Boolean isEmpty() {return list.isempty (); } // Clear elements public void clear() {// call list.clear(); } public void enQueueRear(E element) {list.add(element); } public E deQueueFront() {return list.remove(0); } public void enQueueFront(E element) {list.add(0, element); } public E deQueueRear() {return list.remove(list.size() -1); return list.remove(list.size() -1); Public E front() {return list.get(0); return list.get(0); Public E rear() {return list.get(list.size() -1); return list.get(list.size() -1); }}

4. Circular queue

  • A circular queue is a queue where the sequential queue is joined head to tail

  • Out and in the same queue, first in first out

  • Cyclic queue design and implementation: use dynamic array implementation

    public class CircleQueue { private int front; Private int size; Private E[] elements; Private static final int DEFAULT_CAPACITY = 10; Public CircleQueue() {// Open the queue memory elements = (E[]) new Object[DEFAULT_CAPACITY]; } public int size() {return size; } public Boolean isEmpty() {return size == 0; Public void clear() {for (int I = 0; i < size; i++) { elements[index(i)] = null; } //front = 0; //size = 0 size = 0; } public void enQueue(E element) {ensureCapacity(size + 1); // Add //size+ front = index // If index is larger than array length, Elements [index(size)] = element; elements[index(size)] = element; / / the size 1 size++; } public E deQueue() {frontElement = elements[front]; Elements [front] = null; // If the index is larger than the array length, elements. Index = index-elements. Length // If index is smaller than array length, index = index-0; / / the size minus 1 size -; // Return frontElement; Public E front() {return elements[front]; }

    Private int index(int index) {index += front; private int index(int index) {index += front; return index - (index >= elements.length ? elements.length : 0); @param capacity */ private void ensureCapacity(int capacity) {int oldCapacity = elements.length; if (oldCapacity >= capacity) return; // the newCapacity is 1.5 times the oldCapacity int newCapacity = oldCapacity + (oldCapacity >> 1); E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; Elements[I] = elements[index(I)]; newElements[I] = elements[index(I)]; } elements = newElements; // reset front front = 0; }Copy the code

    }

5. Loop double-endian queue

  • Circular double-ended queue: the head and tail of a circular queue can be deleted or added

  • A circular two-end queue is just that: an implementation of joining from the head and leaving from the back

  • The design and implementation of a circular double-ended queue:

    public class CircleDeque { private int front; private int size; private E[] elements; private static final int DEFAULT_CAPACITY = 10; public CircleDeque() { elements = (E[]) new Object[DEFAULT_CAPACITY]; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void clear() { for (int i = 0; i < size; i++) { elements[index(i)] = null; } front = 0; size = 0; } @param element/public void enQueueRear(E element) {ensureCapacity(size + 1); elements[index(size)] = element; size++; } @param element/public E deQueueFront() {E frontElement = elements[front]; elements[front] = null; front = index(1); size–; return frontElement; } @param element/public void enQueueFront(E element) {ensureCapacity(size + 1); Front = index(-1); front = index(-1); elements[front] = element; size++; } @param element */ public E deQueueRear() {// int rearIndex = index(size-1); E rear = elements[rearIndex]; Elements [rearIndex] = null; / / the size minus 1 size -; return rear; } public E front() { return elements[front]; Return elements[index(size-1)]; return elements[index(size-1)]; }

    private int index(int index) { index += front; If (index < 0) {return index + elements. Length; } return index - (index >= elements.length ? elements.length : 0); @param capacity */ private void ensureCapacity(int capacity) {int oldCapacity = elements.length; if (oldCapacity >= capacity) return; // the newCapacity is 1.5 times the oldCapacity int newCapacity = oldCapacity + (oldCapacity >> 1); E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newElements[i] = elements[index(i)]; } elements = newElements; // reset front front = 0; }}Copy the code

6, buckle exercise -225. Stack implementation with queues

Interview questions link: leetcode-cn.com/problems/im…

Method one: Two queues

In order to meet the characteristics of the stack, that is, the last element to be pushed out of the stack first, when using queues to implement the stack, the element at the front of the queue should be the last element to be pushed. Stack operations can be implemented using two queues, with Queue 1 for stack elements and Queue 2 as a secondary queue for push operations.

Stack operation, the first element of entrance to the queue 2, then all elements of the queue 1 out of the team into the team into the queue in order 2, 2 elements of the front end of the queue at this time for the new elements into the stack, then the queue and queue 1 2 swaps, The elements in Queue 1 are the elements in the stack, and the front end and back end of Queue 1 correspond to the top and bottom of the stack respectively.

Since each push ensures that the front element of Queue 1 is at the top of the stack, both the off stack and the get to the top of the stack can be easily implemented. Unstack simply removes the front end of Queue 1 and returns it, and get the top of the stack just takes the front end of Queue 1 and returns it without removing the element. Since Queue 1 is used to store the elements in the stack, you only need to check whether queue 1 is empty to determine whether the stack is empty.

class MyStack { Queue<Integer> queue1; Queue<Integer> queue2; /** Initialize your data structure here. */ public MyStack() { queue1 = new LinkedList<Integer>(); queue2 = new LinkedList<Integer>(); } /** push */ public void push(int x) {queue2.offer(x); while (! queue1.isEmpty()) { queue2.offer(queue1.poll()); } Queue<Integer> temp = queue1; queue1 = queue2; queue2 = temp; Public int pop() {return queue1.poll(); } public int top() {return queue1.peek(); } public Boolean empty() {return queue1.isempty (); }}Copy the code

Method two: a queue

When using a queue, in order to satisfy the stack characteristic that the last element to be pushed on the stack is the first, the element at the front of the queue must also be the last element to be pushed on the stack.

Stack operation, the first to get into the number of elements in the stack before n n, and then the element of entrance to the queue, then the queue first n n elements (i.e., in addition to all elements of new elements of the stack), in turn, the team into the team to the queue, queue at this time of the front element is the new elements into the stack, queue and front-end and back-end respectively corresponding to the top and bottom of the stack.

Since each push ensures that the front element of the queue is the top element, both the off stack and the get to the top element can be easily implemented. An out of the stack operation simply removes the front end of the queue and returns it, and an get to the top of the stack operation just takes the front end of the queue and returns it (without removing the element).

Since queues are used to store elements in a stack, it is only necessary to determine whether the stack is empty

Class MyStack {// Initialize the Queue<Integer> Queue; /** Initialize your data structure here. */ public MyStack() { queue = new LinkedList<Integer>(); } public void push(int x) {public void push(int x) {int n = queue.size(); / / the team queue. Offer (x); For (int I = 0; i < n; Queue. Offer (queue.poll()); // queue first in first out (fifO) is the opposite of stack. } } /** chu zhan */ public int pop() { return queue.poll(); } /** Get the top element. */ public int top() { return queue.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue.isEmpty(); }}Copy the code