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
