栈和队列面试题
发布日期: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();
template
class 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。

代码实现:

template
class 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};template
class 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:类和对象1-this指针
下一篇:栈和队列(基本实现)

发表评论

最新留言

不错!
[***.144.177.141]2024年03月28日 16时50分16秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

oracle存储过程调用sql文件,oracle - 在SQL Developer中运行存储过程? 2019-04-21
oracle同时报604和12507,V$SES_OPTIMIZER_ENV 查不到刚修改的隐含参数, 2019-04-21
zblog的php更换域名,zblogphp更换域名后,原zblog里使用了固定域名,登录不进去怎么办... 2019-04-21
oracle dnfs 配置,Source of Oracle参数解析(dnfs_batch_size) - django-\/\/ i K | 2019-04-21
oracle所需的环境,转:面对一个全新的oracle环境,首先应该了解什么? 2019-04-21
linux 小数四则运行,shell四则运算(整数及浮点数)的方法介绍 2019-04-21
linux系统分区后进入紧急模式,Linux系统的救援模式应用详解 2019-04-21
linux配置匿名ftp服务器,在Linux环境中使用vsftpd搭建ftp实现匿名上传详细配置 2019-04-21
linux创建硬盘分区lvm,LVM创建及分区调整、更换LVM硬盘 2019-04-21
FreeBSD可以安装Linux软件吗,在Linux服务器上面通过网络安装FreeBSD 2019-04-21
.net core linux 桌面应用,C# dotnet core + AvaloniaUI 开发桌面软件,hello world 2019-04-21
linux tcp 113错误,linux系统报tcp_mark_head_lost错误的处理方法 2019-04-21
南昌工程学院c语言答案,南昌工程学院C语言程序设计基础课件第3讲运算符和表达式... 2019-04-21
python学画画_python学画画(下) 2019-04-21
云栖社区 mysql_【直播结束,已更新回放】PG、MySQL到底哪个好?云栖说这次请来五位专家撕了一下-阿里云开发者社区... 2019-04-21
老男孩mysql 百度云_英语语录:除了你,没人能掌控你的幸福 2019-04-21
mysql驱动多次执行问题_Laravel5.2队列驱动expire参数设置带来的重复执行问题 数据库驱动... 2019-04-21
mysql获取刚新增的数据库_如何取得刚插入数据库的数据的id mysql 2019-04-21
python将10到1递减_(Python)如何将3个递减列表合并成一个递减列表? 2019-04-21
python脚本怎么用来处理数据_长时间运行数据处理python脚本的程序结构 2019-04-21