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

 

相关文章
|
20天前
|
设计模式 存储 C++
C++:Stack和Queue的模拟实现
C++:Stack和Queue的模拟实现
|
存储 消息中间件 调度
【C++】容器篇(三)—— stack的基本介绍及其模拟实现
【C++】容器篇(三)—— stack的基本介绍及其模拟实现
|
17天前
|
C++ 容器
【C++练级之路】【Lv.9】【STL】stack类和queue类的模拟实现
【C++练级之路】【Lv.9】【STL】stack类和queue类的模拟实现
|
算法 程序员 C语言
【C++ 迭代器】深入探讨 C++ 迭代器:标准与自定义容器中的 begin() 和 cbegin()
【C++ 迭代器】深入探讨 C++ 迭代器:标准与自定义容器中的 begin() 和 cbegin()
46 0
|
19天前
|
存储 安全 编译器
【C++ 17 泛型容器对比】C++ 深度解析:std::any 与 std::variant 的细微差别
【C++ 17 泛型容器对比】C++ 深度解析:std::any 与 std::variant 的细微差别
44 1
|
20天前
|
存储 安全 算法
【C++ 17 包裹类 泛型容器 std::any】深入理解与应用C++ std::any:从泛型编程到多态设计
【C++ 17 包裹类 泛型容器 std::any】深入理解与应用C++ std::any:从泛型编程到多态设计
45 1
|
25天前
|
安全 算法 调度
C++队列探秘:队列容器的使用技巧与实战案例解析
C++队列探秘:队列容器的使用技巧与实战案例解析
125 0
|
25天前
|
存储 网络协议 C++
C++ Vector容器详解:一站式指南,掌握动态数组的高效使用
C++ Vector容器详解:一站式指南,掌握动态数组的高效使用
49 2
|
25天前
|
存储 缓存 安全
【C/C++ 基础 数组容器比较】深入探究C++容器:数组、vector与array之间的异同
【C/C++ 基础 数组容器比较】深入探究C++容器:数组、vector与array之间的异同
14 0
|
存储 算法 C++
【C++】容器篇(四)—— queue的基本介绍以及模拟实现
【C++】容器篇(四)—— queue的基本介绍以及模拟实现
【C++】容器篇(四)—— queue的基本介绍以及模拟实现