队列和栈面试题(一)— 请编写一个程序,按升序对栈进行排序,要求最多只能使用一个额外的栈存放临时数据

简介: 题目:请编写一个程序,按升序对栈进行排序,要求最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中。

题目:请编写一个程序,按升序对栈进行排序,要求最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中。


思路:首先申请一个栈sta来存放数据栈,再申请一个辅助栈help来存放临时数据,然后比较sta弹出的栈顶的值res与help栈顶元素的大小。

当sta栈不为空时:

1、如果help.empty()或者res<=help.top(),那么就把res的值压入help栈中;

2、如果help不为空并且res>help.top(),那么就把help中栈顶的值弹出并压入sta栈,最后把res的值压入help栈中。

具体可看如下过程图:

12

34

56

78

9


示例代码:

#include<iostream>
#include<string>
#include<stack>//pop,top,push
#include<vector>
using namespace std;
class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) 
    {
        stack<int> sta;
        for(vector<int>::reverse_iterator riter=numbers.rbegin();riter!=numbers.rend();riter++)
            sta.push(*riter);
        StackSort(sta);
        vector<int> res;
        while(!sta.empty())
        {
            res.push_back(sta.top());
            sta.pop();
        }
        return res;
    }
    void StackSort(stack<int> &sta)
    {
        stack<int> help;
        while(!sta.empty())
        {
            int res=sta.top();
            sta.pop();
            if(help.empty()||res<=help.top())
                help.push(res);
            else
            {
                while(!help.empty()&&res>help.top())
                {
                    sta.push(help.top());
                    help.pop();
                }
                help.push(res);
            }
        }
        while(!help.empty())
        {
            sta.push(help.top());
            help.pop();
        }
    }
};
int main()
{
    int a[5]={1,2,3,4,5};
    TwoStacks A;
    vector<int> arr(a,a+5),res;
    res=A.twoStacksSort(arr);
    for(vector<int>::iterator iter=res.begin();iter!=res.end();iter++)
        cout<<*iter<<" ";
    return 0;
}
相关文章
|
18天前
|
SQL 缓存 easyexcel
面试官问10W 行级别数据的 Excel 导入如何10秒处理
面试官问10W 行级别数据的 Excel 导入如何10秒处理
48 0
|
3月前
|
编解码 移动开发 前端开发
【面试题】 给你十万条数据,怎么样顺滑的渲染出来?
【面试题】 给你十万条数据,怎么样顺滑的渲染出来?
|
3月前
|
前端开发 JavaScript
【面试题】面试官:如果后端给你 1w 条数据,你如何做展示?
【面试题】面试官:如果后端给你 1w 条数据,你如何做展示?
|
4月前
|
存储 Java 编译器
【面试知识】Java内存分配之常量池、堆、栈
【面试知识】Java内存分配之常量池、堆、栈
|
4月前
|
算法 容器
【算法训练营】队列合集(2) 2073. 买票需要的时间 || 面试题 03.04. 化栈为队 ||
【算法训练营】队列合集(2) 2073. 买票需要的时间 || 面试题 03.04. 化栈为队 ||
61 0
|
2月前
|
Java 关系型数据库 MySQL
面试官:如何实现10亿数据判重?
面试官:如何实现10亿数据判重?
47 0
面试官:如何实现10亿数据判重?
|
2月前
|
存储 算法 调度
【数据结构入门精讲 | 第五篇】栈知识点及考研408、企业面试练习
【数据结构入门精讲 | 第五篇】栈知识点及考研408、企业面试练习
37 0
|
2月前
|
存储 前端开发 搜索推荐
【数据结构入门精讲 | 第六篇】队列知识点及考研408、企业面试练习
【数据结构入门精讲 | 第六篇】队列知识点及考研408、企业面试练习
58 0
|
3月前
|
设计模式 消息中间件 Java
面试官:什么是JIT、逃逸分析、锁消除、栈上分配和标量替换?
面试官:什么是JIT、逃逸分析、锁消除、栈上分配和标量替换?
525 1
|
3月前
|
存储 程序员 C++
面试题:C++堆和栈的区别?
面试题:C++堆和栈的区别?
24 0