《数据结构之栈和队列应用》由会员分享，可在线阅读，更多相关《数据结构之栈和队列应用（21页珍藏版）》请在金锄头文库上搜索。
1、,数据结构之栈与队列,重庆电子工程职业学院软件学院,前言,Introduction,数据结构是计算机存储、组织数据的方式。是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。 数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据的运算。 逻辑结构就是数据之间的关系。而按数据之间的关系来说，逻辑结构大概可以分为两种：线性结构和非线性结构（集合、树、网）。 存储结构是逻辑结构的存储映像。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储（哈希表）。,线性表（Linear li
2、st）是最简单且最常用的一种数据结构。这种结构具有下列特点： 存在一个唯一的没有前驱的（头）数据元素； 存在一个唯一的没有后继的（尾）数据元素； 每一个数据元素均有一个直接前驱和一个直接后继的数据元素。 例如： 英文字母表（A，B，C，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元素； 某公司2006年每月产值表（400，420，500，600，650）(单位：万元)是一个长度为12的线性表，其中的每一个数值就是一个数据元素。,栈和队列也是线性表，不过是两种特殊的线性表。 栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和
3、队列也可以被称作为操作受限的线性表。,栈：,top,bottom,进栈,出栈,允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom),第一个进栈的元素在栈底， 最后一个进栈的元素在栈顶， 第一个出栈的元素为栈顶元素， 最后一个出栈的元素为栈底元素,栈的特点：后进先出LIFO（Last In First Out）,栈和队列也是线性表，不过是两种特殊的线性表。 栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。,队列：,出队,进队,队首(head),队尾(tail),qn-1,qi+1,q
4、i,q1,q0,允许插入的一端称为队尾（tail），另一端称为队头(head),第一个进队的元素在队首， 最后一个进队的元素在队尾， 第一个出队的元素为队首元素， 最后一个出队的元素为队尾元素,队列的特点：先进先出FIFO（First In First Out）,问题描述 现在，有一行括号序列，请你检查这行括号是否配对。 输入 第一行输入一个数N（0N=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有“,“,“(“,“)“四种字符 输出 每组输入数据的输出占一行，如果该字符串
5、中所含的括号是配对的，则输出Yes,如果不配对则输出No 样例输入 3 () () () 样例输出 No No Yes,构建栈：,获取符号字符串,(,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.em
6、pty()return true; else return false; ,问题描述 某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠 拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。 Input 本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。 Output 共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。
7、Sample Input 2 20 40 Sample Output 1 7 19 1 19 37,构建队列1：,构建队列2：,1,3,5,7,9,11,13,15,17,19,1,2,3,4,5,6,7,11,12,13,14,15,16,17,18,19,20,8,9,10,队首,队首,问题描述 某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠 拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人
8、数不超过三人为止。 Input 本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。 Output 共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。 Sample Input 2 20 40 Sample Output 1 7 19 1 19 37,构建队列1：,构建队列2：,1,3,5,7,9,11,13,15,17,19,1,3,7,9,13,15,19,队首,队首,问题描述 某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠 拢，再
9、从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。 Input 本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。 Output 共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。 Sample Input 2 20 40 Sample Output 1 7 19 1 19 37,构建队列1：,构建队列2：,1,7,13,19,1,3,7,9,13,15,19,队首,队首,问题描述 某部队进行新兵队列训练，将新兵从
10、一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠 拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。 Input 本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。 Output 共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。 Sample Input 2 20 40 Sample Output 1 7 19 1 19 37,构建队列1：,构建
11、队列2：,1,7,13,19,1,7,19,队首,队首,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“);
12、,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“, ,问题描述 输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。 输入格式 输入一行，包含一个表达式。 输出格式 输出这个表达式的值。
13、 样例输入 1-2+3*(4-5) 样例输出 -4 数据规模和约定 表达式长度不超过100，表达式运算合法且运算过程都在int内进行。,构建符号栈：,获取表达式字符串,构建操作数栈：,#,1,运算,-,2,=,-1,问题描述 输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。 输入格式 输入一行，包含一个表达式。 输出格式 输出这个表达式的值。 样例输入 1-2+3*(4-5) 样例输出 -4 数据规模和约定 表达式长度不超过100，表达式运算合法且运算过程都在int内进行。,构建符号栈：,获取表达式字符串,构建操作数栈：,#,-1,运算,+,3,*,(,4,-,5,=,
14、-1,问题描述 输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。 输入格式 输入一行，包含一个表达式。 输出格式 输出这个表达式的值。 样例输入 1-2+3*(4-5) 样例输出 -4 数据规模和约定 表达式长度不超过100，表达式运算合法且运算过程都在int内进行。,构建符号栈：,获取表达式字符串,构建操作数栈：,#,-1,运算,+,3,*,-1,=,-3,问题描述 输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。 输入格式 输入一行，包含一个表达式。 输出格式 输出这个表达式的值。 样例输入 1-2+3*(4-5) 样例输出 -4 数据规模和
15、约定 表达式长度不超过100，表达式运算合法且运算过程都在int内进行。,构建符号栈：,获取表达式字符串,构建操作数栈：,#,-1,运算,+,-3,=,-4,值得注意的有几个地方： 数据存在负数（即“-”是单目运算符） 数据是多位数,+,-,问题描述 输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。 输入格式 输入一行，包含一个表达式。 输出格式 输出这个表达式的值。 样例输入 1-2+3*(4-5) 样例输出 -4 数据规模和约定 表达式长度不超过100，表达式运算合法且运算过程都在int内进行。,构建符号栈：,获取表达式字符串,设计后缀表达式字符串,1,2,3,*,(,4,5,-,构建数据栈：,运算,=,-1,*,-,问题描述 输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。 输入格式 输入一行，包含一个表达式。 输出格式 输出这个表达式的值。 样例输入 1-2+3*(4-5) 样例输出 -4 数据规模和约定 表达式长度不超过100，表达式运算合法且运算过程都在int内进行。,构建符号栈：,获取表达式字符串,设计后缀表达式字符串,3,4,5,构建数据栈：,运算,=,-1,+,-1,*,问题描述 输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除
