GuilinDev

Lc0622

05 August 2008

622 Design Circular Queue

题目

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Your implementation should support following operations:

  • 1

    MyCircularQueue(k)
    : Constructor, set the size of the queue to be k.
  • 1

    Front
    : Get the front item from the queue. If the queue is empty, return -1.
  • 1

    Rear
    : Get the last item from the queue. If the queue is empty, return -1.
  • 1

    enQueue(value)
    : Insert an element into the circular queue. Return true if the operation is successful.
  • 1

    deQueue()
    : Delete an element from the circular queue. Return true if the operation is successful.
  • 1

    isEmpty()
    : Checks whether the circular queue is empty or not.
  • 1

    isFull()
    : Checks whether the circular queue is full or not.

Example:

1
2
3
4
5
6
7
8
9
10

MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
circularQueue.enQueue(1);  // return true
circularQueue.enQueue(2);  // return true
circularQueue.enQueue(3);  // return true
circularQueue.enQueue(4);  // return false, the queue is full
circularQueue.Rear();  // return 3
circularQueue.isFull();  // return true
circularQueue.deQueue();  // return true
circularQueue.enQueue(4);  // return true
circularQueue.Rear();  // 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 Queue library.

分析

可以用链表或者array实现，维护两个索引head和tail，每次入队时，tail向右移动一位；每次出队时，head向右移动一位。为了不让head和tail跑到array长度的外面去，所以用取模的方式让head和tail重新回到头部，另外额外维护一个实时的长度len方便检查是否为空或者满。

循环队列应用场景：

  • Memory Management: The unused memory locations in the case of ordinary queues can be utilized in circular queues.
  • Traffic system: In computer controlled traffic system, circular queues are used to switch on the traffic lights one by one repeatedly as per the time set.
  • CPU Scheduling: Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.
  • Lock Free Queue: When high performance is required, we don’t want to use lock. Circular Queue can is the top 1 data structure for lock free queue.

代码

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 {
    int head;
    int tail;
    int len; // 当前array实际含有的元素
    final int[] cq;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        this.head = 0; // 头部在第一个位置
        this.tail = -1; // 尾部初始化没有
        this.len = 0;
        this.cq = new int[k];
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (!isFull()) {
            tail = (tail + 1) % cq.length; // tail指针位置向后移动一位，或者去头部
            cq[tail] = value;
            len++;
            return true;
        } else return false;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (!isEmpty()) {
            head = (head + 1) % cq.length; // head指针位置向后移动一位，或者去头部
            len--;
            return true;
        } else return false;
    }
    
    /** Get the front item from the queue. */
    public int Front() {
        return isEmpty() ? -1 : cq[head];
    }
    
    /** Get the last item from the queue. */
    public int Rear() {
        return isEmpty() ? -1 : cq[tail];
    }
    
    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return len == 0;
    }
    
    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return len == cq.length;
    }
}

/**
 * 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();
 */
This site is open source. Improve this page.