参考:
总结
本系列为C++数据结构系列,会介绍 线性结构,简单树,特殊树,简单图等。本文为线性结构部分。
大纲要求
- 线性结构
【 3 】链表:单链表、双向链表、循环链表
【 3 】栈
【 3 】队列
线性结构-队列
队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:
(1)队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构;
(2)在队尾添加元素,在队头删除元素。
队列的相关概念:
(1)队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头;
(2)入队:队列的插入操作;
(3)出队:队列的删除操作。
3、队列的操作:
(1)入队: 通常命名为push()
(2)出队: 通常命名为pop()
(3)求队列中元素个数
(4)判断队列是否为空
(5)获取队首元素
4、队列的分类:
(1)基于数组的循环队列(循环队列)
(2)基于链表的队列(链队列)
QQ号码解密
新学期开始了,甘德是石申的新同桌,为交流天文学,甘德向石申询问QQ号,石申给了甘德一串加密过的数字,同时石申也告诉了甘德解密规则。规则是这样的:首先将第1个数删除,紧接着将第2个数放到这串数的末尾,再将第3个数删除并将第4个数放到这串数的末尾,再将第5个数删除直到剩下最后一个数,将最后一个数也删除。按照刚才删除的顺序,把这些删除的数连在一起就是石申的QQ啦。现在你来帮帮甘德吧。石申给甘德加密过的一串数是“631758924”。
过程如下:
#include<stdio.h> int q[102]={0,6,3,1,7,5,8,9,2,4}; int head,tail; int main() { int i; // 初始化队列 head=1; tail=10;//队列中已有9个元素 tail西乡队尾的后一个位置 while(head<tail)//当队列不为空的时候执行循环 { // 打印队首并将队首出队 printf("%d",q[head]); head++;//把队首出队 // 先将新队首添加到队尾 q[tail]=q[head]; tail++; //将队首出队 head++; } getchar(); getchar(); return 0; }
用结构体封装队列
#include<stdio.h> struct queue { int data[100];//队列的主体,用来存储内容 int head;// int tail; }; int q_demo[102]={0,6,3,1,7,5,8,9,2,4}; int main() { struct queue q; int i; // 初始化队列 q.head=1; q.tail=1; for(i=1;i<=9;i++) { // 依次向队列中插入9个数 //scanf("%d",&q.data[q.tail]);// q.data[q.tail]=q_demo[i]; q.tail++; } while(q.head<q.tail)//当队列不为空的时候执行循环 { // 打印队首并将队首出队 printf("%d",q.data[q.head]); q.head++;//把队首出队 // 先将新队首添加到队尾 q.data[q.tail]=q.data[q.head]; q.tail++; //将队首出队 q.head++; } getchar(); getchar(); return 0; }