/* */ John Waken's Blog

John Waken's Blog

Beauty is Simplicity

栈的反转问题

John Waken posted @ Dec 31, 2009 11:07:10 PM in Algorithm with tags stack , 13430 阅读

作者：John Waken
邮箱：JohnWaken@163.com
转载请著明：http://johnwaken.is-programmer.com/posts/14471.html

给你一个有n个元素的栈，问要经过多少次pop和push操作才能把这个栈反转。如下，1 2 3 4 5 变为 5 4 3 2 1

 栈反转例子

解决这个问题还是用递归思想。记住，要让递归融入你的血液，嵌入你的灵魂。

定义符号$$(a_{n}, b_{n})$$，它表示是反转大小为n的栈时pop操作的次数是$$a_{n}$$，push操作的次数是 $$b_{n}$$

现在要构造第推式了。要反转n个数，就是把栈顶的元素放到底部去，然后再反转上面n－1个数。于是步骤出来了：
       0. 先定义栈反转的递归终止条件：反转空栈时，什么也不做。

       1. 执行 pop 操作，将 pop 出来的数保存到 temp 中
       2. 反转剩下来的 n-1 个数
       3. 把 temp 这个数 push 进去
       4. 再反转这 n 个数（这样temp就到最底层去了，而上面 n－1 个数没有变）
       5. 保持栈底的元素不动，反转最上面 n-1 个元素

OK，大功告成，这就是反转一个栈的算法。如果你真的这样认为，那么你还没有理解递归。递归是把大问题化为基础问题和能用同样方法解决的小问题，但是请看步骤4，这里出现了和原问题同样规模的子问题，所以违背了递归的本意。

没办法，重新试探一些构造方法吧。没错，是“ 试探 ”，虽然演绎推理诠释了数学的精妙，但数学的美丽与震撼还是来自于经验和直觉。

       0. 递归终止条件还是碰到空栈就什么也不做

       1. 执行 pop 操作，将弹出来的数存在 temp1 中
       2. 反转栈。此时栈中有 n-1 个数
       3. 如果栈中还有元素，就将它弹出来，保存在 temp2 中
       4. 反转栈。此时栈中有 n-1 个数
       5. 执行push，将 temp1 压入栈
       6. 反转栈。此时栈中有 n-1 个数
       7. 如果temp2保存来弹出来的数，则将它压入栈中

这才真正OK，真正地“ 大事化小” 了。这个算法的基本思想是反转一个序列可以先将首尾互换，再将中间的序列反转。当n为奇数，最后一次递归时，temp2肯定没用。

然后我们再从算法中提取有关pop和push操作次数的信息：

             $$a_{n} = 3a_{n-1} + 2, \quad n \geq 2

             $$a_{n} = 3a_{n-1} + 1, \quad n=1

             起始条件 $$a_{0} = 0 $$

将上面式子调整一下，得到：

             $$a_{n} = 3a_{n-1} + 2, \quad n \geq 2

             起始条件是 $$a_{0}=0, a_{1} = 1 $$

同理可求得push操作的第推式：

             $$b_{n} = 3b_{n-1} + 2, \quad n \geq 2

              起始条件是  $$b_{0} = 0, b_{1} = 1

综上所述得到：
             $$(a_{n}, b_{n})=(3a_{n-1}+2,3b_{n-1}+2), \quad n \geq 2$$

              起始条件 $$(a_{0},b_{0})=(0,0),\quad (a_{1},b_{1})=(1,1) $$


思考 1：这个算法只用到了两个辅助记录，temp1和temp2，那么它的空间复杂度是O(1)吗？ 不是，因为这是一个递归过程，在每次递归时都会用到新的temp1，temp2。所以空间复杂度是O(n)。再看他的时间复杂度，根据第推公式可知，通项肯定是指数形式的。

思考 2：由以上论述可知借助栈来实现栈的反转是很复杂的（当然如果你借助很多栈的话就像当于借助足够的变量了，这样就意思了）；试着用一个同样大小的队列来实现栈的反转，这就简单高效的多了。

Small_feed 评论 (7)
1
[回复]
deep cleaning dubai 说:
Sep 15, 2019 04:35:24 PM

We are able to provide a person the services based on your needs once we own high-pressure gear. The hygiene of cellar area is no less than a lethal task. Right now, you need not worry regarding basement cleansing. Our expert staff provides you with the solutions very quickly. Here tend to be major creating and systems cleaning providers we will be ready to offer you twenty-four hours a day.

2
[回复]
full time maids in d 说:
Sep 04, 2021 04:14:47 PM

Some people may reckon that this posting contains a little motivational principles, but virtually no... this article is actually a call to use it. And loads of it. Also looked as "Massive action". I unquestionably don't prefer to scare any one away together with the word "massive", but oftentimes it's expected to provide a reality check. If you agree you're visiting see success while in the cleaning by way of sticking your yellow website ad search while in the phone book for your good enterprise, good luck start.

3
[回复]
celeb networth 说:
Sep 10, 2021 10:39:26 PM

Have you ever heard of celeb networth post - the famous website for celebrities information?

4
[回复]
babysitting services 说:
Sep 14, 2021 06:03:15 PM

Its for these reasons the top-class clinic prefers clinic cleaning to look after their environments. This comprises of cleaning the various areas of the office along the lines of floors, wall surfaces, washrooms, clinic equipment, panels, and truck's window glass to boot. Over typically the years, you will find many commercial establishments are availing work cleaning assistance as his or her's prime choice precisely as it reaps advantages. The cleanliness associated with office is as it again impacts at the occupants’ vigorous health and in addition as throughout their productivity not to mention wellbeing. Avail a lot of our cleaning service precisely as it provides peace from mind to get results in some clean habitat.

5
[回复]
Things to do 说:
May 25, 2022 08:57:50 PM

What do you love about traveling? There are many reasons why people love traveling: to meet new people, to see the beautiful world by our own eyes, to experience new things, to capture the beautiful moment, beautiful place with yourself in it, or just simple love the wanderlust feeling... Things to do post will show you the best ideas to travel from all around the world, and makes you want to grab to backpack and go.

7
[回复]
full time maids in d 说:
Aug 17, 2023 04:36:17 PM

The earliest one and also residential cleaning up services is made up of maid expert services with carpet cleaning and home window cleaners. These services are crucial less typically but are certainly useful. There will be many companies globally that give quality personal cleaning resources at economical prices. You may easily search any one of the suitable personal cleaning repair shops over the internet and enjoy your wellbeing without distressing about cleaning the home.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter