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