欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++学习(三十)(C语言部分)之 栈和队列

程序员文章站 2022-05-29 12:04:24
数据结构1.保存数据 2.处理数据数组+操作增查删改 栈和队列是一种操作受限的线性表 栈 是先进后出 是在一端进行插入删除的操作 >栈顶 另一端叫做栈底(栈和栈区是两个概念)(是一种数据结构)队列 是先进先出 是在两端进行插入删除的操作 在插入的一端叫做队尾 在删除的一端叫做队头 栈 需要回退操作 ......

数据结构
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

 附:

C++学习(三十)(C语言部分)之 栈和队列

 

2019-03-31  19:41:48