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

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

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


思路:首先申请一个栈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;
}
相关文章
|
1月前
|
存储 网络协议 安全
30 道初级网络工程师面试题,涵盖 OSI 模型、TCP/IP 协议栈、IP 地址、子网掩码、VLAN、STP、DHCP、DNS、防火墙、NAT、VPN 等基础知识和技术,帮助小白们充分准备面试,顺利踏入职场
本文精选了 30 道初级网络工程师面试题,涵盖 OSI 模型、TCP/IP 协议栈、IP 地址、子网掩码、VLAN、STP、DHCP、DNS、防火墙、NAT、VPN 等基础知识和技术,帮助小白们充分准备面试,顺利踏入职场。
87 2
|
2月前
|
存储 缓存 关系型数据库
滴滴面试:单表可以存200亿数据吗?单表真的只能存2000W,为什么?
40岁老架构师尼恩在其读者交流群中分享了一系列关于InnoDB B+树索引的面试题及解答。这些问题包括B+树的高度、存储容量、千万级大表的优化、单表数据量限制等。尼恩详细解释了InnoDB的存储结构、B+树的磁盘文件格式、索引数据结构、磁盘I/O次数和耗时,以及Buffer Pool缓存机制对性能的影响。他还提供了实际操作步骤,帮助读者通过元数据找到B+树的高度。尼恩强调,通过系统化的学习和准备,可以大幅提升面试表现,实现“offer直提”。相关资料和PDF可在其公众号【技术自由圈】获取。
|
2月前
|
监控 Java easyexcel
面试官:POI大量数据读取内存溢出?如何解决?
【10月更文挑战第14天】 在处理大量数据时,使用Apache POI库读取Excel文件可能会导致内存溢出的问题。这是因为POI在读取Excel文件时,会将整个文档加载到内存中,如果文件过大,就会消耗大量内存。以下是一些解决这一问题的策略:
276 1
|
2月前
|
存储 关系型数据库 MySQL
面试官:MySQL一次到底插入多少条数据合适啊?
本文探讨了数据库插入操作的基础知识、批量插入的优势与挑战,以及如何确定合适的插入数据量。通过面试对话的形式,详细解析了单条插入与批量插入的区别,磁盘I/O、内存使用、事务大小和锁策略等关键因素。最后,结合MyBatis框架,提供了实际应用中的批量插入策略和优化建议。希望读者不仅能掌握技术细节,还能理解背后的原理,从而更好地优化数据库性能。
|
2月前
|
存储 大数据 数据库
Android经典面试题之Intent传递数据大小为什么限制是1M?
在 Android 中,使用 Intent 传递数据时存在约 1MB 的大小限制,这是由于 Binder 机制的事务缓冲区限制、Intent 的设计初衷以及内存消耗和性能问题所致。推荐使用文件存储、SharedPreferences、数据库存储或 ContentProvider 等方式传递大数据。
98 0
|
4月前
|
Java
【Java基础面试五】、 int类型的数据范围是多少?
这篇文章回答了Java中`int`类型数据的范围是-2^31到2^31-1,并提供了其他基本数据类型的内存占用和数值范围信息。
【Java基础面试五】、 int类型的数据范围是多少?
|
4月前
|
存储 安全 Java
JVM常见面试题(二):JVM是什么、由哪些部分组成、运行流程,JDK、JRE、JVM关系;程序计数器,堆,虚拟机栈,堆栈的区别是什么,方法区,直接内存
JVM常见面试题(二):JVM是什么、由哪些部分组成、运行流程是什么,JDK、JRE、JVM的联系与区别;什么是程序计数器,堆,虚拟机栈,栈内存溢出,堆栈的区别是什么,方法区,直接内存
JVM常见面试题(二):JVM是什么、由哪些部分组成、运行流程,JDK、JRE、JVM关系;程序计数器,堆,虚拟机栈,堆栈的区别是什么,方法区,直接内存
|
5月前
|
canal 缓存 NoSQL
Redis常见面试题(一):Redis使用场景,缓存、分布式锁;缓存穿透、缓存击穿、缓存雪崩;双写一致,Canal,Redis持久化,数据过期策略,数据淘汰策略
Redis使用场景,缓存、分布式锁;缓存穿透、缓存击穿、缓存雪崩;先删除缓存还是先修改数据库,双写一致,Canal,Redis持久化,数据过期策略,数据淘汰策略
Redis常见面试题(一):Redis使用场景,缓存、分布式锁;缓存穿透、缓存击穿、缓存雪崩;双写一致,Canal,Redis持久化,数据过期策略,数据淘汰策略
|
4月前
|
存储 设计模式 Java
Unity精华☀️ 面试“堆、栈”误区!这样做可能反而会降低吸引力
Unity精华☀️ 面试“堆、栈”误区!这样做可能反而会降低吸引力
|
4月前
|
存储 负载均衡 算法
[go 面试] 一致性哈希:数据分片与负载均衡的黄金法则
[go 面试] 一致性哈希:数据分片与负载均衡的黄金法则