C++学习（三十）（C语言部分）之 栈和队列
数据结构
1.保存数据 2.处理数据
数组+操作
增查删改
栈和队列
是一种操作受限的线性表
栈 是先进后出 是在一端进行插入删除的操作--->栈顶 另一端叫做栈底（栈和栈区是两个概念）（是一种数据结构）
队列 是先进先出 是在两端进行插入删除的操作 在插入的一端叫做队尾 在删除的一端叫做队头
栈 需要回退操作 退回上一步（悔棋）
队列 多用于和时间有关的 比如消息（鼠标点击消息 键盘消息） 先来的先处理-->服务器请求
（举个比较恶心的例子 吃了吐--->栈 吃了拉---->队列）
例子
1、进制转换（栈）
2、队列的例子 入队 出队
测试代码笔记如下：
1 //用栈实现 进制转换
2 #if 0
3 #include<stdio.h>
4 #include<stdbool.h> //判断真假 c++中的
5 //栈 1.线性表 （顺序表 链表的实现）
6 struct STACK
7 {
8 int arr[40]; //数组
9 int size; //栈的大小 栈中最多可以存放多少的元素
10 int top; //栈顶 栈中不关心有多少元素 关心的是插入删除的位置
11 };
12
13 //初始化栈
14 void initStack(struct STACK*p)
15 {
16 p->top = 0; //表示没有任何元素
17 p->size = 20; //栈的大小
18 //栈顶就是即将要插入的数据的位置
19 //栈 是否是满 top==size
20 //top==0 表示栈中没有元素
21 }
22
23 //栈的插入 入栈/压栈
24 void pushStack(struct STACK*p,int data)
25 {
26 if (p->top >= p->size)//表示栈满
27 {
28 printf("栈满，压栈失败！\n");
29 }
30 else
31 {
32 p->arr[p->top++] = data;
33 }
34 }
35
36 //栈的删除 出栈
37 int popStack(struct STACK*p) //出一个元素 需要在外面得到这个元素 需要返回值
38 {
39 if (p->top <= 0) //栈空
40 {
41 printf("没有元素，出栈失败！\n");
42 return 0;
43 }
44 else
45 {
46 return p->arr[--(p->top)]; //出最后一个元素
47 }
48 }
49
50 //判断栈是否为空
51 int isStackEmpty(struct STACK*p) //操作栈的时候会用
52 {
53 return p->top <= 0; //返回值是1表示空 不然栈没空
54 }
55
56 int main()
57 {
58 //进制转换 代码实现 不断除2求余 直到除到0的位置
59 //栈实现 余数栈
60 //十进制转换
61 int x = 66666;
62 printf("要转换的值是：%d\n", x);
63 //scanf_s("%d", &x);
64 struct STACK stack;
65 initStack(&stack); //栈初始化
66 while (x != 0)
67 {
68 pushStack(&stack, x % 2);
69 x /= 2; //或x>>=1; 右移等于1相当于除以二 比除法快
70 }
71 //入完栈之后 出栈
72 printf("转换出的二进制是：");
73 while (isStackEmpty(&stack) != 1) //表示栈没有空
74 {
75 printf("%d", popStack(&stack)); //出栈 %x打印16进制
76 }
77 //对于其他进制
78 //入栈 做处理 10-15 用A-F替换 -->if
79 getchar();
80 return 0;
81 }
82 #endif
83
84 /***************************分割线*********************************/
85 //队列的例子 队尾插入 队头删除
86 #if 1
87 //队
88 struct QUEUE
89 {
90 int arr[20];
91 int size;
92 int begin; //队头
93 int end; //队尾
94 };
95
96 //初始化
97 void initQueue(struct QUEUE*p)
98 {
99 p->begin = p->end = 0; //刚刚开始队列没有元素
100 p->size = 20; //数组下标
101 /*
102 begin==end 队空
103 end+1-->begin的位置 队满
104 */
105 }
106
107 //入队 队尾操作
108 void inQueue(struct QUEUE*p, int data)
109 {
110 if ((p->end + 1) % p->size == p->begin) //判断队列是否已满
111 {
112 return; //队列已满情况 只是表示退出函数 没有别的意思
113 }
114 else
115 {
116 p->arr[p->end++] = data; //插入
117 p->end %= p->size; //保证end+1之后 最后的end还是小于size
118 }
119 }
120
121 //出队 队头操作
122 int outQueue(struct QUEUE*p)
123 {
124 if (p->begin == p->end) //队空 不操作 判断队是否满
125 {
126 return 0; //返回一个0
127 }
128 else
129 {
130 int x = p->arr[p->begin]; //要出队的元素
131 p->begin = (p->begin + 1) % p->size; //防止begin往后移动之后 等于size
132 return x; //返回要出队的元素
133 }
134 }
135
136 int main()
137 {
138 struct QUEUE queue;
139 initQueue(&queue);
140 int y = 666;
141 //入队
142 while (y != 0)
143 {
144 inQueue(&queue, y % 16); //将余数入队
145 y >>= 4;
146 }
147 //出队
148 while (queue.begin!=queue.end)
149 {
150 printf("%x", outQueue(&queue));
151 }
152
153
154 getchar();
155 return 0;
156 }
157 #endif
158
159 #if 0
160 //ctf比赛 密码部分
161 //flag{c4es4r_variation}
162 //bg[`sZ*Zg'dPfP`VM_SXVd
163 #include<stdio.h>
164 int main()
165 {
166 int arr[] = { 98, 103, 91, 96, 115, 90, 42, 90, 103, 39, 100, 80, 102, 80, 96, 86, 77, 95, 83, 88, 86, 100 };
167 printf("原样输出:\n");
168 for (int i = 0; i < 22; ++i)
169 {
170 printf("%d\t", arr[i]);
171 }
172 printf("\n");
173 printf("进行运算:\n");
174 int brr[] = { 4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25 };
175 printf("结果输出:\n");
176 int crr[22];
177 for (int i = 0; i < 22;++i)
178 crr[i] = arr[i] + brr[i];
179 for (int i = 0; i < 22; ++i)
180 printf("%d\t", crr[i]);
181 getchar();
182 return 0;
183 }
184 #endif
2019-03-31 19:41:48