# Smarter Python数据结构：如何翻转栈

Python数据结构：链表合集（12+7），复现几遍，包你学会

Smaller And Smarter Python数据结构：自己动手实现栈

Smaller And Smarter Python数据结构：自己动手实现队列

#### 今日问题

"""

Goal: write a program to flip all elements in the stack
Input: 5, 4, 3, 2, 1
Output: 1, 2, 3, 4, 5
"""

### 解题

from StackQueueHash.b_1_implementation_stack import LinkStack
from StackQueueHash.b_2_implementation_queue import LinkQueue

### 方法一：数组（列表）实现队列

"""
Method One : 借助辅存

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 : 递归翻转

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()  # 出栈

#### 运行结果

|
2天前
|

python对tcp协议栈进行优化之一
**TCP优化摘要:** - MSS优化涉及调整TCP最大段大小，Python中可使用socket.getsockopt()查询MSS。 - Scapy是Python库，用于创建和发送网络包，可用于测试和优化协议栈性能。 - LwIP是轻量级TCP/IP协议栈，适合嵌入式设备，可通过分析和调整提升性能，特别是实时性和资源管理。
17 5
|
2天前
|

【7月更文挑战第12天】图的遍历利器：DFS 和 BFS。Python 中，图可表示为邻接表或矩阵。DFS 沿路径深入，回溯时遍历所有可达顶点，适合找路径和环。BFS 层次遍历，先近后远，解决最短路径问题。两者在迷宫、网络路由等场景各显神通。通过练习，掌握这些算法，图处理将游刃有余。
9 3
|
1天前
|

“解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系，通过节点和边连接。常见的表示方法是邻接矩阵（适合稠密图）和邻接表（适合稀疏图）。图遍历包括DFS（深度优先搜索）和BFS（广度优先搜索）：DFS深入探索分支，BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
8 1
|
2天前
|

Python中的列表（List）和元组（Tuple）是两种重要的数据结构
【7月更文挑战第12天】Python中的列表（List）和元组（Tuple）是两种重要的数据结构
4 1
|
4天前
|

【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 0
|
5天前
|

【7月更文挑战第9天】Python并发编程提升效率：**理解并发与并行，线程借助threading模块处理IO密集型任务，受限于GIL；进程用multiprocessing实现并行，绕过GIL限制。示例展示线程和进程创建及同步。选择合适模型，注意线程安全，利用多核，优化性能，实现高效并发编程。
18 3
|
7天前
|

Python元类实战：打造你的专属编程魔法，让代码随心所欲变化
【7月更文挑战第7天】Python的元类是编程的变形师，用于创建类的“类”，赋予代码在构建时的变形能力。
30 1
|
8天前
|

Python元类大揭秘：从理解到应用，一步步构建你的编程帝国
【7月更文挑战第6天】Python元类是创建类的对象的基石，允许控制类的生成过程。通过自定义元类，可在类定义时动态添加方法或改变行为。
16 0