软件工程-基础课程-数据结构_线性数据结构：栈与队列.docxVIP

PAGE1

PAGE1

线性数据结构概览

1栈的基本概念

栈（Stack）是一种特殊的线性数据结构，其特点是只能在一端进行插入和删除操作，通常这一端被称为栈顶（Top）。栈的这种操作特性遵循后进先出（LastInFirstOut,LIFO）原则。栈在计算机科学中有着广泛的应用，例如函数调用、表达式求值、括号匹配等。

1.1栈的实现

栈可以通过数组或链表来实现。下面是一个使用Python列表实现的栈示例：

classStack:

def__init__(self):

初始化一个空栈

self.items=[]

defis_empty(self):

判断栈是否为空

returnlen(self.items)==0

defpush(self,item):

向栈顶添加一个元素

self.items.append(item)

defpop(self):

从栈顶移除一个元素

ifnotself.is_empty():

returnself.items.pop()

else:

raiseException(栈为空，无法执行pop操作)

defpeek(self):

返回栈顶元素，但不移除

ifnotself.is_empty():

returnself.items[-1]

else:

raiseException(栈为空，无法执行peek操作)

defsize(self):

返回栈中元素的数量

returnlen(self.items)

1.2示例：括号匹配

我们可以使用栈来检查一个字符串中的括号是否正确匹配。例如，对于字符串((()))，括号是正确匹配的；而对于字符串(()))(，括号没有正确匹配。

defis_parentheses_matched(parentheses_str):

检查括号是否正确匹配

stack=Stack()

forcharinparentheses_str:

ifchar==(:

stack.push(char)

elifchar==):

ifstack.is_empty():

returnFalse

stack.pop()

returnstack.is_empty()

#测试

print(is_parentheses_matched(((()))))#输出：True

print(is_parentheses_matched((()))())#输出：False

2队列的基本概念

队列（Queue）是一种线性数据结构，其特点是先进先出（FirstInFirstOut,FIFO）。队列的一端用于插入元素，称为队尾（Rear）；另一端用于删除元素，称为队首（Front）。

2.1队列的实现

队列可以通过数组或链表来实现。下面是一个使用Python列表实现的队列示例：

classQueue:

def__init__(self):

初始化一个空队列

self.items=[]

defis_empty(self):

判断队列是否为空

returnlen(self.items)==0

defenqueue(self,item):

在队尾添加一个元素

self.items.insert(0,item)

defdequeue(self):

从队首移除一个元素

ifnotself.is_empty():