链式队列----数据结构

队列的基本概念

队列是一种操作受限的线性表（先进先出），只允许在队尾插入，队头删除。

例如去银行办理业务，肯定是先来的先出去，后来的人排在后方，只有第一个人业务办理完了，才会有一个人出队列。

队列的实现

结点和指针的定义

#define MAX_SIZE 50typedef int DateElem;         //队列中的元素类型
typedef struct _QueueNode
{DateElem date;struct _QueueNode* next;  //和单链表结点的定义一样
}QueueNode; typedef QueueNode*  QueuePtr;      //可以用QueuePtr创建一个指向结点的指针typedef struct LinkQueue           //定义的是队列头、尾指针
{int length;    //存储队列的长度，因为要频繁获取长度QueuePtr head; //指向第一个结点，队头指针QueuePtr tail; //指向最后一个结点，队尾指针
}Queue;

初始化

//初始化队列
bool InitQueue(Queue* sq)
{if (!sq) return false; sq->length = 0;sq->head = NULL;     //置为空，最开始为空队列sq->tail = NULL;return true;
}

判断是否为空

bool IsEmpty(Queue* sq)
{if (!sq) return false;//头指针没有指向任何一个结点if (sq->head == NULL) //不能用 sq->head == sq->tail 来判断，因为队列只有一个元素时，头尾指针指向同一个结点，但是可以用 sq->head == sq->tail = NULL，意思是三个都相等{return true;}return false;
}

判断是否满了

bool IsFull(Queue* sq)
{if (!sq) return false;if (sq->length >= MAX_SIZE) //长度最开始为0，插入一个，长度 +1{return true;}return false;
}

插入（入队）

bool EnterQueue(Queue* sq, DateElem *e)
{if (!sq) return false;   if (IsFull(sq)) return false; //队列满了，无法继续插入QueueNode *p = new QueueNode;p->date = *e;p->next = NULL;               //因为是最后一个结点，没有直接后继if (IsEmpty(sq)) //空队列{sq->head = p;sq->tail = p;}else{//此时head指向第一个结点，tail指向最后一个结点sq->tail->next = p;sq->tail = p;          //更新tail指针}sq->length++;              //别忘记了return true;
}

删除（出队）

bool PopQueue(Queue* sq,DateElem *date)
{if (!sq || IsEmpty(sq)) return false;if (!date) return false;//此时head指向第一个结点，tail指向最后一个结点QueueNode* p = sq->head;sq->head = p->next;         //head指向第二个结点*date = p->date;            //返回删除的值delete p;//如果队列只有一个结点，而恰好刚刚删除了，也就是空队列if (IsEmpty(sq)){sq->head = NULL; //head已经为空，写一下更整齐（可以不用写）sq->tail = NULL;}sq->length--;return true;
}

打印队列

bool Print(Queue* sq)  //和链表的打印一样
{if (!sq ) return false; if (IsEmpty(sq)){cout << "队列为空" << endl;}QueueNode* p = sq->head;cout << "队列中的元素：";while (p != NULL){printf("%d ", p->date);p = p->next;}cout << endl;return true;
}

清空队列

//清空队列
bool ClearQueue(Queue* sq)
{if (!sq || IsEmpty(sq)) return false; QueueNode* p = sq->head,*q = NULL;while (p != NULL) {q = p->next;    delete p;            p = q;}sq->length = 0;sq->head = NULL;sq->tail = NULL;return true;
}

获取队头元素

bool GetHead(Queue* sq, DateElem* date)
{if (!date || !sq || IsEmpty(sq) )return false; *date = sq->head->date;   //指针返回队首元素return true;}

主函数代码

可以在主函数中测试一下刚刚实现的功能，还有一些功能可以自己去实现，比如获取队列长度。

int main(void)
{Queue* sq = new Queue ;DateElem* s = new DateElem;//1.初始化队列InitQueue(sq);for (int i = 1; i <= 7; i++){if (EnterQueue(sq, &i)){cout << "入队成功" << endl;}else{cout << "入队失败，" << i << "未插入" << endl;}}Print(sq);for (int i = 0; i < 8; i++){if (PopQueue(sq, s)){cout << "出队的元素是" << *s << endl;}else{cout << "出队失败" << endl;}Print(sq);}ClearQueue(sq);Print(sq);return 0;
}