文档章节

对栈元素排序

r
 ranjiewen
发布于 2016/11/03 23:52
字数 1725
阅读 89
收藏 0
     对栈元素排序,借助另外一个栈,主要是对vector的尾部进行操作。

/*****************************************************
* \file twoStacksSort.cpp
* \date 2016/05/07 23:58

* \问题描述:
请编写一个程序,按升序对栈进行排序(即最大元素位于栈顶),要求最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中。
给定一个int[] numbers(C++中为vector&ltint>),其中第一个元素为栈顶,请返回排序后的栈。请注意这是一个栈,意味着排序过程中你只能访问到第一个元素。
测试样例:
[1,2,3,4,5]
返回:[5,4,3,2,1]

* \问题分析:
思路
因为只能使用一个辅助栈,我们每次取出栈内元素的时候,就要与辅助栈的元素比较,将所有大于取出元素的辅助站元素全部放回原栈之中,
一直重复这个操作,就能最后得到一个排好序的栈。


*****************************************************/


#include<iostream>
using namespace std;
#include<vector>

class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        // write code here
        vector<int> ans;
        if (numbers.size()==0)
        {
            return ans;
        }
        while (numbers.size()!=0)
        {
            int temp = numbers.back();
            numbers.pop_back();
            while (ans.size()!=0&&temp<ans.back())     //num 4 3 5 1 2 (后面为back)
            {
                numbers.push_back(ans.back());
                ans.pop_back();
            }
            ans.push_back(temp);
        }
        while (ans.size()!=0)   
        {
            numbers.push_back(ans.back());  //此时num为空
            ans.pop_back();
        }
        return numbers;
    }
};

 

一、内存基本构成
可编程内存在基本上分为这样的几大部分:静态存储区、堆区和栈区。他们的功能不同,对他们使用方式也就不同。
静态存储区:内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。它主要存放静态数据、全局数据和常量。
栈区:在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。
堆区:亦称动态内存分配。程序在运行的时候用malloc或new申请任意大小的内存,程序员自己负责在适当的时候用free或delete释放内存。动态内存的生存期可以由我们决定,如果我们不释放内存,程序将在最后才释放掉动态内存。 但是,良好的编程习惯是:如果某动态内存不再使用,需要将其释放掉,否则,我们认为发生了内存泄漏现象。

二、三者之间的区别
我们通过代码段来看看对这样的三部分内存需要怎样的操作和不同,以及应该注意怎样的地方。
例一:静态存储区与栈区

复制代码 代码如下:

    char* p = “Hello World1”;
    char a[] = “Hello World2”;
    p[2] =‘A';
    a[2] =‘A';
    char* p1 = “Hello World1;”


这个程序是有错误的,错误发生在p[2] = ‘A'这行代码处,为什么呢,是变量p和变量数组a都存在于栈区的(任何临时变量都是处于栈区的,包括在main()函数中定义的变量)。但是,数据“Hello World1”和数据“Hello World2”是存储于不同的区域的。因为数据“Hello World2”存在于数组中,所以,此数据存储于栈区,对它修改是没有任何问题的。因为指针变量p仅仅能够存储某个存储空间的地址,数据“Hello World1”为字符串常量,所以存储在静态存储区。虽然通过p[2]可以访问到静态存储区中的第三个数据单元,即字符‘l'所在的存储的单元。但是因为数据“Hello World1”为字符串常量,不可以改变,所以在程序运行时,会报告内存错误。并且,如果此时对p和p1输出的时候会发现p和p1里面保存的地址是完全相同的。
例二:栈区与堆区

复制代码 代码如下:

char* f1()
  { 
 char* p = NULL; 
 char a;  
 p =    return p; 
  } 

 char* f2()  
 { 
  char* p = NULL: 
  p =(char*)new char[4];
   return p;  
 } 


这两个函数都是将某个存储空间的地址返回,二者有何区别呢?f1()函数虽然返回的是一个存储空间,但是此空间为临时空间。也就是说,此空间只有短暂的生命周期,它的生命周期在函数f1()调用结束时,也就失去了它的生命价值,即:此空间被释放掉。所以,当调用f1()函数时,如果程序中有下面的语句:

复制代码 代码如下:

    char* p;
    p = f1();
    *p =‘a';


此时,编译并不会报告错误,但是在程序运行时,会发生异常错误。因为,你对不应该操作的内存(即,已经释放掉的存储空间)进行了操作。但是,相比之下,f2()函数不会有任何问题。因为,new这个命令是在堆中申请存储空间,一旦申请成功,除非你将其delete或者程序终结,这块内存将一直存在。也可以这样理解,堆内存是共享单元,能够被多个函数共同访问。如果你需要有多个数据返回却苦无办法,堆内存将是一个很好的选择。但是一定要避免下面的事情发生:

复制代码 代码如下:

   void f()
    {
    …
    char * p;
    p =(char*)new char[100];
    …
    }


这个程序做了一件很无意义并且会带来很大危害的事情。因为,虽然申请了堆内存,p保存了堆内存的首地址。但是,此变量是临时变量,当函数调用结束时p变量消失。也就是说,再也没有变量存储这块堆内存的首地址,我们将永远无法再使用那块堆内存了。但是,这块堆内存却一直标识被你所使用(因为没有到程序结束,你也没有将其delete,所以这块堆内存一直被标识拥有者是当前您的程序),进而其他进程或程序无法使用。这种不道德的“流氓行为”(我们不用,却也不让别人使用)称为内存泄漏。

总之,对于堆区、栈区和静态存储区它们之间最大的不同在于,栈的生命周期很短暂。但是堆区和静态存储区的生命周期相当于与程序的生命同时存在(如果您不在程序运行中间将堆内存delete的话),我们将这种变量或数据成为全局变量或数据。但是,对于堆区的内存空间使用更加灵活,因为它允许你在不需要它的时候,随时将它释放掉,而静态存储区将一直存在于程序的整个生命周期中。

本文转载自:http://www.cnblogs.com/ranjiewen/p/5901232.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
python学习10.03:Python list常用方法(count、index、pop、reverse和sort)

除前面章节介绍的增加元素、删除元素、修改元素方法之外,列表还包含了一些常用的方法。 例如,在交互式解释器中输入 dir(list) 即可看到列表包含的所有方法,如下所示: 在上面输出结果中己...

太空堡垒185
昨天
7
0
按升序对栈进行排序

按升序对栈进行排序(即最大元素位于栈顶)。最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构(如数组)。 该栈支持如下操作:push, pop, peek,和isEmpty 如果可以...

一贱书生
2016/11/17
63
0
排序算法C语言实现——快速排序的递归和非递归实现

/*快排 - 递归实现 nlogn / / 原理: 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部...

Jo_ZSM
2018/10/11
0
0
LeetCode算法题-Min Stack(Java实现)

这是悦乐书的第177次更新,第179篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第36题(顺位题号是155)。设计一个支持push,pop,top和在恒定时间内检索最小元素的堆栈。 pu...

小川94
2018/11/20
0
0
[面试专题]数据结构和算法-JS之魂

数据结构和算法-JS之魂 标签(空格分隔): 未分类 数据结构: 栈:一种遵从先进后出 (LIFO) 原则的有序集合;新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端为栈底。在栈里,新元...

逺方小鎭
09/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Flink Graph生成及Hash生成分析

222

MrPei
1分钟前
1
0
[译]Android Activity 和 Fragment 状态保存与恢复的最佳实践

https://blog.csdn.net/growing_tree/article/details/53759564 https://blog.csdn.net/u013588712/article/details/54691791...

shzwork
2分钟前
1
0
调用第三方快递鸟物流单号查询接口API代码示例

最近进行网站后台开发,需要实现物流的即时查询,发现之前集成的 快递100物流查询 API ——【PHP 快递查询源码资源】 已经不能正常使用了; 为了方便以后的业务需求,经过比较,最后选择使用...

程序的小猿
9分钟前
1
0
java Poi 操作执行excel 文件中函数问题

poi 读取excel 文件,当excel 有函数时,poi直接读取返回的是excel 函数,并不能返回函数计算结果: 解决步骤: sheet.setForceFormulaRecalculation(true); 判断该列格式是否为...

早a
17分钟前
2
0
js模拟实现输入框input事件

直接修改value值是无法触发对应元素的事件的。 通过发送输入框input事件了, 可以触发。 这里简单封装了一个方法. window.inputValue = function (dom, st) { var evt = new InputEvent('i...

開援带碼
18分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部