Smarter Python数据结构:如何翻转栈

简介: Smarter Python数据结构:如何翻转栈

简说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.pyb_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()  # 出栈

运行结果

image.png

本文代码思路来自书籍《Python程序员面试宝典》,书中部分代码有问题,文中已经修改过了,并添加上了丰厚的注释,方便大家学习,后面我会把所有内容开源放到Github上,包括代码,思路,算法图解(手绘或者电脑画),时间充裕的话,会录制视频。

希望大家多多支持。


大家好,我是老表

觉得本文不错的话,转发、留言、点赞,是对我最大的支持。

欢迎关注微信公众号:简说Python

关注后回复:1024,可以领取精选编程学习电子书籍。

相关文章
|
2天前
|
网络协议 Python
python对tcp协议栈进行优化之一
**TCP优化摘要:** - MSS优化涉及调整TCP最大段大小,Python中可使用`socket.getsockopt()`查询MSS。 - Scapy是Python库,用于创建和发送网络包,可用于测试和优化协议栈性能。 - LwIP是轻量级TCP/IP协议栈,适合嵌入式设备,可通过分析和调整提升性能,特别是实时性和资源管理。
|
2天前
|
算法 Python
逆袭之路!用 Python 玩转图的 DFS 与 BFS,让数据结构难题无处遁形
【7月更文挑战第12天】图的遍历利器:DFS 和 BFS。Python 中,图可表示为邻接表或矩阵。DFS 沿路径深入,回溯时遍历所有可达顶点,适合找路径和环。BFS 层次遍历,先近后远,解决最短路径问题。两者在迷宫、网络路由等场景各显神通。通过练习,掌握这些算法,图处理将游刃有余。
9 3
|
1天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
8 1
|
2天前
|
存储 缓存 Python
Python中的列表(List)和元组(Tuple)是两种重要的数据结构
【7月更文挑战第12天】Python中的列表(List)和元组(Tuple)是两种重要的数据结构
4 1
|
4天前
|
存储 算法 调度
惊呆了!Python高级数据结构堆与优先队列,竟然能这样优化你的程序性能!
【7月更文挑战第10天】Python的heapq模块实现了堆和优先队列,提供heappush和heappop等函数,支持O(log n)时间复杂度的操作。优先队列常用于任务调度和图算法,优化性能。例如,Dijkstra算法利用最小堆加速路径查找。堆通过列表存储,内存效率高。示例展示了添加、弹出和自定义优先级元素。使用堆优化程序,提升效率。
14 2
|
1天前
|
存储 数据可视化 数据处理
`geopandas`是一个开源项目,它为Python提供了地理空间数据处理的能力。它基于`pandas`库,并扩展了其对地理空间数据(如点、线、多边形等)的支持。`GeoDataFrame`是`geopandas`中的核心数据结构,它类似于`pandas`的`DataFrame`,但包含了一个额外的地理列(通常是`geometry`列),用于存储地理空间数据。
`geopandas`是一个开源项目,它为Python提供了地理空间数据处理的能力。它基于`pandas`库,并扩展了其对地理空间数据(如点、线、多边形等)的支持。`GeoDataFrame`是`geopandas`中的核心数据结构,它类似于`pandas`的`DataFrame`,但包含了一个额外的地理列(通常是`geometry`列),用于存储地理空间数据。
4 0
|
4天前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
5天前
|
安全 Python
告别低效编程!Python线程与进程并发技术详解,让你的代码飞起来!
【7月更文挑战第9天】Python并发编程提升效率:**理解并发与并行,线程借助`threading`模块处理IO密集型任务,受限于GIL;进程用`multiprocessing`实现并行,绕过GIL限制。示例展示线程和进程创建及同步。选择合适模型,注意线程安全,利用多核,优化性能,实现高效并发编程。
18 3
|
7天前
|
开发者 Python
Python元类实战:打造你的专属编程魔法,让代码随心所欲变化
【7月更文挑战第7天】Python的元类是编程的变形师,用于创建类的“类”,赋予代码在构建时的变形能力。
30 1
|
8天前
|
设计模式 存储 Python
Python元类大揭秘:从理解到应用,一步步构建你的编程帝国
【7月更文挑战第6天】Python元类是创建类的对象的基石,允许控制类的生成过程。通过自定义元类,可在类定义时动态添加方法或改变行为。
16 0