设计
队列
数组
链表
题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k)
: 构造器,设置队列长度为 k 。
Front
: 从队首获取元素。如果队列为空,返回 -1 。
Rear
: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value)
: 向循环队列插入一个元素。如果成功插入则返回真。
deQueue()
: 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty()
: 检查循环队列是否为空。
isFull()
: 检查循环队列是否已满。
示例:
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false,队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
提示:
所有的值都在 0 至 1000 的范围内;
操作数将在 1 至 1000 的范围内;
请不要使用内置的队列库。
解法
方法一
Python3 Java C++ Go TypeScript Rust
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 class MyCircularQueue :
def __init__ ( self , k : int ):
self . q = [ 0 ] * k
self . front = 0
self . size = 0
self . capacity = k
def enQueue ( self , value : int ) -> bool :
if self . isFull ():
return False
idx = ( self . front + self . size ) % self . capacity
self . q [ idx ] = value
self . size += 1
return True
def deQueue ( self ) -> bool :
if self . isEmpty ():
return False
self . front = ( self . front + 1 ) % self . capacity
self . size -= 1
return True
def Front ( self ) -> int :
return - 1 if self . isEmpty () else self . q [ self . front ]
def Rear ( self ) -> int :
if self . isEmpty ():
return - 1
idx = ( self . front + self . size - 1 ) % self . capacity
return self . q [ idx ]
def isEmpty ( self ) -> bool :
return self . size == 0
def isFull ( self ) -> bool :
return self . size == self . capacity
# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()
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 class MyCircularQueue {
private int [] q ;
private int front ;
private int size ;
private int capacity ;
public MyCircularQueue ( int k ) {
q = new int [ k ] ;
capacity = k ;
}
public boolean enQueue ( int value ) {
if ( isFull ()) {
return false ;
}
int idx = ( front + size ) % capacity ;
q [ idx ] = value ;
++ size ;
return true ;
}
public boolean deQueue () {
if ( isEmpty ()) {
return false ;
}
front = ( front + 1 ) % capacity ;
-- size ;
return true ;
}
public int Front () {
if ( isEmpty ()) {
return - 1 ;
}
return q [ front ] ;
}
public int Rear () {
if ( isEmpty ()) {
return - 1 ;
}
int idx = ( front + size - 1 ) % capacity ;
return q [ idx ] ;
}
public boolean isEmpty () {
return size == 0 ;
}
public boolean isFull () {
return size == capacity ;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
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 class MyCircularQueue {
private :
int front ;
int size ;
int capacity ;
vector < int > q ;
public :
MyCircularQueue ( int k ) {
capacity = k ;
q = vector < int > ( k );
front = size = 0 ;
}
bool enQueue ( int value ) {
if ( isFull ()) return false ;
int idx = ( front + size ) % capacity ;
q [ idx ] = value ;
++ size ;
return true ;
}
bool deQueue () {
if ( isEmpty ()) return false ;
front = ( front + 1 ) % capacity ;
-- size ;
return true ;
}
int Front () {
if ( isEmpty ()) return -1 ;
return q [ front ];
}
int Rear () {
if ( isEmpty ()) return -1 ;
int idx = ( front + size - 1 ) % capacity ;
return q [ idx ];
}
bool isEmpty () {
return size == 0 ;
}
bool isFull () {
return size == capacity ;
}
};
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue* obj = new MyCircularQueue(k);
* bool param_1 = obj->enQueue(value);
* bool param_2 = obj->deQueue();
* int param_3 = obj->Front();
* int param_4 = obj->Rear();
* bool param_5 = obj->isEmpty();
* bool param_6 = obj->isFull();
*/
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 type MyCircularQueue struct {
front int
size int
capacity int
q [] int
}
func Constructor ( k int ) MyCircularQueue {
q := make ([] int , k )
return MyCircularQueue { 0 , 0 , k , q }
}
func ( this * MyCircularQueue ) EnQueue ( value int ) bool {
if this . IsFull () {
return false
}
idx := ( this . front + this . size ) % this . capacity
this . q [ idx ] = value
this . size ++
return true
}
func ( this * MyCircularQueue ) DeQueue () bool {
if this . IsEmpty () {
return false
}
this . front = ( this . front + 1 ) % this . capacity
this . size --
return true
}
func ( this * MyCircularQueue ) Front () int {
if this . IsEmpty () {
return - 1
}
return this . q [ this . front ]
}
func ( this * MyCircularQueue ) Rear () int {
if this . IsEmpty () {
return - 1
}
idx := ( this . front + this . size - 1 ) % this . capacity
return this . q [ idx ]
}
func ( this * MyCircularQueue ) IsEmpty () bool {
return this . size == 0
}
func ( this * MyCircularQueue ) IsFull () bool {
return this . size == this . capacity
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* obj := Constructor(k);
* param_1 := obj.EnQueue(value);
* param_2 := obj.DeQueue();
* param_3 := obj.Front();
* param_4 := obj.Rear();
* param_5 := obj.IsEmpty();
* param_6 := obj.IsFull();
*/
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 class MyCircularQueue {
private queue : number [];
private left : number ;
private right : number ;
private capacity : number ;
constructor ( k : number ) {
this . queue = new Array ( k );
this . left = 0 ;
this . right = 0 ;
this . capacity = k ;
}
enQueue ( value : number ) : boolean {
if ( this . isFull ()) {
return false ;
}
this . queue [ this . right % this . capacity ] = value ;
this . right ++ ;
return true ;
}
deQueue () : boolean {
if ( this . isEmpty ()) {
return false ;
}
this . left ++ ;
return true ;
}
Front () : number {
if ( this . isEmpty ()) {
return - 1 ;
}
return this . queue [ this . left % this . capacity ];
}
Rear () : number {
if ( this . isEmpty ()) {
return - 1 ;
}
return this . queue [( this . right - 1 ) % this . capacity ];
}
isEmpty () : boolean {
return this . right - this . left === 0 ;
}
isFull () : boolean {
return this . right - this . left === this . capacity ;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* var obj = new MyCircularQueue(k)
* var param_1 = obj.enQueue(value)
* var param_2 = obj.deQueue()
* var param_3 = obj.Front()
* var param_4 = obj.Rear()
* var param_5 = obj.isEmpty()
* var param_6 = obj.isFull()
*/
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 struct MyCircularQueue {
queue : Vec < i32 > ,
left : usize ,
right : usize ,
capacity : usize ,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MyCircularQueue {
fn new ( k : i32 ) -> Self {
let k = k as usize ;
Self {
queue : vec ! [ 0 ; k ],
left : 0 ,
right : 0 ,
capacity : k ,
}
}
fn en_queue ( & mut self , value : i32 ) -> bool {
if self . is_full () {
return false ;
}
self . queue [ self . right % self . capacity ] = value ;
self . right += 1 ;
true
}
fn de_queue ( & mut self ) -> bool {
if self . is_empty () {
return false ;
}
self . left += 1 ;
true
}
fn front ( & self ) -> i32 {
if self . is_empty () {
return - 1 ;
}
self . queue [ self . left % self . capacity ]
}
fn rear ( & self ) -> i32 {
if self . is_empty () {
return - 1 ;
}
self . queue [( self . right - 1 ) % self . capacity ]
}
fn is_empty ( & self ) -> bool {
self . right - self . left == 0
}
fn is_full ( & self ) -> bool {
self . right - self . left == self . capacity
}
}
GitHub