顺序队列 - 循环队列 - 链队列

1.顺序队列：队列是只能在线性表的一端删除（队头），在线性表的另一 端插入的特殊线性表;

2.通常对头指针q->front总是指向对头元素的前一个位置；

3.而队尾指针q->rear总是指向对为元素；

4.顺序队列的结构体定义： tyopedef struct { int data[MAXSIXE]; int front,rear; }Sequeue;

5.Sequeue *q = (Sequeue *)malloc(sizeof(Sequeue));

(1)队空：q->front = q->rear = -1; 队空时出队为上溢；

(2)队满：q->rear = MAXSIZE – 1（q->data[0]~q->data[1]）;

(3)队中元素的个数：(q->rear)-(q->front);

(4)队尾入队： q->rear++; q->data[q->rear] = value;

(5)队头出队并赋值给X： q->front++; x=q->data[q->front];

顺序队列的假溢出现象：q->front != -1; q->rear = MAXSIZE-1

（出队元素空间无法再利用造成）

循环队列的实现过程：

#include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 typedef struct { int data[MAXSIZE]; int front,rear; }CriQuence; //修改队列的地址，传双重地址 void init(CriQuence **q) { *q = (CriQuence *)malloc(sizeof(CriQuence)); (*q)->front = 0; (*q)->rear = 0; } //入队 判断队满 void insertQ(CriQuence *p,int value) { if((p->rear + 1)%MAXSIZE == p->front) { printf("Quence is full\n"); }else{ p->rear=(p->rear+1)%MAXSIZE; p->data[p->rear] = value; printf("%d\n",p->data[p->rear]); } } //出栈 判栈空 void popQ(CriQuence *p,int *x) { if(p->rear == p->front) { printf("Quence is empty\n"); }else{ p->front = (p->front+1)%MAXSIZE; *x = p->data[p->front]; printf("%d\n",*x); } } void emptyQ(CriQuence *q) { if(q->rear == q->front) { printf("empty Quence!\n"); } } int main(int argc,char **argv) { int x = 0; int value = 5; CriQuence *q = NULL; init(&q); insertQ(q,value); popQ(q,&x); emptyQ(q); return 0; }

链队列：

#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *next; }Qnode; //通常将链队列的头指针和尾指针放在一个结构体中 typedef struct { Qnode *front,*rear; }LQnode; //传指针地址可修改链表指针地址下的所有内容 void init(LQnode **p) { *p = (LQnode *)malloc(sizeof(LQnode)); Qnode *q = (Qnode *)malloc(sizeof(Qnode)); //申请链表头结点 q->next = NULL; (*p)->front = q; (*p)->rear = q; } //判队空 void empty_LQuence(LQnode *q) { if(q->front = q->rear) { printf("the LQnode is empty\n"); // return 1; } } //入队 void pushQ(LQnode *q,int value) { Qnode *p = (Qnode *)malloc(sizeof(Qnode)); p->data = value; p->next = NULL; q->rear->next = p; q->rear = p; printf("%d\n",p->data); } //出队(判队空) 删除头结点后的第一个结点 void popQ(LQnode *q,int *x) { if(q->rear != q->front) { Qnode *p = q->front->next; //p指向第一个有效结点 q->front->next = p->next; *x = p->data; free(p); printf("%d\n",*x); } } int main(int argc,char **argv) { int x = 0; LQnode *p = NULL; init(&p); empty_LQuence(p); pushQ(p,5); popQ(p,&x); empty_LQuence(p); return 0; }