leetcode622设计循环队列

傷城~ 2022-10-05 03:59 110阅读 0赞

使用数组完成对循环队列的设计  
**空闲单元法**：进行队列是否为空，是否为满的情况；

front : 指向队列中第一个元素
    rear : 指向队列中最后一个元素的下一个位置，这个地方注意！！！

![在这里插入图片描述][20210606112900441.png]  
所有减都要有+length  
所有加都要有%length  
思路：

1.  队空条件：`front == rear;`
2.  队满条件：`front == (rear+1)%length;`
3.  队列长度：`queue_l = (rear - front +length)%length;`
4.  队头元素：`queue[front];`
5.  队尾元素：`queue[(rear-1+length)%length];`
6.  插入元素：`queue[rear]=value; rear = (rear+1)%length;`
7.  删除元素：`front = (front+1)%length;`

代码

class MyCircularQueue { 
        int * queue = nullptr;
        int front;
        int rear;
        int length;
    public:
        MyCircularQueue(int k) { 
            queue =(int *)malloc((k+1)*sizeof(int));//要比实际需要的空间多1
            front = 0;
            rear = 0;
            length = k+1;
        }
        
        bool enQueue(int value) { 
            if(isFull())
                return false;
            else 
            { 
                queue[rear]=value;
                rear = (rear+1)%length;
                return true;
            }
                
        }
        
        bool deQueue() { 
            if(isEmpty())
                return false;
            else{ 
                front = (front+1)%length;
                return true;
            }
    
        }
        
        int Front() { 
            if(!isEmpty())
                return queue[front];
            else return -1;
        }
        
        int Rear() { 
            if(!isEmpty())
            { 
                cout<<"rear = "<< rear <<endl;
                return queue[(rear-1+length)%length];
            }
                
            else return -1;
        }
        
        bool isEmpty() { 
            return front == rear;
        }
        
        bool isFull() { 
            return front == ((rear+1)%length);
        }
        void print(){ 
            int i =front;
            cout<<"print circle"<<endl;
            while(i!=rear)
            { 
                cout<<queue[i]<<" ";
                i = (i+1)%length;
            }
            cout<<endl;
        }
    };

[20210606112900441.png]: /images/20221005/8758b5ef04514e9ca75ce6d2e0da2953.png