栈和队列基础知识

1、栈和队列基础知识C程 序 设 计CONTENTS 栈相关知识 队列相关知识 总结栈相关知识1.栈相关知识l 栈： 限制仅在一端进行插入和删除运算的线性表栈顶栈顶栈底栈底入栈入栈出栈出栈l 栈顶：进行插入、删除的一端l 栈底：除栈顶外的另一端.a2a1an栈是后进先出表（ LIFO ） 栈的概念栈的概念 栈的基本操作栈的基本操作1.栈相关知识l 置空栈 createEmptyStack(void)：空栈；l 判栈空 isEmptytack（st）：这是一个布尔函数。若st为空栈，则函数值为“真”, 否则为“假”。l 入栈 push（st，x）：在st的顶部插入(亦称压入）元素 x。l 出栈 po

2、p（st）：删除（亦称弹出）栈st的顶部元素。l 取栈顶 top（st）：取栈st的顶部元素。1.栈相关知识 栈的两种实现方式栈的两种实现方式顺序栈和链栈 顺序栈顺序栈利用一组地址连续的存储单元依次存放自栈顶到栈底的数据元素。#define MAXNUM 100 /* 栈中能达到的最大容量栈中能达到的最大容量*/ typedef int DataType; /* 定义栈元素的数据类型定义栈元素的数据类型* /struct SeqStack /* 顺序栈类型定义顺序栈类型定义 */DataType sMAXNUM;int t; /*栈顶栈顶*/；typedef struct SeqStack,

3、*PSeqStack;PSeqStack pastack; /*指向顺序栈的指针变量指向顺序栈的指针变量*/t是 int型简单变量 ,指向栈顶元素在栈中的位置(序号) 6 5 4 3 2 1 0-11.栈相关知识 顺序栈顺序栈约定:1、栈空时，t=-12、栈满时，t=MAXNUM-13、栈顶元素：St4、若t=-1时，执行出栈操作,产生“下溢”5、若t=MAXNUM-1时，执行入栈,产生“上溢”ABCD入栈和出栈1.栈相关知识 链栈链栈栈的链式存储结构称为链栈。由于只能在链表头部进行操作，故链栈没有必要像单链表那样需附加头结点。栈顶指针top就是链表的头指针head。 typedef int

4、DataType; typedef struct Node /* 结点结构结点结构 */ DataType info; pNode link; *pNode;struct LinkStack/* 链接栈类型定义链接栈类型定义 */pNode top;/* 指向栈顶结点指向栈顶结点 */;typedef struct LinkStack *PLinkStack;栈的链接表示栈的链接表示 top info link .队列相关知识2. 队列相关知识l 队列：只允许在表的一端进行插入，而在另一端进行删除l 队头：允许删除的一端l 队尾：允许插入的一端出队入队队头队尾a1 a2 an . 队列是先进先

5、出表（FIFO）2. 队列相关知识 队列的基本操作队列的基本操作l 创建一个空队列 Queue createEmptyQueue ( void ) l 判队列是否为空队列 int isEmptyQueue ( Queue qu ) l 往队列中插入一个元素 void enQueue ( Queue qu, DataType x ) l 从队列中删除一个元素 void deQueue ( Queue qu ) l 求队列头部元素的值 DataType frontQueue ( Queue qu ) 2. 队列相关知识 队列的两种实现方式队列的两种实现方式顺序队列和链队列 顺序队列顺序队列队列的顺

6、序存储结构简称为顺序队列 由于队列的队头和队尾的位置均是变化的，因而要设置两个指针，分别指示当前队头元素和队尾元素在向量空间中的位置。#define MAXNUM 100struct SeqQueue datatype qMAXNUM; int f, r;typedef struct SeqQueue *PSeqQueue;PSeqQueue sq;2. 队列相关知识 顺序队列的入队和出队操作顺序队列的入队和出队操作队列空： sq-f=0; sq-r=0; 入队： sq-qsq-r=x; sq-r+; 出队： sq-f+; 76543210frxryrf队列长度:（sq-r) - (sq-f)

7、2. 队列相关知识 链队列链队列队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。 显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表上的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一地确定。typedef struct Node DataType info; pNodelink; *pNode;struct LinkQueue PNodef; PNoder;typedef struct LinkQueue, *PLinkQueue; k0 k1 k2 kn-1.ff总结3.总结栈是限制仅在一端进行插入和删除运算的线性表，它是一种后进先出（LIFO）的数据结构。进行插入、删除的一端称为栈顶。栈有两种实现方式，分别为顺序栈和链栈。队列是只允许在表的一端进行插入，而在另一端进行删除的线性表，它是一种先进先出（FIFO)的数据结构，允许删除的一端称为队头，允许插入的一端称为队尾。队列有两种实现方式，