C++学习笔记_19 适配器容器-stack queue 2021-05-19

简介: C++学习笔记_19 适配器容器-stack queue 2021-05-19

stack 容器(栈)

只支持在栈顶  存取  元素

后进先出

queue容器(队列)

从容器尾部插入元素,从容器头部取元素

先进先出

1. // C++学习笔记_19 适配器容器-stack queue
2. #include <iostream>
3. #include<string>
4. #include<vector>
5. #include<list>
6. #include<stack>  //STL 中栈的头文件
7. #include<queue>
8. using namespace std;
9. 
10. void TestStack()
11. {
12.     stack<int>  iStack1; 
13. //事实上,就是把 deque 封装了一下,限制了一些函数的使用,而且不提供迭代器。
14. //push 调用 deque.push_back(); pop 调用 deque.pop_back(); 等等
15. //这里,deque 我们称之为 底层容器 (默认使用deque做底层容器)
16. //能不能用 list, vector 做底层容器呢?
17. stack<int>  iStack2(iStack1);
18. stack<int>  iStack3({ 1, 2, 3, 4, 5 });
19. 
20.     stack<int, list<int>>    iStack4; //可以使用 list   做底层容器
21.     stack<int, vector<int>>  iStack5; //可以使用 vector 做底层容器
22. //区别就是 list 和 deque 的区别,vector 和 deque 的区别  ---》 数据的存储方式不同
23. 
24. //所用容器都有的函数
25. //empty()
26. //size()
27.     cout << "压栈:";
28. for (int i = 0; i < 10; i++){
29.         cout << i << " ";
30.         iStack1.push(i);
31.         iStack4.push(i);
32.         iStack5.push(i);
33.     }
34.     cout << endl;
35. 
36.     cout << "弹栈:";
37. while (!iStack1.empty()) {
38.         cout << iStack1.top() << " "; //取栈顶元素
39. 
40. //注意一点 iStack1.top() 
41. //返回值是引用:意味着可以通过复制来修改栈顶元素
42. // iStack1.top() = xxx;
43. 
44.         iStack1.pop();//删除栈顶元素
45.     }
46.     cout << endl;
47. 
48.     cout << "弹栈:";
49. while (!iStack4.empty()){
50.         cout << iStack4.top() << " "; //取栈顶元素
51.         iStack4.pop();//删除栈顶元素
52.     }
53.     cout << endl;
54. 
55.     cout << "弹栈:";
56. while (!iStack5.empty()){
57.         cout << iStack5.top() << " "; //取栈顶元素
58.         iStack5.pop();//删除栈顶元素
59.     }
60.     cout << endl;
61. }
62. void TestQueue()
63. {
64.     queue<int> iQue1;
65. queue<int> iQue2(iQue1);
66. queue<int> iQue3({ 1, 2, 3, 4, 5 });
67. 
68. //队列的底层容器也是 deque
69. //能不能用 vector 和 list ?
70. //queue<int, vector<int>> iQue4; 
71. //queue.pop() 弹出元素,调用的是底层容器的 pop_front()
72. //vector 容器没有这个方法,所以,queue 不能是用 vector做底层容器
73.     queue<int, list<int>>   iQue5;
74. 
75. //empty(); size()
76. 
77.     cout << "入队列:";
78. for (int i = 0; i < 10; i++){
79.         cout << i << " ";
80.         iQue1.push(i);
81. //iQue4.push(i);
82.         iQue5.push(i);
83.     }
84.     cout << endl;
85. 
86. //O(N^2) , O(2^N)
87. //可以取队头和队尾元素
88.     cout << "队头元素:" << iQue1.front() << endl;
89.     cout << "队尾元素:" << iQue1.back()  << endl;
90. //这里 front() 和 back() 都返回引用 ---》可以直接赋值,修改队头和队尾元素
91. 
92.     cout << "出队列:";
93. while (!iQue1.empty()){
94.         cout << iQue1.front() << " ";
95.         iQue1.pop(); //删除队头元素
96.     }
97.     cout << endl;
98. 
99. /*
100.     cout << "出队列:";
101.     while (!iQue4.empty()){        
102.         cout << iQue4.front() << " ";
103.         //error C2039: “pop_front”: 不是“std::vector<int,std::allocator<_Ty>>”的成员
104.         iQue4.pop(); //删除队头元素
105.     }
106.     cout << endl;
107.     */
108. 
109.     cout << "出队列:";
110. while (!iQue5.empty()){
111.         cout << iQue5.front() << " ";
112.         iQue5.pop(); //删除队头元素
113.     }
114.     cout << endl;
115. }
116. int main()
117. {
118. TestStack();
119. TestQueue();
120. system("pause");
121.  return 0;
122. }
1. //C 语言的 栈实现
2. #include <iostream>
3. using namespace std; 
4. //创建栈结构体 
5. typedef struct tagStack
6. {
7. int *pBase;  //栈内存起始地址
8. int *pTop;   //栈顶指针 (下一个元素存在这里)
9. int size;    //栈的长度
10. } MyStack;
11. //申请栈 
12. int InitStack(MyStack *pStack, int sz)
13. {
14.     pStack->pBase = (int*)malloc(sz*sizeof(int));
15. if (pStack->pBase == NULL) return -1;
16.     pStack->pTop = NULL; //表示空栈
17.     pStack->size = sz;
18. return 0;
19. }
20. //进栈
21. int push(MyStack *pStack, int data)
22. {
23. //1: 空间不够
24. if (pStack->pTop == pStack->pBase + pStack->size - 1) return -1;
25. //栈顶上移
26. if (pStack->pTop == NULL) pStack->pTop = pStack->pBase;
27. else (pStack->pTop)++;
28. //存元素到栈顶
29.     *(pStack->pTop) = data;
30. return 0;
31. }
32. //出栈, 直接删除栈顶,返回成功或者失败
33. int pop(MyStack *pStack)
34. {
35. //空栈
36. if (pStack->pTop == NULL) return -1;
37.     (pStack->pTop)--;
38. //并没有做删除元素的操作 (指针下移,把元素位置置为不可用)
39. return 0;
40. }
41. //取栈顶元素, 返回栈顶元素
42. int top(MyStack *pStack)
43. {
44. //考虑一个问题:空栈?
45. //if (pStack->pTop == NULL)
46. //{
47. //写断言,抛出异常,....
48. //也可以不写,有使用者保证空栈的时候,不调用它
49. //}
50. return *(pStack->pTop);
51. }
52. bool empty(MyStack *pStack)
53. {
54. return !(pStack->pTop == NULL);
55. }
56. //获取栈中元素个数 (不是栈的大小)
57. int size(MyStack *pStack)
58. {
59. if (pStack->pTop == NULL) return  0;
60. else
61. return pStack->pTop - pStack->pBase + 1;
62. }
63. //释放栈内存
64. void DestroyStack(MyStack *pStack)
65. {
66. if (pStack->pBase){
67. free(pStack->pBase);
68.         pStack->pBase = NULL;
69.         pStack->pTop = NULL;
70.         pStack->size = 0;
71.     }
72. }
73. void Test_MyStack()
74. {
75.   MyStack *pStack;
76.   InitStack(pStack, 5);
77.   for(int i=0;i<5;i++)
78.     push(pStack, i+1);
79.   cout<<top(pStack)<<endl;
80.   cout<<pop(pStack)<<endl;
81.   cout<<top(pStack)<<endl;
82.   cout<<empty(pStack)<<endl;
83.   cout<<size(pStack)<<endl;
84.   DestroyStack(pStack);
85.   cout<<size(pStack)<<endl; 
86. } 
87. int main()
88. {
89.   Test_MyStack();
90.   return 0;
91. }
1. typedef struct tagQueue
2. {
3. int *pBase; //指定内存起始位置
4. int *pHead;
5. int *pTail;
6. int size;
7. }MyQueue;
8. //pBase 基址
9. //pTail 指向队尾元素
10. //为了不移动元素,我们再定义一个 pHead 指针,指向队头元素 (做成一个循环形式)
11. //1:一个元素出队 --》把 pHead 后移
12. //2:pTail 到了末尾位置? --》判断 pHead 是不是在 pBase
13. //       是的话,表示存满了,不是的话,存到 pBase 位置来 (跳转到起始位置)
14. //3:同样的 pHead 到了末尾,移动到 pBase 位置
15. //   这个时候 如果 pTail 也在这个位置,表示队列是空的了
16. //4:事实上:pHead == pTail 表示队列是空的
17. //   pTail 的后一个位置(末尾的后一个位置就跳到了队头),是 pHead 表示队列满了
18. //5:所以我们要注意一点:N 个长度的队列,只能插入 N-1 个元素
19. //   有个位置留白,用于区分到底是空队列还是满队列
20. 
21. //作业:自己实现队列  InitQueue   push   pop  front  back  empty  size  destroy

 

相关文章
|
2天前
|
设计模式 C++ 容器
c++中的Stack与Queue
c++中的Stack与Queue
|
24天前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
55 21
|
3月前
|
存储 设计模式 C++
【C++】优先级队列(容器适配器)
本文介绍了C++ STL中的线性容器及其适配器,包括栈、队列和优先队列的设计与实现。详细解析了`deque`的特点和存储结构,以及如何利用`deque`实现栈、队列和优先队列。通过自定义命名空间和类模板,展示了如何模拟实现这些容器适配器,重点讲解了优先队列的内部机制,如堆的构建与维护方法。
60 0
|
4月前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
62 1
|
4月前
|
设计模式 存储 C++
C++之stack 和 queue(下)
C++之stack 和 queue(下)
64 1
|
4月前
|
C++ 容器
C++之stack 和 queue(上)
C++之stack 和 queue(上)
102 0
|
4月前
|
存储 C++ 容器
C++番外篇——stack、queue的实现及deque的介绍
C++番外篇——stack、queue的实现及deque的介绍
41 0
|
4月前
|
存储 算法 C++
C++入门10——stack与queue的使用
C++入门10——stack与queue的使用
63 0
|
4天前
|
Ubuntu API 网络虚拟化
ubuntu22 编译安装docker,和docker容器方式安装 deepseek
本脚本适用于Ubuntu 22.04,主要功能包括编译安装Docker和安装DeepSeek模型。首先通过Apt源配置安装Docker,确保网络稳定(建议使用VPN)。接着下载并配置Docker二进制文件,创建Docker用户组并设置守护进程。随后拉取Debian 12镜像,安装系统必备工具,配置Ollama模型管理器,并最终部署和运行DeepSeek模型,提供API接口进行交互测试。
90 15
|
2月前
|
监控 NoSQL 时序数据库
《docker高级篇(大厂进阶):7.Docker容器监控之CAdvisor+InfluxDB+Granfana》包括:原生命令、是什么、compose容器编排,一套带走
《docker高级篇(大厂进阶):7.Docker容器监控之CAdvisor+InfluxDB+Granfana》包括:原生命令、是什么、compose容器编排,一套带走
299 78