数据结构第三章：栈和队列

数据结构第三章数据结构堆栈和队列在计算机科学中，数据结构是组织和存储数据的方式，以便能够有效地对数据进行操作和处理。

在众多的数据结构中，堆栈和队列是两种非常基础且重要的结构，它们在程序设计和算法实现中有着广泛的应用。

让我们先来聊聊堆栈。

堆栈就像是一个只能从一端进行操作的容器，这个端我们称之为栈顶。

想象一下，你有一堆盘子，每次你放新盘子或者取盘子，都只能在最上面操作，这就是堆栈的基本工作方式。

堆栈遵循“后进先出”（Last In First Out，简称 LIFO）的原则。

也就是说，最后被放入堆栈的元素会首先被取出。

这在很多实际场景中都有体现。

比如，当计算机程序在执行函数调用时，会使用堆栈来保存函数的调用信息。

每次调用一个新函数，相关的信息就被压入堆栈。

当函数执行完毕返回时，相应的信息就从堆栈中弹出。

在程序实现上，堆栈可以通过数组或者链表来实现。

如果使用数组，我们需要确定一个固定的大小来存储元素。

但这种方式可能会存在空间浪费或者溢出的问题。

如果使用链表，虽然可以动态地分配内存，但在操作时需要更多的指针处理，会增加一些复杂性。

接下来，让看看如何对堆栈进行基本的操作。

首先是入栈操作，也称为压栈（Push）。

这就是将一个元素添加到堆栈的栈顶。

比如说，我们有一个初始为空的堆栈，现在要将元素 5 入栈，那么 5 就成为了堆栈的唯一元素，位于栈顶。

然后是出栈操作（Pop），它会移除并返回堆栈栈顶的元素。

继续上面的例子，如果执行出栈操作，就会取出 5，此时堆栈又变为空。

除了入栈和出栈，我们还可以获取栈顶元素（Top），但不会将其从堆栈中移除。

这在很多情况下很有用，比如在进行某些判断或者计算之前，先查看一下栈顶元素是什么。

再来说说队列。

队列和堆栈不同，它就像是在银行排队的队伍，先到的人先接受服务，遵循“先进先出”（First In First Out，简称 FIFO）的原则。

队列有一个队头和一个队尾。

新元素从队尾加入，而从队头取出元素。

数据结构第三章数据结构堆栈和队列数据结构第三章数据结构堆栈和队列3.1 堆栈堆栈（Stack）是一种遵循后进先出（Last In First Out，LIFO）原则的线性数据结构。

堆栈中只有一个入口，即栈顶，所有的插入和删除操作都在栈顶进行。

3.1.1 堆栈的基本操作- Push：将元素插入到栈顶- Pop：从栈顶删除一个元素- Top：获取栈顶元素的值- IsEmpty：判断栈是否为空- IsFull：判断栈是否已满3.1.2 堆栈的实现堆栈可以使用数组或链表来实现。

- 基于数组的堆栈实现：使用一个数组和一个指针来表示堆栈，指针指向栈顶元素的位置。

Push操作时，将元素插入到指针指向的位置，然后将指针向上移动；Pop操作时，将指针指向的元素弹出，然后将指针向下移动。

- 基于链表的堆栈实现：使用一个链表来表示堆栈，链表的头结点表示栈顶元素。

Push操作时，创建一个新节点并将其插入链表的头部；Pop操作时，删除链表的头结点。

3.1.3 堆栈的应用堆栈广泛应用于各种场景，如函数调用栈、表达式求值、括号匹配等。

3.2 队列队列（Queue）是一种遵循先进先出（First In First Out，FIFO）原则的线性数据结构。

队列有两个端点，一个是入队的端点（队尾），一个是出队的端点（队首）。

3.2.1 队列的基本操作- Enqueue：将元素插入到队尾- Dequeue：从队首删除一个元素- Front：获取队首元素的值- Rear：获取队尾元素的值- IsEmpty：判断队列是否为空- IsFull：判断队列是否已满3.2.2 队列的实现队列可以使用数组或链表来实现。

- 基于数组的队列实现：使用一个数组和两个指针来表示队列，一个指针指向队首元素，一个指针指向队尾元素的下一个位置。

Enqueue操作时，将元素插入到队尾指针所指向的位置，然后将队尾指针向后移动；Dequeue操作时，将队首指针指向的元素弹出，然后将队首指针向后移动。

第三章栈和队列【学习目标】1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。

2. 熟练掌握栈类型的两种实现方法。

3. 熟练掌握循环队列和链队列的基本操作实现算法。

4. 理解递归算法执行过程中栈的状态变化过程。

【重点和难点】栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。

【知识点】顺序栈、链栈、循环队列、链队列【学习指南】在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。

本章要求必须完成的算法设计题为：3.15，3.17，3.19，3.22，3.28，3.30，3.31，3.32。

其中前4个主要是练习栈的应用，后4个主要是有关队列的实现方法的练习。

【课前思考】1.什么是线性结构？简单地说，线性结构是一个数据元素的序列。

2.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n 的次序往上叠的，那么使用时候的次序应是什么样的？必然是依从上往下的次序，即n,…,2,1。

它们遵循的是"后进先出"的规律，这正是本章要讨论的"栈"的结构特点。

3.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？是"排队"。

在计算机程序中，模拟排队的数据结构是"队列"。

[引言]栈和队列是两种操作受限的线性表，是两种常用的数据类型通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

线性表栈队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)1≤i≤n+1Delete(L, i) Delete(S, n) Delete(Q, 1)1≤i≤n即线性表允许在表内任一位置进行插入和删除；而栈只允许在表尾一端进行插入和删除；队列只允许在表尾一端进行插入，在表头一端进行删除。

1第3章栈和队列3.1 栈3.2 队列2栈和队列是两种特殊的线性表，其特殊性在于插入和删除运算的限制上。

这两种线性结构在程序设计中经常使用。

33.1 栈3.1.1 栈的抽象数据类型3.1.2 顺序栈3.1.3 链式栈3.1.4 栈的应用举例3.1.5 栈与递归43.1 栈(stack)栈是一种限定仅在一端进行插入和删除操作的线性表。

插入：入栈（压栈） 删除：出栈（退栈） 插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）。

特征：后进先出(LIFO表，Last-In First-Out)。

k 0k 1k 2k 3栈底栈顶出栈入栈53.1.1 栈的抽象数据类型template <class ELEM> class Stack {public:void clear(); // 清空bool push(const T item); // 入栈bool pop(T& item); // 出栈bool top(T& item); // 返回栈顶内容bool is Empty(); //判栈是否空bool isFull(); // 判栈是否满};6栈的实现顺序栈采用顺序存储结构表示的栈链式栈采用链式存储结构表示的栈7template <class T>class arrStack : public Stack<T> {private:int mSize; // 栈容量int top; // 栈顶指针，初始为-1T *st; // 存放栈内容的连续空间public:arrStack(int size) { mSize=size; top=-1; st=new T[mSize];}arrStack() {mSize = 0; top = -1; st = null;}~arrStack() { delete[] st; }void clear() { top = -1;}bool push(const T item);bool pop(T& item);bool top(T& item);};3.1.2 顺序栈8template <class T>bool arrStack<T>::push(const T item) {if (top==mSize-1){cout<<"栈满"<endl;return false;}else {st[++top]=item;return true;}}k 0k 1k 2k 3top top栈空9自动解决栈溢出的入栈操作template <class T>bool arrStack<T>::push(const T item) {if (top==mSize-1){ // 扩展存储空间T * new2St = new T[mSize*2];for (i=0;i<top ;i++) newst[i]=st[i];delete [] st;st=newSt;mSize *=2;}st[++top]=item;return true;}10template <class T>bool arrStack<T>::pop(T& item) {if (top==-1){cout<<“栈为空，不能执行出栈操作"<endl;return false;}else {item = st[top--];return true;}}11template <class T>bool arrStack<T>::top(T& item) {if (top==-1){cout<<“栈为空，不能读取栈顶元素"<endl;return false;}else {item = st[top ];return true;}}123.1.3 链式栈\top13template <class T>class lnkStack : public Stack<T>{private:Link<T>*top; // 头指针int size; // 结点个数public:lnkStack(int defSize) { top=NULL; size=0; }~lnkStack() { clear(); }void clear();bool push(const T item);bool pop(T& item);bool top(T& item);}；14template <class T>void lnkStack::clear(){while (top!=NULL) {Link<T>* temp = top;top = top->next;delete temp;}size=0;}template <class T>bool lnkStack::push(const T item){Link<T>* tmp=new Link<T >(item, top );top=tmp;size++;return true;}template <class T>bool lnkStack::pop(T& item) {Link<T>* item;if (size==0){cout<<"栈空"<<endl;return false;}item=top->data;tmp=top->next;delete top;top=tmp;size--;return true;}153.1.4 栈的应用举例数制转换 迷宫问题表达式括号匹配检验 表达式求值 背包问题161.数制转换（1348）10=（2504）8==========================N N/8 N%81348 168 416821 021 2 52 0 2while (N) {N%8入栈；N/8=>N;}while (栈非空）{出栈；输出；}17//将非负十进制整数转换成八进制输出void conversion( ){Stack s;cin>>N;while (N){s.push( N%8); N=N/8;}while (!s.isEmpty()){s.pop(e); cout<<e;}}182.迷宫问题1234567891011121314151617181213141516171819201419*1234o o o o oo o o o o o oo o o o o o入口出口20*1234入口出口0 1 2 3 4 5 6 7 8 9 10 1112345687109OO21算法基本思路“穷举求解”，即从入口出发，沿某一方向向前试探，若能走通，则继续往前走；否则原路退回，换一个方向再继续试探，直到走到出口或确定无路可走为止。

第3章数据结构栈和队列数据结构是计算机科学中重要的基础知识之一，它是用于组织和管理数据的方法。

栈和队列是其中两种常见的数据结构，它们分别以后进先出（Last In First Out，LIFO）和先进先出（First In First Out，FIFO）的方式操作数据。

本文将详细介绍栈和队列的概念、特点以及应用。

一、栈栈是一种限制仅在表尾进行插入和删除操作的线性表。

插入和删除操作称为入栈和出栈，即数据项的入栈相当于把数据项放入栈顶，而数据项的出栈相当于从栈顶移除数据项。

栈具有后进先出的特点，即后入栈的数据项先出栈，而最先入栈的数据项最后出栈。

类比现实生活中的例子就是一叠盘子，我们只能从最上面取盘子或放盘子。

栈的实现方式有两种：基于数组和基于链表。

基于数组的栈实现相对简单，通过一个数组和一个指向栈顶的指针来完成栈的操作。

基于链表的栈实现则需要定义一个节点结构，每个节点包含一个数据域和一个指向下一个节点的指针，通过头指针来操作栈。

栈的应用非常广泛，比如浏览器中的返回功能就是通过栈来实现的。

当我们点击浏览器的返回按钮时，当前页面会入栈，点击前进按钮时，当前页面会出栈。

在编程中，栈也被广泛应用，比如函数调用栈用于存储函数调用的上下文信息。

二、队列队列是一种限制仅在表头删除和在表尾插入的线性表。

表头删除操作称为出队列，表尾插入操作称为入队列。

和栈不同，队列采用先进先出的原则，即最先入队列的元素最先出队列。

队列的实现方式也有两种：基于数组和基于链表。

基于数组的队列实现和栈类似，通过一个数组和两个指针（一个指向队头，一个指向队尾）来完成队列的操作。

基于链表的队列实现则需要定义一个节点结构，每个节点包含一个数据域和一个指向下一个节点的指针，通过头指针和尾指针来操作队列。

队列同样具有广泛的应用，比如操作系统中的进程调度就是通过队列来实现的。

CPU会按照进程到达的顺序，依次从队列中取出进程进行执行。

在编程中，队列也常用于解决一些需要按顺序处理数据的问题。