本篇我以堆栈的数据类型和操作方法两个方面总结学习笔记
堆栈（Stack）
- 一种后进先出（LIFO）的线性数据结构，对堆栈的插入和删除操作都只能在栈顶（top）进行。
- 堆栈可以通过数组和链表轻松实现
一、数据类型
-
Stack()创建堆栈 -
push(item)向栈顶插入项(平时的insert) / append()(内置) -
pop()返回栈顶的项(内置)，并从堆栈中删除该项(平时的remove) -
clear()清空堆栈 -
empty()判断堆栈是否为空 -
size()返回堆栈中项的个数 -
top()返回栈顶的项
操作示意图
二、代码实现
下面以数组和链表两个方面写出实现代码。时间复杂度分析如下
- 动态数组插入前面O(n)，插入后面0(1)
- 链表插入前面O(1)，插入后面O(n)
- 所以堆栈为了达到0(1)的效果：数组堆到后面，链表插到前面
'''
动态数组堆栈（Array Stack）
堆栈的数组实现插到数组后面，因此基本都是对最后一个元素进行操作
'''
class ArrayStack(object):
def __init__ (self):
self._data = [] #空的容器 def __len__ (self): #size
return len(self._data) def is_empty(self):
return len(self._data) == 0 #push进堆栈： O(1)
def push(self, e):
self._data.append(e) # 查看栈顶元素：O(1)
def top(self):
if self.is_empty( ):
raise ValueError( 'Stack is empty' )
return self._data[-1] # 弹出栈顶元素O(1)
def pop(self):
if self.is_empty( ):
raise ValueError( 'Stack is empty' )
return self._data.pop( ) #打印堆栈
def printstack(self):
for i in range(len(self._data)):
print(self._data[i], end = ' ')
print() mystack = ArrayStack()
print ('size was: ', str(len(mystack)))
mystack.push(1)
mystack.push(2)
mystack.push(3)
mystack.push(4)
mystack.push(5)
print ('size was: ', str(len(mystack)))
mystack.printstack()
mystack.pop()
mystack.pop()
print ('size was: ', str(len(mystack)))
mystack.printstack()
print(mystack.top())
mystack.pop()
mystack.pop()
mystack.pop() #输出结果
size was: 0
size was: 5
1 2 3 4 5
size was: 3
1 2 3
3
'''
链表（Linked List）
堆栈的链表实现插到元素前面，因此都是对第一个节点进行操作
下面模块导入自我的链表学习笔记代码
'''
from LinkedList import LinkedList
from LinkedList import Node class LinkedStack(object):
def __init__ (self):
self._list = LinkedList() def __len__ (self):
return self._list.length def is_empty(self):
return self._list.length == 0 # O(1)
def push(self, e):
self._list.add_first(e); # O(1)
def top(self):
return self._list.get_first().value; # O(1)
def pop(self):
return self._list.remove_first().value; def printstack(self):
self._list.printlist() mystack = LinkedStack()
print ('size was: ', str(len(mystack)))
mystack.push(1)
mystack.push(2)
mystack.push(3)
mystack.push(4)
mystack.push(5)
print ('size was: ', str(len(mystack)))
mystack.printstack()
mystack.pop()
mystack.pop()
print ('size was: ', str(len(mystack)))
mystack.printstack()
print(mystack.top())
mystack.pop()
mystack.pop()
mystack.pop() #输出结果
size was: 0
size was: 5
5 4 3 2 1
size was: 3
3 2 1
3