Design your implementation of the circular double-ended queue (deque).
Your implementation should support following operations:
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.
Example:
MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3 circularDeque.insertLast(1); // return true circularDeque.insertLast(2); // return true circularDeque.insertFront(3); // return true circularDeque.insertFront(4); // return false, the queue is full circularDeque.getRear(); // return 2 circularDeque.isFull(); // return true circularDeque.deleteLast(); // return true circularDeque.insertFront(4); // return true circularDeque.getFront(); // return 4
Note:
- All values will be in the range of [0, 1000].
- The number of operations will be in the range of [1, 1000].
- Please do not use the built-in Deque library.
class MyCircularDeque { LinkedList<Integer> list; int len = 0; int le = 0; /** Initialize your data structure here. Set the size of the deque to be k. */ public MyCircularDeque(int k) { list = new LinkedList<Integer>(); le = k; } /** Adds an item at the front of Deque. Return true if the operation is successful. */ public boolean insertFront(int value) { if(!isFull()) { list.addFirst(value); len++; return true; } else return false; } /** Adds an item at the rear of Deque. Return true if the operation is successful. */ public boolean insertLast(int value) { if(!isFull()) { list.addLast(value); len++; return true; } else return false; } /** Deletes an item from the front of Deque. Return true if the operation is successful. */ public boolean deleteFront() { if(!isEmpty()){ list.removeFirst(); len--; return true; } return false; } /** Deletes an item from the rear of Deque. Return true if the operation is successful. */ public boolean deleteLast() { if(!isEmpty()){ list.removeLast(); len--; return true; } return false; } /** Get the front item from the deque. */ public int getFront() { if(isEmpty()) return -1; return list.peekFirst(); } /** Get the last item from the deque. */ public int getRear() { if(isEmpty()) return -1; return list.peekLast(); } /** Checks whether the circular deque is empty or not. */ public boolean isEmpty() { return len == 0; } /** Checks whether the circular deque is full or not. */ public boolean isFull() { return len == le; } } /** * Your MyCircularDeque object will be instantiated and called as such: * MyCircularDeque obj = new MyCircularDeque(k); * boolean param_1 = obj.insertFront(value); * boolean param_2 = obj.insertLast(value); * boolean param_3 = obj.deleteFront(); * boolean param_4 = obj.deleteLast(); * int param_5 = obj.getFront(); * int param_6 = obj.getRear(); * boolean param_7 = obj.isEmpty(); * boolean param_8 = obj.isFull(); */
啊这,
java的linkedlist和arraydequeue好像,都能offer/addFrist/Last,remove/poll/peekFirst/Last,用起来就很方便
用来设计这种dequeue就很方便
class MyCircularDeque { int[] queue; int front, tail; int count; /** Initialize your data structure here. Set the size of the deque to be k. */ public MyCircularDeque(int k) { queue = new int[k]; front = 0; tail = 0; count = 0; } /** 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 - 1 + queue.length) % queue.length; if (isEmpty()) { tail = front; } queue[front] = value; count++; 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; } tail = (tail + 1) % queue.length; if (isEmpty()) { front = tail; } queue[tail] = value; count++; 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) % queue.length; count--; return true; } /** Deletes an item from the rear of Deque. Return true if the operation is successful. */ public boolean deleteLast() { if (isEmpty()) { return false; } tail = (tail - 1 + queue.length) % queue.length; count--; return true; } /** Get the front item from the deque. */ public int getFront() { return isEmpty() ? -1 : queue[front]; } /** Get the last item from the deque. */ public int getRear() { return isEmpty() ? -1 : queue[tail]; } /** Checks whether the circular deque is empty or not. */ public boolean isEmpty() { return count == 0; } /** Checks whether the circular deque is full or not. */ public boolean isFull() { return count == queue.length; } }
我是啥b,不能用已有的collection的
用array,add的时候先算下一个head/tail位置,如果此时变空,就让两个相等,因为要重新开始
addFirst就是(head-1+k)%k
addLast就是(tail+1)%k