第四章 栈与队列

定义：

栈（Stack）是限定仅在表尾进行插入和删除操作的线性表。 把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

栈和队列的抽象数据类型

栈的抽象数据类型 ADT(Abstract Data Type) 栈（Stack） Data 同线性表，元素具有相同的类型，相邻元素具有前驱和后继关系。 Operation InitStack(*S):初始化操作，建立一个空栈S。 Destroy(*S):若栈存在，则销毁它 ClearStack(*S):将栈清空 StackEmpty(*S):若栈为空，返回true，否则返回false GetTop(*S):若栈存在且非空，用e返回S的栈顶元素 Push(*S,e):若栈S存在，插入新元素e到栈S中并称为栈顶元素 Pop(*S,*e):删除栈S中栈顶元素，并用e返回其值 StackLength(S):返回S中的元素个数 endADT 队列的抽象数据类型 ADT(Abstract Data Type) 队列（Queue） Data 同线性表，元素具有相同的类型，相邻元素具有前驱和后继关系。 Operation InitQueue(*Q):初始化操作，建立一个空队列Q。 Destroy(*Q):若队列Q存在，则销毁它 ClearQueue(*Q):将队列清空 QueueEmpty(*Q):若队列为空，返回true，否则返回false GetHead(*Q):若队列存在且非空，用e返回队列Q的队头元素 EnQueue(*Q,e):若队列Q存在，插入新元素e到队列Q中并称为队尾元素 DeQueue(*Q,*e):删除队列Q中队头元素，并用e返回其值 QueueLength(Q):返回Q中的元素个数 endADT