4.2.4 列表实现堆栈和队列
堆栈和队列是数据结构中常用的数据结构，列表可以用来实现堆栈和队列。
堆栈是指最先进入堆栈的元素最后才输出，符合“后进先出”的顺序。栈的插入、弹出是通过栈首指针控制的。插入一个新的元素，指针移到新元素的位置；弹出一个元素，指针移到下面一个元素的位置，即原堆栈倒数第2个元素的位置，该元素成为栈顶元素。
队列是指最先进入队列的元素最先输出，符合“先进先出”的顺序。队列的插入、弹出是分别通过队首指针和队尾指针控制的。插入一个新的元素，队尾指针移到新元素的位置；弹出一个元素，队首指针移到原队列中第2个元素的位置，该元素成为队列的第1个元素。
使用列表的append()、pop()方法可以模拟这两个数据结构，append()、pop()的使用参见4.2.1小节。
首先分析一下堆栈的实现，调用append()可以把一个元素添加到堆栈的顶部，调用pop()方法把堆栈中最后一个元素弹出来。
假设有一个堆栈["apple"，"grape"，"grape"]，要向堆栈中添加一个新的元素“orange”。图4-4描述了列表实现堆栈的原理。
图4-4 列表实现堆栈的原理
“apple”是列表中第1个进入的元素，所以置于堆栈的最底端。调用append（"orange"）后，程序把“orange”元素插到堆栈的顶部。此时栈的指针移动到元素“orange”，栈中包含4个元素，“orange”置于堆栈的顶部。然后调用pop()，弹出顶部的元素“orange”，栈的指针移到“grape”。
下面这段代码使用列表模拟了堆栈。
01 # 堆栈的实现
02 list = ["apple", "grape", "grape"] # 定义list列表
03 list.append("orange") # 将orange压入堆栈
04 print (list)
05 print ("弹出的元素：", list.pop()) # 从堆栈中弹出最后压入的元素
06 print (list)
【代码说明】
·第2行代码创建了一个堆栈list。
·第3行代码向堆栈中添加一个元素“orange”。
·第4行代码输出添加新元素后堆栈中的内容。输出结果：
['apple', 'banana', 'grape', 'orange']
·第5行代码弹出堆栈中最顶部的元素。输出结果：弹出的元素：
orange
·第6行代码输出顶部元素被弹出后堆栈中的内容。输出结果：
['apple', 'banana', 'grape']
队列也是通过调用append()和pop()方法实现的。pop()的调用方式有所不同，通过调用pop（0）弹出队列最前面的元素。假设有一个队列["apple"，"grape"，"grape"]，要向队列中添加一个新的元素“orange”。图4-5描述了列表实现队列的原理。
图4-5 列表实现队列的原理
“apple”是列表中第1个进入的元素，所以置于队列的最前端。调用append（"orange"）后，程序把“orange”元素插到队列的尾部，队尾指针移到元素“orange”。此时列表中包含4个元素，“orange”置于队列的尾部。然后调用pop（0），弹出队列最前面的元素“apple”，队首指针移到元素“banana”。从而实现了“先进先出”的队列结构。下面这段代码使用列表模拟了队列。
01 #队列的实现
02 list = ["apple", "grape", "grape"] # 定义list列表
03 list.append("orange") # 队尾加入orange
04 print (list)
05 print ("弹出的元素：", list.pop(0)) # 弹出第一个元素
06 print (list)
【代码说明】
·第2行代码创建了一个队列list。
·第3行代码向队列中添加一个元素“orange”。
·第4行代码输出添加新元素后队列中的内容。输出结果：
['apple', 'banana', 'grape', 'orange']
·第5行代码弹出队列最前面的元素。输出结果：
弹出的元素： apple
·第6行代码输出最前面的元素被弹出后队列中的内容。输出结果：
['banana', 'grape', 'orange']
堆栈和队列是数据结构这门课程探讨的内容，读者可以参考相关的书籍进一步学习。