在上一篇文章中我们讲了线性表，并介绍了线性表的两种实现也就是顺序表与链表，这篇文章我们来介绍一下队列这种数据结构。
不论是队列还是栈，都是对线性表进行一些操作上的限制，队列是从尾进从头出的，也就是先进先出。
队列也有两种实现的方式，顺序队列与链队列。
顺序队列
顺序队列就是利用顺序存储结构实现的队列，下面我们来介绍一下具体实现:
1.结构体定义：
typedef struct queue { int *data; //数据域 int front,rear,length; //队首队尾标志,队列最大长度 }Queue;
2.队列初始化:
void init(Queue *q,int length) { q->data = (int*)malloc(sizeof(int) * length); //申请数据空间 q->front = 0; //队首标志置0,指向第一个元素 q->rear = -1; //队尾指针置-1,便于入队的操作 q->length = length; //获取队列最大长度 }
3.顺序队列的简单应用:
1)判断队是否为空:
int empty(Queue *q) { return q->front > q->rear; //如果队首标志大于队尾标志则说明队空，返回1，否则返回0 }
2)入队:
int push(Queue *q,int x) { if(q->rear + 1 >= q->length) //如果队尾标志加1大于或等于最大队列长度,则证明队列已经满了,不能再继续入队 { printf("queue is full,can't insert element %d ",x); return 0; } q->rear++; //队尾标志右移 q->data[q->rear] = x; //元素入队 return 1; }
3)出队:
int pop(Queue *q) { int rem_element = q->data[q->front]; //获取并保存队首元素 q->front++; //队首标志右移,表示元素已出队 return rem_element; //返回队首元素 }
4)返回队首元素:
int get_front_element(Queue *q) { return q->data[q->front]; }
5)获取当前队列长度:
int get_queue_length(Queue *q) { return q->rear - q->front + 1; }
4.销毁队列:
void destory_queue(Queue *q) { free(q->data); free(q); }
链队列
上面介绍了顺序存储的队列，下面我们来介绍一下链式存储的队列:
1.结点与指针的定义:
typedef struct ptr { Queue *front,*rear; //队首,队尾指针 int length; //当前队列长度 }QueuePtr;
2.初始化:
void init(QueuePtr *q) { q->front = (Queue*)malloc(sizeof(Queue)); //申请队头结点 q->rear = q->front; // 初始化队首与队尾指针 q->front->next = NULL; //对头结点指针置空 }
3.链队列的简单应用
1)入队:
void push(QueuePtr *q,int x) { Queue *s = (Queue*)malloc(sizeof(Queue)); //申请一个新的结点 s->data = x; s->next = NULL; q->rear->next = s; //尾插法 q->rear = s; q->length++; //更新当前队列长度 }
2)出队:
int pop(QueuePtr *q) { if(q->front == q->rear) //判断队空 { printf("queue is empty! "); return 0; } int rem_element = q->front->next->data; //要出队的元素 Queue *p = q->front; q->front = q->front->next; //头指针后移 free(p); q->length--; //更新当前队列长度 return rem_element; }
3)返回队首元素:
int get_front_element(QueuePtr *q) { if(q->front == q->rear) { printf("queue is empty! "); return 0; } return q->front->next->data; }
4)获取当前队长:
int get_length(QueuePtr *q) { if(q->front == q->rear) { printf("queue is empty! "); return 0; } return q->length; }
5)打印队列:
void print_queue(QueuePtr *q) { Queue *p = q->front->next; while(p != NULL) { printf("%d ",p->data); p = p->next; } putchar(' '); }
4.销毁队列:
void destroy_queue(QueuePtr *q) //销毁队列 { while(q->front != NULL) //从头结点开始释放队列中所有结点 { q->rear = q->front->next; free(q->front); q->front = q->rear; } }
队列还有其他很多形式如循环队列，双端队列，优先队列等，在后面会有专题介绍。