用单链表实现栈

1 问题

链表跟数组类似，也是一个有序集合。但他们的区别在于，创建数组时需要分配一大块内存用来存储元素，而链表中的元素在内存分配上是相互独立的，元素与元素之间是通过指针或者引用连接起来的。此次实验用单链表实现栈。

2 方法

1. 创建节点： _Node 类的构造函数是为了方便而设计，它允许为每个新创建的节点赋值。 由于 python 没有指针，因此一般使用类的结构实现指向关系。
2. 在链表的头部插入/删除元素： 只有在链表头部才能实现有效插入和删除元素。 为避免每次返回栈的大小时，必须遍历整个列表，因此定义一个变量_size持续追踪当前元素的数量。
3. 元素压栈： 当栈顶插入新元素时，调用_Node类来完成链接结构的改变。

代码清单 1

class LinkedStack:
   # 创建节点
   class _Node:
       __slot__='_element','_next'
       def __init__(self,element,next):
           self._element = element
           self._next = next
   # 设置栈顶
   def __init__(self):
       self._head =None
       self._size = 0
   # 元素压栈
   def push(self,e):
       self._head = self._Node(e,self._head)
       self._size += 1
ls=LinkedStack()
ls.push(1)
ls.push(2)

3 结语

相比数组，链表的插入和删除效率更高，对于不需要搜索但变动频繁且无法预知数量上限的数据，更适合用链表。比如，当我们从一个数组中移除第一个元素后，需要将后面的元素在内存中的位置都往前移，这就意味着需要重新进行内存分配和内存布局，因为数组中的元素在内存上是连续的。但是对于链表，我们只需要把 head 指针/引用指向第二个元素就可以了。所以链表更适合用来做栈。