1 题目理解

要求设计一个双端循环队列。这个队列能支持以下操作： MyCircularDeque(k): Constructor, set the size of the deque to be k. insertFront(): Adds an item at the front of Deque. Return true if the operation is successful. insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful. deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful. deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful. getFront(): Gets the front item from the Deque. If the deque is empty, return -1. getRear(): Gets the last item from Deque. If the deque is empty, return -1. isEmpty(): Checks whether Deque is empty or not. isFull(): Checks whether Deque is full or not.

2 思路

再次来做的时候完全没有想法，参考了答案后回过头看自己的队列文章发现思路就在文章的循环队列里面讲明白了。 重点理解： 1 front表示第一个数字有效的位置， tail表示最有一个有效数字位置的下一位，也可以理解为要插入一个元素时候的位置。这两个变量的含义不能变。 2 队列为空的条件：front =tail 3 队列满的条件：(tail+1)%capacity=0，是要空出一个位置的。

class MyCircularDeque { private int capacity ; private int[] values; private int front; private int rear; /** Initialize your data structure here. Set the size of the deque to be k. */ public MyCircularDeque(int k) { this.values = new int[k+1]; this.capacity = k+1; } /** Adds an item at the front of Deque. Return true if the operation is successful. */ public boolean insertFront(int value) { if(isFull()) return false; front = front == 0? capacity-1 :(front-1); values[front] = value; return true; } /** Adds an item at the rear of Deque. Return true if the operation is successful. */ public boolean insertLast(int value) { if(isFull()) return false; values[rear] = value; rear = (rear+1)%capacity; return true; } /** Deletes an item from the front of Deque. Return true if the operation is successful. */ public boolean deleteFront() { if(isEmpty()) return false; front = (front+1)%capacity; return true; } /** Deletes an item from the rear of Deque. Return true if the operation is successful. */ public boolean deleteLast() { if(isEmpty()) return false; rear = rear==0? capacity-1: rear-1; return true; } /** Get the front item from the deque. */ public int getFront() { return !isEmpty()?values[front]:-1; } /** Get the last item from the deque. */ public int getRear() { return !isEmpty()?values[rear>0?rear-1:capacity-1]:-1; } /** Checks whether the circular deque is empty or not. */ public boolean isEmpty() { return front == rear; } /** Checks whether the circular deque is full or not. */ public boolean isFull() { return (rear+1)%capacity==front; } }