單回圈佇列
-
q ：用陣列來記錄資料
-
cap：代表陣列的長度
-
len：代表元素的個數，取尾部元素可以根據頭元素指標和這個值來進行計算
(queue->head+queue->len)%queue->cap ，
取余是為了在規定范圍內回圈使用有限空間
-
head：頭元素的指標
-
出隊：出頭元素只需要將head往前移動即可，注意也要取余， 同時len需要減一
-
入隊：入隊只需要賦值給 (queue->head+queue->len)%queue->cap位置的值即可，同時 len++，也就是說 tail=(queue->head+queue->len)%queue->cap) 永遠指向尾部元素的后一個待賦值的位置
#include <iostream>
using namespace std;
struct Queue{
int* q;
int cap;
int len;
int head;
};
Queue* Create(int cap){
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->q = (int*)calloc(cap,sizeof(int));
queue->len=0;
queue->cap=cap;
queue->head=0;
return queue;
}
bool isFull(Queue* queue){
return queue->cap==queue->len;
}
bool isEmpty(Queue* queue){
return queue->len==0;
}
bool enQueue(Queue* queue,int val){
if(isFull(queue))
return false;
queue->q[(queue->head+queue->len)%queue->cap] = val;
queue->len++;
return true;
}
int deQueue(Queue* queue){
if(isEmpty(queue))
return -1;
int r = queue->q[queue->head];
queue->head = (queue->head+1)%queue->cap;
queue->len--;
return r;
}
int Front(Queue* queue){
if(isEmpty(queue))
return -1;
return queue->q[queue->head] ;
}
int Rear(Queue* queue){
if(isEmpty(queue))
return -1;
return queue->q[(queue->head+queue->len-1)%queue->cap];
}
int main(int argc, char *argv[])
{
Queue* queue = Create(4);
enQueue(queue,1);
enQueue(queue,2);
enQueue(queue,3);
cout<<enQueue(queue,4)<<endl;
cout<<enQueue(queue,5)<<endl;
cout<<"----------------\n";
cout<<deQueue(queue)<<endl;
cout<<deQueue(queue)<<endl;
cout<<Rear(queue)<<" "<<Front(queue)<<endl;
return 0;
}
雙端回圈佇列
- head：指向頭元素指標
- tail：指向尾部元素的后一個待賦值的位置
- q：資料陣列指標
- length：元素個數
- N：陣列容量， 比設定的容量大一
為什么N不設定為cap，因為需要留一個位置判斷隊滿
-
左入：head永遠指向左邊的頭元素，head向左移動，(queue->head-1+queue->N)%queue->N ，然后賦值，+N是為了防止出席那負數
-
左出：head向右移動，(queue->head+1+queue->N)%queue->N，
-
右入：賦值 然后tail向右移動， (queue->tail+1+queue->N)%queue->N，為什么tail先賦值，因為tail永遠指向右邊尾元素的下一個待賦值的元素的位置，
-
右出：tail向左移動，(queue->tail-1+queue->N)%queue->N;
-
判滿：因為開辟佇列的時候多留了一個位置，所以如果 ((queue->tail+1)%queue->N)==queue->head，則佇列滿了
-
判空：因為剛開始 tail=head=0，所以是空的，如果在移動的程序中出現空了，也就是說 head追上了tail的位置，就代表佇列空了
#include <iostream>
#include <limits.h>
using namespace std;
#define SIZE 5
struct Dequeue{
int head;
int tail;
int N; //為啥多一個 因為%運算之后能達到SIZE， 比如4 那么只能到3
int* q;
int length;
};
Dequeue* Create(int k){
Dequeue* queue = (Dequeue*)malloc(sizeof(Dequeue));
queue->head=0;
queue->tail=0;
queue->length=0;
queue->q = (int*)calloc(queue->N,sizeof(int));
queue->N = k+1;
return queue;
}
bool isEmpty(Dequeue* queue){
return queue->head==queue->tail;
}
bool isFull(Dequeue* queue){
return ((queue->tail+1)%queue->N)==queue->head;
}
bool Lpush(Dequeue* queue,int val){
if(isFull(queue))
return false;
queue->head = (queue->head-1+queue->N)%queue->N;
queue->q[queue->head] = val;
return true;
}
bool Rpush(Dequeue* queue,int val){
if(isFull(queue))
return false;
queue->q[queue->tail] = val;
queue->tail = (queue->tail+1+queue->N)%queue->N;
return true;
}
int Lpop(Dequeue* queue){
if(isEmpty(queue))
return -1;
int r = queue->q[queue->head];
queue->head = (queue->head+1+queue->N)%queue->N;
return r;
}
int Rpop(Dequeue* queue){
if(isEmpty(queue))
return -1;
queue->tail = (queue->tail-1+queue->N)%queue->N;
return queue->q[queue->tail];
}
int getFront(Dequeue* queue){
if(isEmpty(queue))
return -1;
return queue->q[queue->head];
}
int getRear(Dequeue* queue){
if(isEmpty(queue))
return -1;
return queue->q[(queue->tail-1+queue->N)%queue->N];
}
int main(int argc, char *argv[])
{
Dequeue* q = Create(4);
Lpush(q,1);
Lpush(q,2);
Rpush(q,3);
Rpush(q,4);
cout<<Lpop(q)<<endl;
cout<<Rpop(q)<<endl;
cout<<Lpop(q)<<endl;
cout<<Rpop(q)<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57200.html
標籤：其他
上一篇：滑動視窗的最大值