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
1
2
3
4
5
6
7
8
9
10
|
MyCircularDeque circularDeque = new MycircularDeque(3);
circularDeque.insertLast(1);
circularDeque.insertLast(2);
circularDeque.insertFront(3);
circularDeque.insertFront(4);
circularDeque.getRear();
circularDeque.isFull();
circularDeque.deleteLast();
circularDeque.insertFront(4);
circularDeque.getFront();
|
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.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
private int[] queue;
private int front;
private int rear;
private int size;
public (int k) {
queue = new int[k];
front = 0;
rear = -1;
size = 0;
}
public boolean insertFront(int value) {
if (!isFull()) {
if (isEmpty()) {
front = 0;
rear = 0;
}
else
front = (front - 1 + queue.length) % queue.length;
queue[front] = value;
size++;
return true;
}
return false;
}
public boolean insertLast(int value) {
if (!isFull()) {
rear = (++rear) % queue.length;
queue[rear] = value;
size++;
return true;
}
return false;
}
public boolean deleteFront() {
if (!isEmpty()) {
front = (++front) % queue.length;
size--;
return true;
}
return false;
}
public boolean deleteLast() {
if (!isEmpty()) {
rear = (rear - 1 + queue.length) % queue.length;
size--;
return true;
}
return false;
}
public int getFront() {
if (isEmpty())
return -1;
return queue[front];
}
public int getRear() {
if (isEmpty())
return -1;
return queue[rear];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == queue.length;
}
|
近期评论