简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
今天给大家分享的书籍《Python程序员面试算法宝典》第二章第三小节：如何翻转栈。
如果你是第一次看，也许，你可以看看本系列下面的文章：
Python数据结构：链表合集（12+7），复现几遍，包你学会
Smaller And Smarter Python数据结构：自己动手实现栈
Smaller And Smarter Python数据结构：自己动手实现队列
今日问题
""" 目标：写一个程序，翻转栈内所有元素 输入：5，4，3，2，1 输出：1，2，3，4，5 Goal: write a program to flip all elements in the stack Input: 5, 4, 3, 2, 1 Output: 1, 2, 3, 4, 5 """
解题
首先我们之前已经写好了栈和队列的基本操作，在b_1_implementation_stack.py和b_2_implementation_queue文件中，所以我们先导入这两个包。
from StackQueueHash.b_1_implementation_stack import LinkStack from StackQueueHash.b_2_implementation_queue import LinkQueue
方法一：数组（列表）实现队列
""" Method One : 借助辅存 核心思想：充分利用栈和队列特性，栈先进后出，每次只能去栈顶元素，队列先进先出。 我们将栈内元素一一取出，存放到队列中，栈空后，我们再将队列内的元素一一取出， 存入到栈中，实现翻转。 时间复杂度：O(N) 空间复杂度：O(N) Method one: with the help of auxiliary storage Core idea: make full use of stack and queue characteristics, stack first in first out, can only go to the top element of stack each time, queue first in first out. We take out the elements in the stack one by one and store them in the queue. After the stack is empty, we take out the elements in the queue one by one and store them in the stack to realize the flipping. """
代码
def flip_stack_one(s): q = LinkQueue() # 初始化一个队列 while not s.stack_is_empty(): # 遍历栈，将栈中元素取出，存入队列 x = s.get_stack_top() # 获取栈首元素 s.stack_pop() # 出栈 q.queue_push(x) # 入队列 while not q.queue_is_empty(): # 遍历队列，将队列中元素取出，存入栈，实现翻转 x = q.get_queue_top() # 获取队首元素 q.queue_pop() # 出队列 s.stack_push(x) # 入栈
方法二：链表实现队列
""" Method Two : 递归翻转 核心思想：第一次递归，把栈去除栈顶，生成子栈，把每个子栈的栈底元素翻转到栈顶， 第二次递归，对每个子栈操作，遍历到栈底（不断出栈，直到栈为空为止），栈空后开 始回溯，把栈内相邻的两个元素进行互换位置，这样不断从上到下递归回溯，可以实现 把栈底元素翻转到栈顶。 递归两大要素：递归定义 ， 递归终止条件。 递归定义：将当前栈最低元素翻转到栈顶，然后对不包含栈顶元素的子栈进行同样操作。 终止条件：栈为空。 时间复杂度：O(N^2) 空间复杂度：O(1) Method two: recursive flip Core idea: for the first recursion, remove the stack top, generate the sub stack, flip the stack bottom elements of each sub stack to the top of the stack, for the second recursion, operate on each sub stack, traverse to the bottom of the stack (keep going out of the stack until the stack is empty), start to backtrack after the stack is empty, and exchange the two adjacent elements in the stack, so as to recursively backtrack from the top to the bottom, which can be realized Flip the bottom element to the top of the stack. Two elements of recursion: recursion definition and recursion termination condition. Recursion definition: flip the lowest element of the current stack to the top of the stack, and then do the same for the sub stack that does not contain the top element. Termination condition: stack is empty. """
代码
def change_stack_top(s): top1 = s.get_stack_top() # 取出栈顶 # print(top1) s.stack_pop() # 出栈 if not s.stack_is_empty(): # 栈不为空时一直递归遍历 change_stack_top(s) # 递归 top2 = s.get_stack_top() # 取出当前栈顶 s.stack_pop() # 出栈 s.stack_push(top1) # 入栈 s.stack_push(top2) # 入栈，实现相邻元素交换位置 else: # 栈为空时，开始回溯 s.stack_push(top1) # 入栈 def flip_stack_two(s): if s.stack_is_empty(): # 栈为空，直接返回 return # 第一步：将当前栈顶与栈尾交换位置 change_stack_top(s) # 第二步：取出当前栈顶，开始递归处理子栈 top = s.get_stack_top() s.stack_pop() flip_stack_two(s) # 第三步：回溯时，将之前取出的栈顶元素入栈 s.stack_push(top)
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": s = LinkStack() # 初始化一个栈对象 stack_data = [1, 2, 3, 4, 5] # 栈元素 for i in stack_data: # 初始化栈内元素 s.stack_push(i) # 入栈 # flip_stack_one(s) # 翻转栈内元素 flip_stack_two(s) # 翻转栈内元素 while not s.stack_is_empty(): # 遍历打印栈内元素 print(s.get_stack_top(), end=" ") # 打印当前栈顶元素 s.stack_pop() # 出栈
运行结果
本文代码思路来自书籍《Python程序员面试宝典》，书中部分代码有问题，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。
希望大家多多支持。
大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
欢迎关注微信公众号：简说Python
关注后回复：1024，可以领取精选编程学习电子书籍。
