借鉴别人的思路:
思路主旨:不牺牲任何1个存储空间
不浪费1个空间,但这样需要对队列状态的判断进行额外的处理。
首先明确定义:
head和tail的定义,head指向出队元素,tail指向即将入队元素的前一个位置
出队 先出队,再head+1 (若先head+1,再出队,那么必然会造成一个空间的浪费)
入队 先tail+1,再入队
在以上前提下,再去考虑设计队列状态的判断。
队满:tail+1后 发现tail==head,即(tail+1)%size==head,队满
队 空:??
出现了问题,发现队空的状态无法判断,假设head==tail,根据定义,tail指向下一个入队元素的前一个位置,head指向即将出队的元素,那么这种情况说明队列出有1个元素。
那么如何判断队列为空?
解决方案是给队列为空设置一个特殊的初始状态,即令head=tail=-1.这样设计的好处是1特征明显,好判断2.元素入队的时候好操作,tail+1自动指向了正确的0索引,只需要对head作下操作即可。
有了队空状态的解决方案后,那么整体设计方案也就出来了
定义:head,tail同上
初始化:head=tail=-1,size
入队:判队满,看是否失败;然后判对空,若为空队,需要队head指针单独进行处理(head=0)。最后执行入队逻辑。
出队:判队空,看是否失败;判是否仅有一个元素(head==tail),是的话执行出队操作后,令head=tail=-1;
队满:(tail+1)%size==head
队空:head==-1;
自己思路的关键点:
取余法实现循环
牺牲了一个存储空间来区分队列是空还是满
判空 head==tail
判满 (tail+1)%size==head
入队 先判断是否队满,然后tail后移,存入
出对 先判断是否队空,然后head后移,出队
class MyCircularQueue {
private:
vector<int> data;
int head,tail,size;
public:
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k) {
size=k+1;
data=vector<int>(k+1,0);
tail=head=0;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
if(isFull())
return false;
tail=(tail+1)%size;
data[tail]=value;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
if(isEmpty())
return false;
head=(head+1)%size;
return true;
}
/** Get the front item from the queue. */
int Front() {
if(isEmpty())
return -1;
int n=(head+1)%size;
return data[n];
}
/** Get the last item from the queue. */
int Rear() {
if(isEmpty())
return -1;
return data[tail];
}
/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
return head==tail;
}
/** Checks whether the circular queue is full or not. */
bool isFull() {
return (tail+1)%size==head;
}
};
网友评论