栈和队列面试题
发布日期:2021-09-19 03:18:20
浏览次数:1
分类:技术文章
本文共 3447 字,大约阅读时间需要 11 分钟。
(1)实现一个栈,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1) 解析:要想使Min的时间复杂度为o(1),我们需要借助一个栈来辅助我们完成,这个辅助栈用来存放入主栈的最小数据。
如上图所示,在主栈插入1时,辅助栈为空,则将1插入辅助栈。
插入2时,辅助栈不为空则将2与辅助栈中的1比较,2大于1 ,则不入栈。
插入0时,将0和辅助栈的1比较,0比1小,则插入辅助栈。这样就可以保证辅助栈的栈顶一直为当前入站的最小值。而实现主栈的Min时直接返回辅助栈的top();
templateclass StackMin{public: StackMin() {} ~StackMin() {} void push(const T& x) { s.push(x); if (mins.empty() || x <= mins.top()) { mins.push(x); } } void pop() { if (s.empty()) { return; } if (s.top() == mins.top()) { mins.pop(); } s.pop(); } T Min() { return mins.top(); }private: stack s; //主栈 stack mins;//辅助栈};
(2)使用两个栈实现一个队列实现队列,就要实现它的3个方法:Enqueue(入队)、Dequeue(出队)和Peek(队头)
用两个栈(先进后出)实现一个队列(先进先出);
插入时,将数据全都插入在栈1中。
pop时,若栈2为空,则将栈1中的数据插入栈2,然后pop栈2中的数据。
若栈2不为空,则先 pop栈2内的数据,然后将1内数据压入2中pop。
代码实现:
templateclass Cquee{public: Cquee() {} ~Cquee() {} void push(const T& node); T pop();private: stack stack1; stack stack2;};template void Cquee ::push(const T& node){ stack1.push(node);}template T Cquee ::pop(){ T temp = 0; if (stack2.empty()) { while (!stack1.empty()) { temp = stack1.top(); stack2.push(temp); stack1.pop(); } } temp = stack2.top(); stack2.pop(); return temp;}
(3)使用两个队列实现一个栈
用俩个队列实现一个栈,要保证有一个队列为空。
插入时,若俩个队列都为空,则插入在1中,若有不为空的,则插入非空队列
pop时,将非空队列的前n-1个数据插入在空队列中,然后pop掉剩余的最后一个数据
代码实现:
template class Stack{public: Stack() { _count = 0; } ~Stack() {} void push(const T& data); T pop(); int Getnum()const;private: queue queue1; queue queue2; int _count;};template void Stack ::push(const T& data){ if (queue1.size() == 0 && queue2.size() == 0) { queue1.push(data); } else if (queue1.size() > 0) { queue1.push(data); } else { queue2.push(data); } ++_count;}template int Stack ::Getnum()const{ return _count;}template T Stack ::pop(){ T ret; if (queue2.size() == 0) { while (queue1.size() != 1) { T& data = queue1.front(); queue1.pop(); queue2.push(data); } ret = queue1.front(); queue1.pop(); cout << ret << endl; } else { while (queue2.size() != 1) { T& data = queue2.front(); queue2.pop(); queue1.push(data); } ret = queue2.front(); queue2.pop(); cout << ret << endl; } --_count; return ret;}
(4)一个数组实现两个栈 用一个数组实现俩个栈有三种方法 1:奇偶数分别为一个栈(如果奇数栈为空,偶数栈比较大,会浪费很多空间) 2:从中间向两边分别为一个队列(如果前面的栈为空,则会浪费一半的空间) 3:从两边向中间(最优)
代码实现
enum Stack{Frist,Second};templateclass ArrayStack{public: ArrayStack() : _n(5) , _a(new T[_n]) , _size1(0) , _size2(_n - 1) {} ~ArrayStack() { if (_a) { delete []_a; _a = NULL; } } void push(Stack s,T data) { assert(_a); if (_size1 > _size2) { Expand(); } if (s == Frist) { _a[_size1++] = data; } else { _a[_size2--] = data; } } void pop(stack s) { if (s == Frist) { if (_size1 == NULL) { cout << "Stack1 is empty" << endl; return; } --_size1; } if (s == Second) { if (_size2 == _n - 1) { cout << "Stack2 is empty" << endl; return; } ++_size2; } } void Expand() { size_t n = _n; _n *= 2; T* tmp = new T[_n]; for (size_t i = 0; i < _size1; i++) { tmp[i] = _a[i]; } size_t newsize = n - _size2;//栈二的元素个数 _size2 += n + 1; for (size_t i = _n - 1; --_size2; --i) { tmp[i] = _a[--n]; } _size2 = _n - newsize; delete[]_a; swap(_a, tmp); }private: T* _a; size_t _n; size_t _size1; size_t _size2;};
转载地址:https://blog.csdn.net/audience_fzn/article/details/78233889 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年03月28日 16时50分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
oracle所需的环境,转:面对一个全新的oracle环境,首先应该了解什么?
2019-04-21
linux 小数四则运行,shell四则运算(整数及浮点数)的方法介绍
2019-04-21
linux系统分区后进入紧急模式,Linux系统的救援模式应用详解
2019-04-21
linux创建硬盘分区lvm,LVM创建及分区调整、更换LVM硬盘
2019-04-21
FreeBSD可以安装Linux软件吗,在Linux服务器上面通过网络安装FreeBSD
2019-04-21
南昌工程学院c语言答案,南昌工程学院C语言程序设计基础课件第3讲运算符和表达式...
2019-04-21
python学画画_python学画画(下)
2019-04-21
老男孩mysql 百度云_英语语录:除了你,没人能掌控你的幸福
2019-04-21
mysql获取刚新增的数据库_如何取得刚插入数据库的数据的id mysql
2019-04-21
python将10到1递减_(Python)如何将3个递减列表合并成一个递减列表?
2019-04-21
python脚本怎么用来处理数据_长时间运行数据处理python脚本的程序结构
2019-04-21