简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
今天给大家分享的书籍《Python程序员面试算法宝典》第二章第一小节：如何实现栈。
如果你是第一次看，也许，你可以看看本系列下面的文章： Python数据结构：链表合集（12+7），复现几遍，包你学会
今日问题
""" 目标：实现栈，使其具有方法：压栈（push）、弹栈（pop）、取栈顶元素（get_top）、 判断栈是否为空（is_empty）、获取栈中元素个数（size） 为后面操作打基础 Goal: to implement the stack with the following methods: push, pop, get top Judge whether the stack is empty and get the number of elements in the stack (size) Lay a foundation for later operations """
解题
方法一：数组（列表）实现栈
""" Method One : 数组（列表）实现栈 核心思想：以数组（列表）作为存储栈数据的数据结构，Python里本身 对列表有着丰富的内置操作，比如pop,append,len等等，列表是顺序 存储，并且在Python初始化一个列表时，不一定非要指定列表长度，这 使得Python列表实现起来非常简单和方便。 注意：一般在C、Java中初始化数组(列表)时，是必须声明数组（列表） 长度的，而在Python中，可以不限定，但append添加的效率很明显要比 直接赋值（比如：list[1] = "Python"）的低很多。 Method one: array (list) implementation stack Core idea: Taking array (list) as the data structure of stack data storage, python itself has rich built-in operations on list, such as pop, append, len, etc. list is sequential storage, and when Python initializes a list, it is not necessary to specify the length of list, which makes Python list implementation very simple and convenient. Note: when initializing arrays (lists) in C and Java, the length of arrays (lists) must be declared. In Python, there is no limit, but the efficiency of adding append is obviously lower than that of direct assignment (for example: list [1] = "Python"). """
代码
class ListStack: def __init__(self): self.stack = [] # 列表，不指定长度 # self.stack = [0]*10 # 列表，指定长度 # 入栈 def stack_push(self, x): self.stack.append(x) # 入栈 print("********入栈成功********") # 出栈 def stack_pop(self): if self.stack_len() > 0: self.stack.pop() # 出栈 print("********出栈成功********") else: print("********栈已空********") # 获取栈顶元素 def get_stack_top(self): if self.stack_is_empty(): print("********空栈********") return None else: return self.stack[self.stack_len() - 1] # 判断栈是否为空 def stack_is_empty(self): if self.stack_len() == 0: return True else: return False # 栈长度 def stack_len(self): return len(self.stack)
方法二：链表实现栈
""" Method Two : 链表实现栈 核心思想：以链表作为存储栈数据的数据结构，Python里本身 是不含链表这种数据结构的，所以需要我们自己去写对链表的基 本操作，当然在上一章中我们已经非常熟悉链表了，所以操作起 来还是很简单。 注意：Python内置的数据结构里没有链表，我们一般用引用实现 链表这一数据结构，创建一个类LinkNode，包含两个属性，data 为数据域，存放当前结点数据，next为指针域。存放下一个结点的 地址（指针）。 Method two: linked list implementation stack Core idea: take linked list as the data structure to store stack data. Python itself does not contain linked list, so we need to write the basic operation of linked list. Of course, in the previous chapter, we are very familiar with linked list, so the operation is very simple. Note: there is no linked list in Python's built-in data structure. Generally, we use reference to implement the linked list data structure. We create a linknode class, which contains two attributes. Data is the data field, which stores the current node data, and next is the pointer field. Store the address (pointer) of the next node. """
代码
class LinkNode: def __init__(self, x): self.data = x # 数据域 self.next = None # 指针域 class LinkStack: def __init__(self): self.data = "head" self.next = None # 头结点，栈的top指针 # 入栈 def stack_push(self, x): node = LinkNode(x) # 新建一个结点 node.next = self.next self.next = node # 插入到头结点后 print("********入栈成功********") # 出栈 def stack_pop(self): if not self.stack_is_empty(): node = self.next self.next = node.next # 出栈，让self.next指向第二个结点 print("********出栈成功********") else: print("********栈已空********") # 获取栈顶元素 def get_stack_top(self): if self.stack_is_empty(): print("********空栈********") return None else: return self.next.data # 判断栈是否为空 def stack_is_empty(self): if self.stack_len() == 0: return True else: return False # 栈长度 def stack_len(self): link_len = 0 cur_node = self.next while cur_node: # 遍历计算链表长，即栈长 cur_node = cur_node.next link_len = link_len + 1 return link_len
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": # 初始化一个栈 # my_stack = ListStack() # 列表栈测试 my_stack = LinkStack() # 链表栈测试 # 入栈 my_stack.stack_push(1) my_stack.stack_push(2) # 获取栈顶 print("当前栈顶为：", my_stack.get_stack_top()) # 出栈 my_stack.stack_pop() # 判断栈是否为空 if my_stack.stack_is_empty(): print("********栈已空********") else: print("********栈没空********") # 栈长 print("栈长为：", my_stack.stack_len()) # 出栈 my_stack.stack_pop() # 判断栈是否为空 if my_stack.stack_is_empty(): print("********栈已空********") else: print("********栈没空********")
本文代码思路来自书籍《Python程序员面试宝典》，书中部分代码有问题，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。
希望大家多多支持。
大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
欢迎关注微信公众号：简说Python
关注后回复：1024，可以领取精选编程学习电子书籍。
