课件版数据结构ch03stackqueue

1、第三章 栈和队列本章内容3.1 栈3.1.1 栈的定义及基本运算3.1.2 栈的存储结构和实现3.1.3 栈的应用3.2 队列3.2.1 队列的定义及基本运算3.2.2 队列的存储结构和实现3.2.3 队列的应用3.1.1 栈的定义及基本运算栈(Stack)的定义栈是仅限定在表尾进行插入和删除操作的线性表。术语栈顶(top)栈的表尾栈底(bottom) 栈的表头空栈没有元素的栈入栈(push) 向栈顶压入元素出栈(pop) 从栈顶弹出元素anan-1 .a2a1栈底栈顶入栈出栈栈的特点栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。3.1.1 栈的定义及基本运算栈的运算演

2、示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。DCBAABCDDCBA 3.1.1 栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ABCDE操作序列：出栈序列： 元素A入栈A A 元素B入栈B B 元素C入栈C C3.1.1 栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ DE操作序列：出栈序列： 元素A

3、入栈A 元素B入栈B 元素C入栈 元素C出栈CC 元素B出栈B3.1.1 栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ DE操作序列：出栈序列： 元素A入栈A 元素B入栈 元素C入栈 元素C出栈C 元素B出栈B 元素D入栈D D 元素D出栈D 元素A出栈A3.1.1 栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ E操作序列：出栈序列： 元

4、素A入栈 元素B入栈 元素C入栈 元素C出栈C 元素B出栈B 元素D入栈 元素D出栈D 元素A出栈A 元素E入栈EE 元素E出栈E栈的基本运算InitStack(&S): 初始化栈SStackEmpty(): 判断栈是否为空Push(e): 将元素e放入栈顶Pop(e): 移走栈顶的元素，同时由e带回该元素的值Gettop(): 获取栈顶的元素，但不从栈中移走3.1.1 栈的定义及基本运算3.1.2 栈的存储结构和实现顺序栈栈的顺序存储结构a1a2an-1an线性表anan-1 .a2a1栈栈底栈顶6F28an6F26an-1 . .6F02a26F00a1栈的顺序存储映象basetop3.1

5、.2 栈的存储结构和实现顺序栈栈的顺序存储结构6F28an6F26an-1 . .6F02a26F00a1栈的顺序存储映象basetop顺序栈基本操作的实现StackEmpty():top = = basePush(e): *top+ = ePop(e): e = *-topGettop(): e = *(top-1)思考：为何不用top指向栈顶元素？3.1.2 栈的存储结构和实现顺序栈的C语言实现结构定义/ -栈的顺序存储表示-# define STACK_INIT_SIZE 100;# define STACKINCREMENT 10;typedef struct ElemType *ba

6、se; /栈底指针，栈构造前和销毁后为空ElemType *top; /栈顶指针，指向栈顶元素的下一位置int stacksize; /当前分配的栈的存储空间数SqStack; 3.1.2 栈的存储结构和实现顺序栈的C语言实现基本操作的实现(1) 初始化Status InitStack(SqStack &S)/构造一个空栈S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType) ;if(!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE ;

7、return OK;/InitStack3.1.2 栈的存储结构和实现顺序栈的C语言实现基本操作的实现(2) 元素入栈Status Push(SqStack &S, ElemType e)/构造一个空栈if (S.top S.base = S.stacksize) return ERROR;*S.top = e;S.top+;return OK;/Push请自学其他操作的实现算法。3.1.2 栈的存储结构和实现顺序栈的另一种实现结构定义/ -栈的顺序存储表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef struct

8、 ElemType *base; /栈底指针，栈构造前和销毁后为空 int top; /栈顶指针，指向栈顶元素的下一位置int stacksize; /当前分配的栈的存储空间数SqStack; 3.1.2 栈的存储结构和实现链栈栈的链式存储anan-1 .a2a1栈栈底栈顶S栈的链式存储an an-1 a1a2 思考 链栈是否需要另外设置头指针？ 建立链栈适合用哪种插入法？ 链栈的基本操作的实现。STL中的栈#include #include #include using namespace std;int main() stack s; s.push(1); s.pop(); s.push(

9、10); s.push(11); cout s.top() endl; cout s.size() endl; cout s.empty() endl; return 0; The C+ Stack is a container adapter that gives the programmer the functionality of a stack - specifically, a FILO (first-in, last-out) data structure Stack constructors:construct a new stackempty:true if the stack

10、 has no elementspop:removes the top element of a stackpush:adds an element to the top of the stacksize:returns the number of items in the stacktop:returns the top element of the stack.#include #include using namespace std;struct ElemType int x; int y;void main( ) int i, n=7; ElemType t; stack S; for

11、(i=0;in;i+) t.x = i; t.y = i*i; S.push(t); cout S.size() endl; while (!S.empty() t = S.top(); coutt.yt; S.pop(); 3.1.3 栈的应用根据栈的FILO特性，用作某些处理问题的工具。数制转换例： 4310 = 1010112被除数除数商余数432211212101102505221221012010 输出3.1.3 栈的应用括号匹配设一个表达式中可以包含三种括号：“(”和“)”、“”和“”、“”和“”，并且这三种括号可以按照任意的次序嵌套使用，考查表达式中的括号是否匹配。例如： .(.

12、).).例：a=b+(c-d)*(e-f);while (m(a8+t) m=m+1; t=t-1;实现方法利用栈进行表达式中的括号匹配自左至右扫描表达式，若遇左括号，则将左括号入栈，若遇右括号，则将其与栈顶的左括号进行匹配，若配对，则栈顶的左括号出栈，否则出现括号不匹配错误。思考：匹配的充要条件？3.1.3 栈的应用举例迷宫问题寻找一条从入口到出口的通路。8123456781234567入口出口前进方向： 上(北)、下(南)、左(西)、右(东)东南北西 走步规则：首先从向下开始，按照逆时针方向搜索下一步可能前进的位置栈3.1.3 栈的应用迷宫问题8123456781234567(1,1)i(

13、2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i栈3.1.3 栈的应用迷宫问题8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i (5,2)i(5,3)i(6,3)i(6,4)i(8,8)iiiiii3.1.3 栈的应用迷宫问题迷宫的表示const int N=8;struct PosType int x, y;char mazeNN; /位置上的标识，是否可通过迷宫初始化用二层嵌套循环对迷宫赋值迷宫求解(见教材算法)输出栈中的路径Status MazePath(maze, start, end) /若迷宫中存

14、在一条从入口start到出口end的通道，则求出这样的一条通路 InitStack(S); curpos = start; curstep = 1; do if (pass(curpos) /当前位置可以通过 Mark(maze,curpos); /留下记号 e = (curstep,curpos,1); push(S,e); /加入路径 if (curpos=end) return true; /到达出口 curpos = NextPos(curpos,1) ;/下一个位置 curstep+; else /当前位置不能通过 if (!StackEmpty(S) pop(S,e); /退回一步

15、 while(e.di=4 & ! !StackEmpty(S) /当前位置是死胡同 Markdead(maze,e.seat)；pop(S,e); /留下记号，沿来路返回 if (e.di1) return n*f(n-1); else return 1; void main( ) int n=4; printf(“%ld”,f(n); 栈与递归3.2.1 队列的定义及基本运算队列(Queue)的定义队列是仅限定在表尾进行插入和表头进行删除操作的线性表。术语队头(front)队列的表头，即只允许删除的一端。队尾(rear) 队列的表尾，即只允许插入的一端。入队(EnQueue) 向队尾插入元

16、素。出队(DeQueue) 从队头删除元素。队列的特点队列的修改是按先进先出的原则进行的。因此，队列称为先进先出表（FIFO）。a1 a2 ai an队头front队尾rear出队入队3.2.1 队列的定义及基本运算队列的基本运算InitQueue(&Q): 初始化队列QQueueEmpty(): 判断队列是否为空EnQueue(e): 将元素e放入队尾DeQueue(e): 移走队头元素，由e带回该元素的值GetFront(): 获取队头元素的值，但不从队列中移走该元素Length(): 计算并返回队列中元素的个数3.2.2 队列的存储结构和实现链队列队列的链式存储结构 队列的链式存储a1

17、a2 anai Q.frontQ.reara1 a2 ai an队头front队尾rear出队入队3.2.2 队列的存储结构和实现链队列的C语言实现 /-单链队列的存储结构-typedef struct QNode /链表结点类型 QElemType data; struct QNode *next;QNode,*QueuePtr; typedef struct /队列类型 QueuePtr front; /队头指针 QueuePtr rear; /队尾指针LinkQueue;data Q.frontQ.rearStatus InitQueue(LinkQueue &Q) /构造一个空队列QQ

18、.front= Q.rear = (QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next = NULL;return OK;(2) 入队Status EnQueue(LinkQueue &Q, QElemType e)/将元素e插入到队列Q中p = (QueuePtr)malloc(sizeof(QNode);if (!p) exit(OVERFLOW);p-data = e;p-next=NULL;Q.rear-next = p; Q.rear = p;return OK;3.2.2 队列的存储结构和实现

19、链队列基本操作的实现(1) 初始化 Q.frontQ.rearStatus DeQueue(LinkQueue &Q, QElemType &e)/若队列不空，则队头元素出队列，用e返回其值，返回OK /否则返回ERROR if (Q.rear = Q.front) return ERROR; p = Q.front - next; e = p - data; Q.front-next = p - next; if (Q.rear = p) Q.rear = Q.front; free(p); return OK;3.2.2 队列的存储结构和实现链队列基本操作的实现(1) 初始化 (2) 入队

20、列 (3) 出队列 Q.frontQ.rear思考：如果不设置头结点，需要考虑那些特殊情况？3.2.2 队列的存储结构和实现循环队列队列的顺序存储结构a1 a2 ai an队头front队尾rear出队入队6F36an6F26ai . .6F02a26F00a1Q.frontQ.reara1a2a3Q.frontanQ.rear012nn+1m-1循环队列循环队列的C语言实现/-循环队列的存储结构-#define MAXSIZE 100typedef struct QElemType *base; int front; int rear; SqQueue;循环队列基本操作的实现(1) 初始化S

21、tatus InitQueue(SqQueue &Q)Q.base=(QElemType *)malloc(MAXSIZE*sizeof(QElemType);if (!Q.base) exit (OVERFLOW);Q.front = Q.rear = 0;return OK;3.2.2 队列的存储结构和实现(base+Maxsize-1)base3.2.2 队列的存储结构和实现循环队列基本操作的实现(2) 入队Status EnQueue(SqQueue &Q,QElemType e) /将元素e插入队列Q的队尾if (Q.rear+1) % MAXSIZE = Q.front) retu

22、rn ERROR;Q.baseQ.rear = e;Q.rear = (Q.rear+1) % MAXSIZE;return OK;(3) 出队Status DeQueue(SqQueue &Q,QElemType &e) /删除队列Q的队头元素并用e带回if (Q.front = Q.rear) return ERROR;e = Q.baseQ.front;Q.front = (Q.front+1) % MAXSIZE;return OK;STL中的队列#include #include #include using namespace std;int main() queue q; q.p

23、ush(1); q.push(2); q.push(3); q.pop(); cout q.front() endl; cout q.back() endl; cout q.size() endl; cout q.empty() endl; return 0; The C+ Queue is a container adapter that gives the programmer a FIFO (first-in, first-out) data structure. Queue constructor:construct a new queueback:returns a referenc

24、e to last element of a queueempty:true if the queue has no elementsfront:returns a reference to the first element of a queuepop:removes the top element of a queuepush:adds an element to the end of the queuesize:returns the number of items in the queue.双端队列双端队列队头队尾出队入队出队入队输出受限的双端队列队头队尾出队入队入队双端队列输入受限的

25、双端队列队头队尾出队入队出队STL中的双端队列dequequeuedequepushpush_backpush_frontpoppop_frontpop_backfrontfrontbackbacksizesizeemptyemptySTL提供了双端队列（Double-ended Queues ）Double-ended queues are like vectors, except that they allow fast insertions and deletions at the beginning (as well as the end) of the container.at:returns an element at a specific locationback:returns a reference to last element o