浅谈栈和队列

1、浅谈栈和队列 1234 引言引言 在对高级语言编写的源程序进行编译时在对高级语言编写的源程序进行编译时类似于表达式括号匹配问题就是用栈来解决类似于表达式括号匹配问题就是用栈来解决的；计算机系统在处理子程序之间的调用关的；计算机系统在处理子程序之间的调用关系是，用栈来保存处理执行过程中的调用次系是，用栈来保存处理执行过程中的调用次序。现实世界中有许多问题可以用队列描述。序。现实世界中有许多问题可以用队列描述。例如，对顾客服务部门的工作往往是按照队例如，对顾客服务部门的工作往往是按照队列方式进行的，这类系统乘坐排队系统。程列方式进行的，这类系统乘坐排队系统。程序设计中，也经常使用队列记录需按照先进

2、序设计中，也经常使用队列记录需按照先进先出方式处理的数据，例如键盘缓冲区，操先出方式处理的数据，例如键盘缓冲区，操作系统中的作业调度等。作系统中的作业调度等。1 栈栈1.1 栈的概念栈的概念 栈（栈（stack）是一种特殊的线性表。作为一个）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。而在使用时，却是从后冼净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先顶上拿取，也就是说

3、，后冼的先取用，后摞上的先取用。如果我们把冼净的碗取用。如果我们把冼净的碗“摞上摞上”称为进栈（压称为进栈（压栈），把栈），把“取用碗取用碗”称为出栈（弹出），那么上例称为出栈（弹出），那么上例的特点是：后进栈的先出栈。然而，摞起来的碗实的特点是：后进栈的先出栈。然而，摞起来的碗实际上是一个线性表，只不过际上是一个线性表，只不过“进栈进栈”和和“出栈出栈”都都在最顶上进行，或者说，元素的插入和删除操作都在最顶上进行，或者说，元素的插入和删除操作都是在线性表的一端进行而已。是在线性表的一端进行而已。 栈是一种特殊的线性表。其特殊性在于栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作

4、只能在线性限定插入和删除数据元素的操作只能在线性表的一端进行。表的一端进行。 插入元素又称为进栈，删除元素又称为插入元素又称为进栈，删除元素又称为出栈。允许进行插入和删除操作的一端称为出栈。允许进行插入和删除操作的一端称为栈顶（栈顶（top），另一端称为栈（），另一端称为栈（bottom）。）。处于栈顶位置的数据元素称为栈顶元素，处处于栈顶位置的数据元素称为栈顶元素，处于栈底位置的数据元素称为栈底元素。不含于栈底位置的数据元素称为栈底元素。不含任何数据元素的栈称为空栈。任何数据元素的栈称为空栈。 1.2栈的基本操作栈的基本操作 栈除了在栈顶进行进栈与出栈外，还有初始化、栈除了在栈顶进行进栈与出

5、栈外，还有初始化、判空等操作，常用的基本操作有：判空等操作，常用的基本操作有：（1）初始化栈）初始化栈InitStack(S)。其作用是构造一个空。其作用是构造一个空栈栈S。（2）判断栈空）判断栈空EmptyStack(S)。其作用是判断是。其作用是判断是否是空栈，若栈否是空栈，若栈S为空，则返回为空，则返回1；否则返回；否则返回0。（3）进栈）进栈Push(S,x)。其作用是当栈不为满时，将。其作用是当栈不为满时，将数据元素数据元素x插入栈插入栈S中，使其为栈中，使其为栈S的栈顶元素。的栈顶元素。（4）出栈）出栈Pop(S,x)。其作用是当栈。其作用是当栈S不为空时，将不为空时，将栈顶元素赋

6、给栈顶元素赋给x，并从栈，并从栈S中删除当前栈顶元素。中删除当前栈顶元素。（5）取栈顶元素）取栈顶元素GetTop(S,x)。其作用是当栈。其作用是当栈S不不为空时，将栈顶元素赋给为空时，将栈顶元素赋给x并返回，操作结果只是读并返回，操作结果只是读取栈顶元素，栈取栈顶元素，栈S不发生变化。不发生变化。 由于栈是操作受限制的线性表，因此与线性表类似，栈也有两种由于栈是操作受限制的线性表，因此与线性表类似，栈也有两种存储结构，即顺序存储结构和链式存储结构。存储结构，即顺序存储结构和链式存储结构。1.3.11.3.1顺序栈顺序栈 栈的顺序存储结构称为顺序栈。类似于顺序表的类型定义，顺序栈栈的顺序存储

7、结构称为顺序栈。类似于顺序表的类型定义，顺序栈是用一个预设的足够长度的一维数组和一个记录栈顶元素位置的变量是用一个预设的足够长度的一维数组和一个记录栈顶元素位置的变量来实现。来实现。 1.3.21.3.2链栈链栈 用链式存储结构实现的栈称为链栈用链式存储结构实现的栈称为链栈33，链栈与不带头结点单链表，链栈与不带头结点单链表组织形式相似，因为栈的主要操作是在栈顶进行插入与删除操作，显组织形式相似，因为栈的主要操作是在栈顶进行插入与删除操作，显然将链表的第一个结点作为栈顶是最方便的，因此，没有必要如单链然将链表的第一个结点作为栈顶是最方便的，因此，没有必要如单链表那样为了操作方便附加一个头结点。

8、表那样为了操作方便附加一个头结点。 链栈的基本操作实现也有初始化栈操作，判断栈空操作，进栈操作，链栈的基本操作实现也有初始化栈操作，判断栈空操作，进栈操作，出栈操作，取栈顶元素。出栈操作，取栈顶元素。 。 1.3栈的分类栈的分类 2.1 2.1 队列的概念队列的概念 在日常生活中的排队上车，排队的规则是不允许在日常生活中的排队上车，排队的规则是不允许“插插队队”。后来的人需站在队尾，每次总是队头先上车。这。后来的人需站在队尾，每次总是队头先上车。这种先进先出的规则应用在数据结构中称为队列（种先进先出的规则应用在数据结构中称为队列（queuequeue），），队列又称为先进先出（队列又称为先进先

9、出（first in first outfirst in first out）的线性表，）的线性表，简称简称FIFOFIFO表。表。 队列也是一种特殊的线性表队列也是一种特殊的线性表44。与栈不同，其插入操作。与栈不同，其插入操作限定在线性表的一端进行，删除操作限定在线性表的另限定在线性表的一端进行，删除操作限定在线性表的另一端进行，队列插入操作又称为入队，删除操作又称为一端进行，队列插入操作又称为入队，删除操作又称为出队，允许进行插入的一端称为队尾（出队，允许进行插入的一端称为队尾（rearrear），允许进），允许进行删除的一端称为队头（行删除的一端称为队头（frontfront）。处于队

10、头位置的数据）。处于队头位置的数据元素称为队头元素。处于队尾位置的数据元素称为队尾元素称为队头元素。处于队尾位置的数据元素称为队尾元素。不含任何数据元素的队列称为空队元素。不含任何数据元素的队列称为空队。2队列队列2.2 队列的基本操作队列的基本操作 队列的除了在队头进行出队和队尾进行入队外，还有初始化、队列的除了在队头进行出队和队尾进行入队外，还有初始化、判空等操作，常用的基本操作有：判空等操作，常用的基本操作有：（1）初始化队列）初始化队列InitQueue(Q)。其作用是构造一个空队列。其作用是构造一个空队列Q。（2）判断队列空）判断队列空EmptyQueue(Q)。其作用是判断是否是空

11、队列，。其作用是判断是否是空队列，若队列若队列Q为空，则返回为空，则返回1；否则返回；否则返回0。（3）入队）入队EnQueue(Q,x)。其作用是当队列不为满时，将数据元。其作用是当队列不为满时，将数据元素素x插入队列插入队列Q的队尾，使其为队列的队尾，使其为队列Q的队尾元素。的队尾元素。（4）出队）出队DeQueue(Q,x)。其作用是当队列。其作用是当队列Q不为空时，将队头不为空时，将队头元素赋给元素赋给x，并从队列，并从队列Q中删除当前队头元素，而其后继元素成为中删除当前队头元素，而其后继元素成为队头元素。队头元素。（5）取队头元素）取队头元素GetFront(Q,x)。其作用是当队列

12、。其作用是当队列Q不为空时，不为空时，将队头元素赋给将队头元素赋给x并返回，操作结果只是读取队头元素，队列并返回，操作结果只是读取队头元素，队列Q不不发生变化。发生变化。 由于队列是操作受限制的线性表，因此与线性表类由于队列是操作受限制的线性表，因此与线性表类似，队列也有两种存储结构，即顺序存储结构和链式存似，队列也有两种存储结构，即顺序存储结构和链式存储结构。储结构。 队列的顺序存储结构需要使用一个数组和两个整型队列的顺序存储结构需要使用一个数组和两个整型变量来实现，利用数组来顺序存储队列中的所有元素，变量来实现，利用数组来顺序存储队列中的所有元素，利用两个整型变量来分别存储队首元素和队尾元

13、素的下利用两个整型变量来分别存储队首元素和队尾元素的下标位置，分别称它们为队首指针和队尾指针。标位置，分别称它们为队首指针和队尾指针。 队列也是操作受限的线性表。限定在队尾处插入，队列也是操作受限的线性表。限定在队尾处插入，而在队头处删除。而在队头处删除。 队列是先进先出（队列是先进先出（First In First Oout，FIFO）的线性表。的线性表。 约定队列的头指针约定队列的头指针front指向队列头元素前一位置，而为指针指向队列头元素前一位置，而为指针rear指向队尾元素自身。循环队列是重要数据结构，即指队列的指向队尾元素自身。循环队列是重要数据结构，即指队列的顺序存储结构。凡涉及

14、队头或队尾指针的修改都要对顺序存储结构。凡涉及队头或队尾指针的修改都要对MAXSIZE求模：求模： front=(front+1) % MAXSIZE; rear=(rear+1) % MAXSIZE; 循环队列，队空的判定条件：循环队列，队空的判定条件：rear=front； 循环队列，队满的的判定条件是：循环队列，队满的的判定条件是：(rear+1)%MAXSIZE=front； 队列的链式存储结构称为链队列。通常设附加头结点，并设队队列的链式存储结构称为链队列。通常设附加头结点，并设队头指针指向头结点，即指向第一个数据结点的前一位置。队列的尾头指针指向头结点，即指向第一个数据结点的前一位

15、置。队列的尾指针指向终端结点。指针指向终端结点。 链队列的基本操作，也是单链表操作的简化，插入只考虑在链队链队列的基本操作，也是单链表操作的简化，插入只考虑在链队列的尾部进行，删除只考虑在链队列的头部进行，其时间复杂度均列的尾部进行，删除只考虑在链队列的头部进行，其时间复杂度均为为O(1)。1. 1. 队列先进先出，栈先进后出。队列先进先出，栈先进后出。 2. 2. 对插入和删除操作的对插入和删除操作的 限定限定 。 栈是限定只能在表的栈是限定只能在表的一端进行插入和删除操作的线性表。一端进行插入和删除操作的线性表。 队列是限定只能队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表

16、。在表的一端进行插入和在另一端进行删除操作的线性表。从从 数据结构数据结构 的角度看，它们都是线性结构，即数据元的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和了它们各自的基本操作集不同外，主要区别是对插入和删除操作的删除操作的 限定限定 。栈和队列是在程序设计中被广泛使。栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按殊性，栈必须按 后进先出后进先出 的规则进行操作，而队

17、列必的规则进行操作，而队列必须按须按 先进先出先进先出 的规则进行操作。和线性表相比，它的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。定性的线性表结构。 3栈和队列的应用区别栈和队列的应用区别 3. 3. 遍历数据速度不同。栈只能从头部取数据遍历数据速度不同。栈只能从头部取数据 也就最先放入的需也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性队列怎不同，他基于地开辟临时空间，

18、保持数据在遍历前的一致性队列怎不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多。栈（快的多。栈（StackStack）是限定只能在表的一端进行插入和删除操作）是限定只能在表的一端进行插入和删除操作的线性表。队列（的线性表。队列（QueueQueue）是限定只能在表的一端进行插入和在另）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。从一端进行删除操作的线性表。从 数据结构数据结

19、构 的角度看，它们都是的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的除操作的 限定限定 。栈和队列是在程序设计中被广泛使用的两种线。栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按性数据结构，它们的特点在于基本操作的特殊性，栈必须按 后进后进先出先出 的规则进行操作，而队列必须按的规则进行操作，而队列必须按 先进先出先进先出 的规则进行操作。的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构称为限定性的线性表结构。 栈和队列在各类系统中应用广泛。堆栈技栈和队列在各类系统中应用广泛。堆栈技术被广泛应用于编译软件和程序设计，操作系术被广泛应用于编译软件和程序设计，操