队列

队列

1. 逻辑结构

队列(Queue)是一种线性的逻辑结构，但是：

它只允许在一端插入元素，在另一端删除元素
插入的一端称作队尾，删除的一端称为队头。
队列具有先进先出(First In Fist Out, FIFO)的特性。

2. 操作

init_queue 初始化
is_empty 判断空
is_full 判断满
enter_queue 入队列
delete_queue 出队列
get_head 取队列头部元素

3. 顺序实现(循环队列)

3.1. 存储结构

   1 #define MAXSIZE 100
   2 typedef int elem_type;
   3 struct seq_queue{
   4     elem_type elem[MAXSIZE]; //元素的存储空间
   5     int front; //第一个元素位置
   6     int rear; //最后一个元素的下一个位置
   7 };
   8 typedef struct seq_queue seq_queue;

3.2. 操作实现

初始化

   1 void init(seq_queue *q) 
   2 {
   3    q->rear = 0;
   4    q->front = 0;
   5 }

入队操作

   1 void push(seq_queue *q, elem_type e) 
   2 {
   3    q->elem[q->rear] = e;
   4    q->rear = (q->rear+1) % MAXSIZE;
   5 }

出队操作

   1 elem_type pop(seq_queue *q) 
   2 {
   3    int pos = q->front;
   4    q->front = (q->front + 1) % MAXSIZE;
   5    return q->elem[pos];
   6 }

取队首

   1 elem_type get_head() {
   2    return q->elem[q->front];
   3 }

判断是否为空

   1 bool is_empty(seq_queue *q)
   2 {
   3    return q->rear == q->front;
   4 }

判断是否满

   1 bool is_full(seq_queue *q)
   2 {
   3    return (q->rear+1)%MAXSIZE == q->front;
   4 }

4. 链式实现(单循环链表实现)

4.1. 存储结构定义

数据结构定义同带头结点的循环单链表。

   1 typedef int elem_type;
   2 struct node {
   3    elem_type data;
   4    struct node *next;
   5 };
   6 typedef struct node node;
   7 typedef struct node *link_list
   8 struct link_queue {
   9    node *front;
  10    node *rear;
  11 };
  12 typedef struct link_queue link_queue;

4.2. 操作实现

初始化

   1 void init(link_queue *q){
   2    q->front = (node*)malloc(sizeof(node));
   3    q->front->next = NULL;
   4    q->rear = q->front;
   5 }

入队

   1 void push(link_queue *q, elem_type e){
   2    node *p = (node *)malloc(sizeof(node));
   3    p->data = e;
   4    p->next = NULL;
   5    q->rear->next = p;
   6    q->rear = p;   
   7 }

出队

   1 elem_type pop(link_queue *q){
   2    node *p = q->front->next;
   3    elem_type e = p->data;
   4    q->front->next = p->next;
   5    if( q->rear == p)
   6       q->rear = q->front;
   7    free(p);
   8    return e;
   9 }

判断空

   1 int is_empty(link_queue *q) {
   2    return q->front == q->rear;
   3 }

取队首

   1 elem_type get_top(link_queue *q) {
   2    return q->front->next->data;
   3 }