数据结构系列--队列

“ 队列是一种特殊的线性表。

  队列仅在线性表的头部和尾部进行操作

    队头（Front）：取出元素的一端

    队尾（Rear）：插入元素的一端

队列通常有两种实现方式

    顺序结构实现

    链式结构实现。

队列应用

    打印机队列

    广度优先搜索”

队列的基本定义及实现

 

 

 

队列是一种特殊的线性表。

队列仅在线性表的两端并进行操作

    队头（Front）：取出元素的一端

    队尾（Rear）：插入元素的一端

队列不允许在中间部位操作

#include <iostream> using namespace std; const int maxn = 5; int q[maxn],tail= 0,,head= 0;// 指针赋值为0，队列初始化 void push (int x)// x进队尾部进行操作 { q[tail]= x; tail=(tail+1)%maxn;// 解决队列假满问题 } int pop() { int x = q[head];// 先取队首删除元素 head=(head+1)%maxn; } bool isEmpty()// 判空 {return head == tail;} bool isPull()// 判空 {return tail+1 == head;}// 判满 int main() { //1 2 3 push(1); push(2); cout<< pop(); return 0; }

---

队列的顺序存储实现

SeqQueue.h

#ifndef _SEQQUEUE_H_ #define _SEQQUEUE_H_ typedef void SeqQueue;// 数据封装 SeqQueue* SeqQueue_Create(int capacity); void SeqQueue_Destory(SeqQueue* queue); void SeqQueue_Clear(SeqQueue* queue); int SeqQueue_Append(SeqQueue* queue,void* item);// 插入 void SeqQueue_Retrieve(SeqQueue* queue);// 取回元素 void SeqQueue_Header(SeqQueue* queue); int SeqQueue_Length(SeqQueue* queue); int SeqQueue_Capacity(SeqQueue* queue); #endif

SeqQueue.c

#include "SeqList.h" #include "SeqQueue.h" SeqQueue* SeqQueue_Create(int capacity) {return SeqList_Create(capacity);} void SeqQueue_Destory(SeqQueue* queue) {SeqList_Destory(queue);} void SeqQueue_Clear(SeqQueue* queue) {SeqList__Clear(queue);} int SeqQueue_Append(SeqQueue* queue,void* item)// 在尾部插入 {return SeqList_Insert(queue,item,SeqList_Length(queue));} void SeqQueue_Retrieve(SeqQueue* queue)// 在队列头部拿走元素o(n) {return SeqList_Delete(queue,0);} void SeqQueue_Header(SeqQueue* queue) {return SeqList_Get(queue,0);} int SeqQueue_Length(SeqQueue* queue) {return SeqList_Length(queue);} int SeqQueue_Capacity(SeqQueue* queue) {return SeqList_Capacity(queue);}

main.c

#include <stdio.h> #inclkude <stdlib.h> #include "SeqQueue.h" int main(int argc,char *argv[]) { SeqQueue* queue = SeqQueue_Create(20); int a[10] = {0};// 定义数组方便测试 int i= 0 ; for (i=0;i<10;i++)// 数组元素插入队列 { a[i] = i+1; SeqQueue_Append(queue,a + i); } printf("Header: %d\n",*(int*)SeqQueue_Header(queue)); printf("Length: %d\n",*(int*)SeqQueue_Length(queue)); printf("Capacity: %d\n",*(int*)SeqQueue_Capacity(queue)); while(SeqQueue_Length(queue) > 0）// 队列逐个元素取出 { printf("Retrieve: %d\n",*(int*)SeqQueue_Retrieve(queue)); } SeqQueue_Destory(queue); return 0; }

---

队列优化链式储存实现

 

LinkQueue.h

#ifndef _LINKQUEUE_H_ #define _LINKQUEUE_H_ typedef void LinkQueue; LinkQueue* LinkQueue_Create(); void LinkQueue_Destory(LinkQueue* queue); void LinkQueue_Clear(LinkQueue* queue); int LinkQueue_Append(LinkQueue* queue,void* item);// 插入 void LinkQueue_Retrieve(LinkQueue* queue);// 取回元素 void LinkQueue_Header(LinkQueue* queue); int LinkQueue_Length(LinkQueue* queue); #endif

LinkQueue.c.

#include <malloc.h> #include "LinkList.h" #include "LinkQueue.h" typedef struct _tag _LinkQueueNode // 结构体第一个成员是 LinkListNode { LinkListNode header; void* item; }TLinkListNode; LinkQueue* LinkQueue_Create() {return LinkList_Create();} void LinkQueue_Destory(LinkQueue* queue) { LinkQueue_Clear(queue);// 与链式栈实现原理一致，为了释放结构体所占的空间，逐个释放 LinkList_Destory(queue); } void LinkQueue_Clear(LinkQueue* queue)// o(n) {// 队列里每个元素附加的空间释放掉，这样不会产生内存泄漏 while(LinkQueue(queue) > 0) { LinkQueue_Retrieve(queue); } } int LinkQueue_Append(LinkQueue* queue,void* item)// 插入o(n) { TLinkListNode* node = (TLinkQueueNode*malloc(sizeof(TLinkQueueNode)); int ret = (item !=NULL) && (node !=NULL);// 队列不为空且申请队空间不为空 if (ret) { node >item = item; ret = LinkList_Insert(queue,(TLinkQueueNode*)node,LinkList_Length(queue,0); // 插到队列尾部 } if (!ret)// 没插入成功，释放申请的node { free(node); } return ret; } void LinkQueue_Retrieve(LinkQueue* queue)// 取回元素 { TLinkQueueNode* node = (TLinkQueueNode*)LinkList_Delete(queue,0); void* ret = NULL; if (node != NULL) { ret = node->item;// 真正队列元素返回 free(node);// 在append中申请的空间释放掉 } return ret; } void LinkQueue_Header(LinkQueue* queue) { TLinkQueueNode* node = (TLinkQueueNode*)LinkList_Get(queue,0); void* ret = NULL; if (node != NULL) { ret = node->item; } return ret; } int LinkQueue_Length(LinkQueue* queue) {return LinkList_Length(queue);} #endif

main.c

#include <stdio.h> #inclkude <stdlib.h> #include "SeqQueue.h" int main(int argc,char *argv[]) { LinkQueue* queue = LinkQueue_Create(20); int a[10] = {0};// 定义数组方便测试 int i= 0 ; for (i=0;i<10;i++)// 数组元素插入队列 { a[i] = i+1; LinkQueue_Append(queue,a + i); } printf("Header: %d\n",*(int*)LinkQueue_Header(queue)); printf("Length: %d\n",*(int*)LinkQueue_Length(queue)); while(LinkQueue_Length(queue) > 0）// 队列逐个元素取出 { printf("Retrieve: %d\n",*(int*)LinkQueue_Retrieve(queue)); } LinkQueue_Destory(queue); return 0; }

---