-
编程语言
站-
热门城市 全国站>
-
其他省市
-
-
400-636-0069
小标
2018-06-15
来源 ：
阅读 924
评论 0
摘要：本文主要向大家介绍了C/C++知识点的队列和栈相关面试题总结，通过具体的实例让大家了解，希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了C/C++知识点的队列和栈相关面试题总结，通过具体的实例让大家了解，希望对大家学习C/C++知识点有所帮助。
1、实现一个栈，要求实现Push（出栈）、Pop（入栈）、Min（返回最小值的操作）的时间复杂度为O(1)？？
分析：
出栈和入栈根据栈自身提供的接口不难实现，而返回最小值，我们知道遍历一次栈即可找到最小值，但是对栈的操作只能在栈顶，因此，要遍历势必要改变栈的状态，而且还要求时间复杂度为O(1),即更不能遍历栈。我们可以利用两个栈同时进行操作，一个是我们放数据的栈，而另一个栈顶专门放数据中的最小值，最后需要当前最小值，直接取第二个栈顶元素即可。
2、源代码如下：
[cpp] view plain copy
1. //push出栈 ------ pop入栈 min返回最小值 ------ 时间复杂度为O(1)
2.
3. //不能遍历
4.
5. #include <iostream>
6. using namespace std;
7. #include <stack>
8.
9. template <class T>
10. class StackMinValue
11. {
12. public:
13. StackMinValue()
14. {}
15. void Pop(const T& x)
16. {
17. s.push(x);
18. if(min.empty())
19. {
20. min.push(x);
21. }
22. else if(min.top()>=x)
23. {
24. min.push(x);
25. }
26. }
27. void Push() //出栈
28. {
29. if(min.top() == s.top() && s.size() != 1)
30. {
31. min.pop();
32. }
33. s.pop();
34. }
35. T& Min()
36. {
37. return min.top();
38. }
39. ~StackMinValue()
40. {}
41. private:
42. stack<T> s,min;
43. };
44.
45.
46.
47. int main()
48. {
49. StackMinValue<int> a;
50. a.Pop(3);
51. a.Pop(2);
52. cout<<a.Min();
53. a.Pop(5);
54. a.Pop(8);
55. a.Pop(1);
56. cout<<a.Min();
57. a.Push();
58. a.Push();
59. cout<<a.Min();
60. a.Push();
61. a.Push();
62. cout<<a.Min();
63.
64. return 0;
65. }2、使用两个栈实现一个队列
分析：栈--->先进后出 队列--->先进先出
在进行操作时，我们可利用栈的特性，在进行push操作时，使用栈操作，而进行pop操作时将栈中元素逐一放入另一栈
源代码：
[cpp] view plain copy
1. #include <iostream>
2. using namespace std;
3. #include <stack>
4. #include <assert.h>
5. template<class T>
6. class Queue
7. {
8. public:
9. Queue()
10. {}
11. void Push(const T& x) //尾插
12. {
13. a.push(x);
14. }
15. void Pop() //头删
16. {
17. assert(!a.empty());
18. while(!a.empty())
19. {
20. b.push(a.top());
21. a.pop();
22. }
23. b.pop();
24. while(!b.empty())
25. {
26. a.push(b.top());
27. b.pop();
28. }
29. }
30. size_t Size()
31. {
32. return a.size();
33. }
34. bool Empty()
35. {
36. return a.empty();
37. }
38. T& front() //返回队头元素 -------找到再恢复
39. {
40. assert(a.empty() != true);
41. while (!a.empty())
42. {
43. b.push(a.top());
44. a.pop();
45. }
46. T tmp = b.top();
47. while (!b.empty())
48. {
49. a.push(b.top());
50. b.pop();
51. }
52. return tmp;
53. }
54. T& back() //返回队尾元素
55. {
56. return a.top();
57. }
58. ~Queue()
59. {}
60. private:
61. stack<T> a,b;
62. };
63. int main()
64. {
65. Queue<int> a;
66. a.Push(1);
67. a.Push(2);
68. a.Push(3);
69. cout<<a.front()<<endl;
70. cout<<a.Size()<<endl;
71. a.Push(4);
72. a.Pop();
73. cout<<a.front()<<endl;
74. return 0;
75. }
3、两个队列实现栈
思路：栈---先进后出 队列---先进先出
创建两个队列，一个队列放数据，另一个当作辅助队列，当进行push（尾插）操作时直接用队列的push进行操作，而进行pop操作时，由于队列的pop是进行头删，不符合栈pop的条件，这时可将队列1中数据从第一个开始另一辅助队列2中，但是，第一个队列中最后一个元素不放入，然后，将第一个队列清空，再将辅助队列中元素按顺序放入第一个队列中即可。
源代码：
[cpp] view plain copy
1. #include <iostream>
2. using namespace std;
3. #include <queue>
4. #include <assert.h>
5. // 两个队列实现一个栈
6. template <class T>
7. class TStack
8. {
9. public:
10. TStack()
11. {}
12. void Push(const T& x) //进栈---尾插
13. {
14. s1.push(x);
15. }
16. void Pop() //出栈---
17. {
18. assert(!s1.empty());
19. while (!s1.empty() && (s1.size()!=1)) //最后一个元素不进队列
20. {
21. s2.push(s1.front());
22. s1.pop();
23. }
24. s1.pop();
25. while (!s2.empty())
26. {
27. s1.push(s2.front());
28. s2.pop();
29. }
30. }
31. bool Empty()
32. {
33. if (s1.empty())
34. {
35. return true;
36. }
37. return false;
38. }
39. T& Top()
40. {
41. return s1.back();
42. }
43. size_t Size()
44. {
45. return s1.size();
46. }
47.
48. private:
49. queue<T> s1,s2;
50. };
51.
52.
53. int main()
54. {
55. TStack<int> a;
56. a.Push(1);
57. a.Push(7);
58. a.Push(5);
59. a.Push(6);
60. cout<<a.Top()<<endl;
61. cout<<a.Size()<<endl;
62. a.Pop();
63. cout<<a.Size()<<endl;
64. cout<<a.Top()<<endl;
65. return 0;
66. }
4、一个数组实现两个栈
分析：
方案一：将数组的下标为0的位置当做第一个栈的栈底，下标为1的位置当做第二个栈的栈底，将数组的偶数位置看做第一个栈的存储空间，奇数位置看做第二个栈的存储空间。
方案二：从中间分别向两边压栈
将数组的中间位置看做两个栈的栈底，压栈时栈顶指针分别向两边移动，当任何一边到达数组的起始位置或是数组尾部，则开始扩容。
方案三：从两边向中间压栈
将数组的起始位置看作是第一个栈的栈底，将数组的尾部看作第二个栈的栈底，压栈时，栈顶指针分别向中间移动，直到两栈顶指针相遇，则扩容。
比较：方案二和方案一当两栈中元素不同时，比较浪费空间，方案三节省空间
方案3代码：
[cpp] view plain copy
1. #include <iostream>
2. using namespace std;
3. #include <assert.h>
4. //一个数组实现两个栈
5. //从两边开始存
6. template<class T>
7. class Stack
8. {
9. public:
10. Stack()
11. :_arr(NULL)
12. ,_size1(0)
13. ,_size2(0)
14. ,_capacity(0) //初始化容量为2
15. {}
16. void Push1(const T& x)
17. {
18. _checkcapacity();
19. _arr[_size1] = x;
20. _size1++;
21. }
22. void Pop1()
23. {
24. assert(Size1() != 0);
25. _size1--;
26. }
27. size_t Size1()
28. {
29. return _size1;
30. }
31. T& Top1()
32. {
33. return _arr[_size1-1];
34. }
35. void Push2(const T& x)
36. {
37. _checkcapacity();
38. size_t botton = _capacity-_size2-1;
39. _arr[botton] = x;
40. botton--;
41. _size2++;
42. }
43.
44. void Pop2()
45. {
46. assert(Size2() != 0);
47. _size2--;
48. }
49. size_t Size2()
50. {
51. return _size2;
52. }
53. T& Top2()
54. {
55. assert(_size2 != 0);
56. return _arr[_capacity-1];
57. }
58. private:
59. void _checkcapacity()
60. {
61. if ((_size1+_size2)==_capacity || (_capacity==0)) //容量满 或 空
62. {
63. size_t _newcapacity = _capacity*2+2;
64. T* tmp = new T[_newcapacity];
65. for (size_t i=0; i<_size1; i++) //第一个栈放数组左边
66. {
67. tmp[i] = _arr[i];
68. }
69. size_t t = _capacity-1;
70. for(size_t j=_newcapacity-1; (j>(_newcapacity-_size1)) && (t>_size1-1); --t,j--)
71. {
72. tmp[j] = _arr[t];
73. }
74. _capacity = _newcapacity;
75. swap(_arr,tmp);
76. }
77. }
78. private:
79. T* _arr;
80. size_t _size1;
81. size_t _size2;
82. size_t _capacity;
83. };
84.
85. int main()
86. {
87. Stack<int> a;
88. a.Push1(1);
89. cout<<a.Size1()<<endl;
90. a.Push1(8);
91. a.Pop1();
92. a.Push1(5);
93. a.Push1(3);
94. cout<<a.Size1()<<endl;
95. cout<<a.Top1()<<endl;
96. a.Push1(2);
97. a.Push2(1);
98. a.Push2(0);
99. a.Push2(4);
100. cout<<a.Size2()<<endl;
101. cout<<a.Top2()<<endl;
102. a.Push2(1);
103. a.Push2(1);
104. a.Push2(4);
105. a.Push2(10);
106. a.Pop1();
107. cout<<a.Size2()<<endl;
108. a.Pop1();
109. a.Pop2();
110. a.Pop2();
111. cout<<a.Size2()<<endl;
112. cout<<a.Top2()<<endl;
113. return 0;
114. }以上就介绍了C/C+的相关知识，希望对C/C+有兴趣的朋友有所帮助。了解更多内容，请关注职坐标编程语言C/C+频道！
喜欢 | 1
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
索取资料
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
