数据结构之栈和队列应用.pptx
前言Introduction 数据结构是计算机存储、组织数据的方式。是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据的运算。逻辑结构就是数据之间的关系。而按数据之间的关系来说，逻辑结构大概可以分为两种：线性结构和非线性结构（集合、树、网）。存储结构是逻辑结构的存储映像。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储（哈希表）。第1页/共21页线性表线性表线性表（Linear list）是最简单且最常用的一种数据结构。这种结构具有下列特点：l 存在一个唯一的没有前驱的（头）数据元素；l 存在一个唯一的没有后继的（尾）数据元素；l 每一个数据元素均有一个直接前驱和一个直接后继的数据元素。例如：英文字母表（英文字母表（A，B，C，Z）是一个长度为）是一个长度为26的线性表，其中的每一个字母就是一个数据元素；的线性表，其中的每一个字母就是一个数据元素；某某公公司司2006年年每每月月产产值值表表（400，420，500，600，650）(单单位位：万万元元)是是一一个个长长度度为为12的的线线性性表表，其其中中的的每每一一个个数值就是一个数据元素。数值就是一个数据元素。ABCDEZ400420500600650 第2页/共21页栈与队列栈与队列栈和队列也是线性表，不过是两种特殊的线性表。栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。因而，栈和队列也可以被称作为操作受限的线性表。栈：栈：topbottom进栈进栈出栈出栈ana2a1a0允许插入和删除的一端称为栈顶允许插入和删除的一端称为栈顶(top)，另一端称为栈底，另一端称为栈底(bottom)第一第一个进栈的元素在栈底，个进栈的元素在栈底，最后最后一个进栈的元素在栈顶，一个进栈的元素在栈顶，第一第一个出栈的元素为栈顶元素，个出栈的元素为栈顶元素，最后最后一个出栈的元素为栈底元素一个出栈的元素为栈底元素栈的特点：后进先出栈的特点：后进先出LIFO（Last In First Out）第3页/共21页栈与队列栈与队列栈和队列也是线性表，不过是两种特殊的线性表。栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。因而，栈和队列也可以被称作为操作受限的线性表。队列：队列：出队出队进队进队队首队首(head)队尾队尾(tail)qn-1qi+1qiq1q0允许插入的一端称为队尾（允许插入的一端称为队尾（tail），另一端称为队头），另一端称为队头(head)第一第一个个进队的进队的元素元素在队首，在队首，最后最后一个一个进队的进队的元素元素在队尾，在队尾，第一第一个个出队的出队的元素元素为队首元素为队首元素，最后最后一个一个出队的出队的元素元素为队尾元素为队尾元素队列的特点：先进先出队列的特点：先进先出FIFO（First In First Out）第4页/共21页栈应用：括号匹配栈应用：括号匹配问题描述现在，有一行括号序列，请你检查这行括号是否配对。输入第一行输入一个数N（0N=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有,(,)四种字符输出每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No样例输入3()()()样例输出NoNoYes()0构建栈：构建栈：获取符号字符串获取符号字符串(bool match(char str,int length)stack s;for(int i=0;ilength;i+)switch(stri)case(:case:s.push(stri);break;case):if(s.top()=()s.pop();else return false;break;case:if(s.top()=)s.pop();else return false;break;if(s.empty()return true;else return false;第5页/共21页问题描述某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。Input本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。Output共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。SampleInput22040SampleOutput171911937构建队列构建队列1：构建队列构建队列2：1357911 13 15 17 19123456711 12 13 14 15 16 17 18 19 208910队列应用：新兵训练队列应用：新兵训练队首队首第6页/共21页问题描述某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。Input本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。Output共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。SampleInput22040SampleOutput171911937构建队列构建队列1：构建队列构建队列2：1357911 13 15 17 19137913 15 19队列应用：新兵训练队列应用：新兵训练队首队首第7页/共21页问题描述某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。Input本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。Output共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。SampleInput22040SampleOutput171911937构建队列构建队列1：构建队列构建队列2：1713 19137913 15 19队列应用：新兵训练队列应用：新兵训练队首队首第8页/共21页问题描述某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。Input本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。Output共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。SampleInput22040SampleOutput171911937构建队列构建队列1：构建队列构建队列2：1713 191719队列应用：新兵训练队列应用：新兵训练队首队首第9页/共21页队列应用：新兵训练队列应用：新兵训练void train(int num)bool t=false,flag=false;for(int i=0;inum;i+)st.push(i+1);while(1)if(numberOff(false,2)=true)t=false;break;if(numberOff(true,3)=true)t=true;break;while(!st.empty()if(flag)printf();printf(%d,st.front();st.pop();flag=true;printf(n);bool numberOff(bool t,int num)if(st.size()=3)return true;int n=0;t=!t;while(!s!t.empty()n=n%num+1;/n值在1和2之间切换；if(n!=num)st.push(s!t.front();s!t.pop();return false;queue s2;int main()int row,num;scanf(%d,&row);while(row-)scanf(%d,&num);train(num);return 0;第10页/共21页栈应用：表达式计算栈应用：表达式计算问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入一行，包含一个表达式。输出格式输出这个表达式的值。样例输入1-2+3*(4-5)样例输出-4数据规模和约定表达式长度不超过100，表达式运算合法且运算过程都在int内进行。1-2+3*(4-5)0构建符号栈：构建符号栈：获取表达式字符串获取表达式字符串构建操作数栈：构建操作数栈：#+-*/()+-*/(#-*/(#-*/(#-*/(#-1运算运算+-3=-4值得注意的有几个地方：值得注意的有几个地方：数据存在负数（即“-”是单目运算符）数据是多位数第14页/共21页+-栈应用：表达式计算栈应用：表达式计算问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入一行，包含一个表达式。输出格式输出这个表达式的值。样例输入1-2+3*(4-5)样例输出-4数据规模和约定表达式长度不超过100，表达式运算合法且运算过程都在int内进行。1-2+3*(4-5)0构建符号栈：构建符号栈：获取表达式字符串获取表达式字符串设计后缀表达式字符串设计后缀表达式字符串123*(45-构建数据栈：构建数据栈：运算运算=-1第15页/共21页*-栈应用：表达式计算栈应用：表达式计算问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入一行，包含一个表达式。输出格式输出这个表达式的值。样例输入1-2+3*(4-5)样例输出-4数据规模和约定表达式长度不超过100，表达式运算合法且运算过程都在int内进行。1-2+3*(4-5)0构建符号栈：构建符号栈：获取表达式字符串获取表达式字符串设计后缀表达式字符串设计后缀表达式字符串345构建数据栈：构建数据栈：运算运算=-1+-1第16页/共21页*栈应用：表达式计算栈应用：表达式计算问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入一行，包含一个表达式。输出格式输出这个表达式的值。样例输入1-2+3*(4-5)样例输出-4数据规模和约定表达式长度不超过100，表达式运算合法且运算过程都在int内进行。1-2+3*(4-5)0构建符号栈：构建符号栈：获取表达式字符串获取表达式字符串设计后缀表达式字符串设计后缀表达式字符串构建数据栈：构建数据栈：运算运算=-1+3-1-3第17页/共21页栈应用：表达式计算栈应用：表达式计算问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入一行，包含一个表达式。输出格式输出这个表达式的值。样例输入1-2+3*(4-5)样例输出-4数据规模和约定表达式长度不超过100，表达式运算合法且运算过程都在int内进行。1-2+3*(4-5)0构建符号栈：构建符号栈：获取表达式字符串获取表达式字符串设计后缀表达式字符串设计后缀表达式字符串构建数据栈：构建数据栈：运算运算=-1+-4-3第18页/共21页栈应用：表达式计算栈应用：表达式计算问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入一行，包含一个表达式。输出格式输出这个表达式的值。样例输入1-2+3*(4-5)样例输出-4数据规模和约定表达式长度不超过100，表达式运算合法且运算过程都在int内进行。1-2+3*(4-5)0构建符号栈：构建符号栈：获取表达式字符串获取表达式字符串设计后缀表达式字符串设计后缀表达式字符串构建数据栈：构建数据栈：运算运算-4需要思考一下数据是多位数时该怎么处理需要思考一下数据是多位数时该怎么处理需要思考一下数据是多位数时该怎么处理需要思考一下数据是多位数时该怎么处理？第19页/共21页20THANK YOU第20页/共21页感谢您的观看！第21页/共21页
