数据结构3_栈和队列

栈和队列的操作是线性表操作的子集。它们是操作受限的线性表。

从数据结构的角度看&＃xff0c;是限定性的数据结构。

从数据类型的角度看&＃xff0c;是和线性表大不相同的两类重要的抽象数据类型。

3.1 栈

栈&＃xff08;Stack&＃xff09;是限定仅在表尾进行插入或删除操作的线性表。

表尾称为栈顶&＃xff08;Top&＃xff09;。

表头称为栈底&＃xff08;bottom&＃xff09;。

栈S&＃61;(a₁, a₂, a₃, …a_n,)&＃xff0c;a₁称为栈底元素&＃xff0c;a_n为栈顶元素。栈中元素按a₁、a₂、…a_n的依次进栈。

退栈的元素应为栈顶元素。换句话说&＃xff0c;栈的修改是按后进先出的原则进行的。栈又称为后进先出&＃xff08;LIFO&＃xff09;线性表。

栈的操作&＃xff1a;栈顶进行插入或删除&＃xff0c;栈的初始化、判空、取栈顶元素&＃xff1b;

栈也有两种存储表示方法&＃xff1a;顺序栈、链栈&＃xff1b;

3.2 栈的应用举例

3.3 栈与递归实现

Hanoi塔

3.4 队列

先进先出的线性表结构&＃xff1b;只允许在表的一端进行插入&＃xff0c;而在另一端删除元素&＃xff1b;

队尾、队头&＃xff1b;

Queue

队列有两种存储表示&＃xff1a;

链表表示的队列叫链队列&＃xff1b;

循环队列&＃xff1b;

3.5 离散事件模拟

银行排队问题&＃xff0c;计算一天中客户在银行逗留的平均时间&＃xff0c;模拟银行的业务活动。

客户到达和离开银行的这两个时刻发生的事情称为“事件”。整个模拟程序将按照事件发生的先后顺序进行处理。这样一种模拟程序称为事件驱动模拟。