此篇为实现双端队列过程中遇到的问题和想法 |
---|
#双端队列
##双端队列的线性队列
1.我们首先要解决的东西是从左(右)进队既能从左出还能从右出的策
1 #include"h_Public.h"
2
3 #define MaxSize 4
4
5 typedef struct Squeue{
6 int data[MaxSize];
7
8 int Front,Rear;
9 }Squeue;
10
11 int InitQueue(Squeue *P){
12 P->Front = 0;P->Rear = 1;
13 return 1;
14 }
以上是定义代码和初始化代码,为什么是0和1因为我们的目标是让他们两个无论在任何时候都能顺利访问对方的区域,画个圆环就能理解;
16 int isEmpty(Squeue *P){
17 if(P->Front+1 == P->Rear){
18 printf("1此队列是空的\n");
19 return 1;
20 }else{
21 printf("2次队列非空\n");
22 return 0;
23 }
24 }
25
26 int isFull(Squeue *P){
27 if(P->Rear == P->Front){
28 printf("3此队列满了\n");
29 return 1;
30 }else{
31 // printf("4此队列是非满的\n");
32 return 0;
33 }
34 }
这个判空是思想是放弃一个存储空间的思想;
36 int LPush(Squeue *P,int x){
37 if(isFull(P)==1){
38 printf("===5此队列为满\n===");
39 return 0;
40 }else{
41 P->data[P->Front] = x;
42 P->Front = (P->Front-1)%MaxSize;
43 return 1;
44 }
45 }
46
47 int RPush(Squeue *P,int x){
48 if(isFull(P)==1){
49 printf("=6=此队列为满\n==");
50 return 0;
51 }else{
52 P->data[P->Rear] = x;
53 P->Rear = (P->Rear+1)%MaxSize;
54 return 1;
55 }
56 }
这个是写入用的,分左右,也是画个图就能理解;
58 int LPop(Squeue *P){
59 if(isEmpty(P)==1){
60 printf("==7队列为空==\n");
61 return 0;
62 }else{
63 int x=0;
64 P->Front = (P->Front+1)%MaxSize;
65 x = P->data[P->Front];
66 return x;
67 }
68 }
69
70 int RPop(Squeue *P){
71 if(isEmpty(P)==1){
72 printf("==队8列为空==\n");
73 return 0;
74 }else{
75 int x = 0;
76 P->Rear = (P->Rear-1)%MaxSize;
77 x = P->data[P->Rear];
78 return x;
79 }
80 }
出去的函数;
但是写完之后发现出现了些问题,比如-1%4在c语言里结果是-1并不是我们想得到3,所以我们需要写另外一个函数满足我们的运算,此运算规则如下:
-1%6 = 5;但是上述代码思想应该是对的;