首页 > 代码库 > 队列ADT的两种简单实现
队列ADT的两种简单实现
队列在书中说明的方式是两种，一种最简单的链表队列，判断情况比较简单，另一种是使用数组进行创建，限制较多，但是速度较快，也比较容易控制内存，不至于出现在链表实现上那么复杂的内存控制。
下面先是链表实现：
ListQueue.cpp
1 #include "iostream" 2 #include "stdlib.h" 3 4 typedef struct _queue_ 5 { 6 int data; 7 struct _queue_ *next; 8 }queue; 9 10 int isEmpty(queue *front)11 {12 if (front == nullptr)13 return 1;14 else15 return 0;16 }17 18 void enQueue(queue *&front,queue *&rear,int data)19 {20 queue *p = (queue *)malloc(sizeof(queue));21 p->data =http://www.mamicode.com/ data;22 p->next = nullptr;23 if (front == nullptr)24 {25 front = p;26 rear = p;27 return;28 }29 else30 {31 rear->next = p;32 rear = p;33 return;34 }35 }36 37 void deQueue(queue *&front, queue *&rear)38 {39 queue *tmp=nullptr;40 if (isEmpty(front))41 return ;42 if (front->next == nullptr)43 {44 free(front);45 front = nullptr;46 return;47 }48 else49 {50 tmp = front;51 front = front->next;52 tmp->next = nullptr;53 free(tmp);54 return;55 }56 }57 58 int head(queue *front)59 {60 if (isEmpty(front))61 {62 std::cout << "队列为空，返回为 ";63 return -1;64 }65 return front->data;66 }67 68 int main(void)69 {70 queue *front = nullptr;71 queue *rear = nullptr;72 enQueue(front, rear, 1);73 enQueue(front, rear, 2);74 enQueue(front, rear, 3);75 enQueue(front, rear, 4);76 enQueue(front, rear, 5);77 std::cout << head(front) << std::endl;78 deQueue(front, rear);79 std::cout << head(front) << std::endl;80 deQueue(front, rear);81 std::cout << head(front) << std::endl;82 deQueue(front, rear);83 std::cout << head(front) << std::endl;84 deQueue(front, rear);85 std::cout << head(front) << std::endl;86 deQueue(front, rear);87 std::cout << head(front) << std::endl;88 deQueue(front, rear);89 std::cout << head(front) << std::endl;90 system("pause");91 return 0;92 }
还有数组实现
ArrayQueue.cpp
1 #include "iostream" 2 #include "stdlib.h" 3 4 typedef struct _queue_ 5 { 6 int maxSize; 7 int front; 8 int rear; 9 int *Array; 10 }queue; 11 12 queue *createQueue(int maxSize) 13 { 14 queue *p = (queue *)malloc(sizeof(queue)); 15 p->Array = (int *)malloc(sizeof(int)*maxSize); 16 p->front = -1; 17 p->rear = -1; 18 p->maxSize = maxSize; 19 return p; 20 } 21 22 void enQueue(queue *q,int data) 23 { 24 if (q->rear == -1) 25 { 26 q->Array[++q->rear] = data; 27 ++q->front; 28 } 29 else 30 { 31 if ((q->rear + 1) % q->maxSize == 0)//rear到达了数组结尾 32 { 33 if (q->front > 0)//数组头位置已经没有数据 34 { 35 q->rear = 0; 36 q->Array[q->rear] = data; 37 } 38 else//还有数据 39 { 40 std::cout << "栈已满，无法入栈" << std::endl; 41 return; 42 } 43 } 44 else if (q->rear == q->front-1)//如果已经到了头游标的前一个位置，就是再添加也没有位置了 45 { 46 std::cout << "栈已满，无法入栈" << std::endl; 47 return; 48 } 49 else//排除了以上两种情况后，就可以随便插入了 50 { 51 q->Array[++q->rear] = data; 52 } 53 } 54 } 55 56 void deQueue(queue *q) 57 { 58 if (q->front == -1) 59 { 60 std::cout << "队列为空" << std::endl; 61 return; 62 } 63 else 64 { 65 if ((q->front+1)%q->maxSize==0)//如果front标在结尾 66 { 67 if (q->front == q->rear) 68 { 69 q->front = q->rear = -1; 70 } 71 else 72 { 73 q->front = 0; 74 } 75 } 76 else 77 { 78 if (q->front == q->rear) 79 { 80 q->front = q->rear = -1; 81 } 82 else 83 { 84 ++q->front; 85 } 86 } 87 } 88 } 89 90 int head(queue *q) 91 { 92 if (q->front == -1) 93 { 94 std::cout << "队列为空,返回 "; 95 return -1; 96 } 97 return q->Array[q->front]; 98 } 99 100 int main(void)101 {102 queue *q = createQueue(5);103 enQueue(q, 1);104 enQueue(q, 2);105 enQueue(q, 3);106 enQueue(q, 4);107 enQueue(q, 5);108 enQueue(q, 6);109 deQueue(q);110 deQueue(q);111 deQueue(q);112 enQueue(q, 123);113 enQueue(q, 234);114 std::cout << head(q) << std::endl;115 system("pause");116 return 0;117 }
测试不是太过严格，如果读者发现问题，希望不吝赐教，不胜感激。
以上。
队列ADT的两种简单实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。