使用标准库的栈和队列时，先包含相关的头文件
1#include<stack> 2#include<queue>
定义栈如下：
stack<int> stk;
定义队列如下：
queue<int> q;
栈提供了如下的操作
1s.empty() 如果栈为空返回true，否则返回false 2s.size() 返回栈中元素的个数 3s.pop() 删除栈顶元素但不返回其值 4s.top() 返回栈顶的元素，但不删除该元素 5s.push() 在栈顶压入新元素
队列提供了下面的操作
1q.empty() 如果队列为空返回true，否则返回false 2q.size() 返回队列中元素的个数 3q.pop() 删除队列首元素但不返回其值 4q.front() 返回队首元素的值，但不删除该元素 5q.push() 在队尾压入新元素 6q.back() 返回队列尾元素的值，但不删除该元素
c++stack(堆栈）
它是一个容器的改编，它实现了一个先进后出的数据结构（FILO）
使用该容器时需要包含#include头文件；
定义stack对象的示例代码如下：
stacks1;
stacks2;
stack的基本操作有：
1.入栈：如s.push(x);
2.出栈:如 s.pop().注意：出栈操作只是删除栈顶的元素，并不返回该元素。
3.访问栈顶：如s.top();
4.判断栈空：如s.empty().当栈空时返回true。
5.访问栈中的元素个数，如s.size（）;
下面举一个简单的例子：
1 #include<iostream> 2 #include<stack> 3 using namespace std; 4 int main(void) 5 { 6 stack<double>s;//定义一个栈 7 for(int i=0;i<10;i++) 8 s.push(i); 9 while(!s.empty()) 10 { 11 printf("%lf\n",s.top()); 12 s.pop(); 13 } 14 cout<<"栈内的元素的个数为："<<s.size()<<endl; 15 } 16栈是限定仅在表尾进行插入或删除操作的线性表， 17因此表尾端成为栈顶，相应的，表头端成为栈底，不含有任何元素的栈称为空栈。 18栈的修改遵循后进先出的原则，因此栈又称为后进先出的线性表，简称LIFO结构。 19栈一般采用数组作为其存储结构，这样做可以避免使用指针，简化程序 20，当然数组需要预先声明静态数据区的大小，但这不是问题，因为即便是频繁进出入栈操作， 21任何时刻栈元素的实际个数也不会很多，为栈预留一个足够大但又不占用太多空间并不是很困难， 22如果不能做到这一点，那么节省内存的方法就是使用链表存储栈。 23 24线性表实现栈的基本操作 25 #include<iostream> 26 #include<cstdio> 27 using namespace std; 28 typedef struct Stacknode//定义链式栈的结构体 29 { 30 int data;//数据域 31 Stacknode *next;//下一节点的指针域 32 }Stacknode,*Stack; 33 //初始化一个链式栈（返回一个链式栈的头节点） 34 Stack InitStack() 35 { 36 Stack stack=(Stack)malloc(sizeof(Stacknode)); 37 stack->next=NULL; 38 return stack; 39 } 40 //入栈 41 void Push(Stack stack,int newData) 42 { 43 //判断是否为空 44 if(stack==NULL) 45 { 46 printf("栈未初始化，请初始化以后再使用\n"); 47 return; 48 } 49 //找到最后一个节点 50 Stacknode *lastnode=stack; 51 while(lastnode->next) 52 { 53 lastnode=lastnode->next; 54 } 55 lastnode->next=(Stacknode*)malloc(sizeof(Stacknode*)); 56 lastnode->next->data=newData; 57 lastnode->next->next=NULL; 58 printf("入栈成功！\n"); 59 } 60 //出栈 61 int Pop(Stack stack) 62 { 63 //判断栈是否为空 64 if(!stack->next) 65 { 66 printf("栈为空，无法出栈\n"); 67 return -1;//-1只是一个自定义的错误代码 68 } 69 //找到最后一个节点的钱一个节点 70 //tempNode:最后一个节点的前一个节点 71 Stacknode *tempNode=stack; 72 while(tempNode->next->next) 73 { 74 tempNode=tempNode->next; 75 } 76 int data=tempNode->next->data; 77 free(tempNode->next); 78 tempNode->next=NULL; 79 return data; 80 } 81 82 int main() 83 { 84 Stack stack=InitStack(); 85 Push(stack,3);//3进栈 86 Push(stack,4);//4进栈 87 Push(stack,5);//5进栈 88 printf("%d\n",Pop(stack)); 89 printf("%d\n",Pop(stack)); 90 printf("%d\n",Pop(stack)); 91 printf("%d\n",Pop(stack));//第4次出栈，应该出错 92 return 0; 93 } 94queue模版类的定义在<queue>头文件中。 95queue与stack模版非常类似，queue模版也需要定义两个模版参数， 96一个是元素类型，一个是容器类型，元素类型是必要的， 97容器类型是可选的，默认为dqueue类型。 98 99定义queue对象的示例代码如下： 100queue<int>q1; 101queue<double>q2; 102queue的基本操作有： 1031.入队：如q.push(x):将x元素接到队列的末端； 1042.出队：如q.pop() 弹出队列的第一个元素，并不会返回元素的值； 1053,访问队首元素：如q.front() 1064,访问队尾元素，如q.back(); 1075,访问队中的元素个数，如q.size(); 108二.优先队列 109在<queue>头文件中，还定义了一个非常有用的模版类priority_queue 110(优先队列），优先队列与队列的差别在于优先队列不是按照入队的顺序出队， 111而是按照队列中元素的优先权顺序出队（默认为大者优先，也可以通过指定算子来指定自己的优先顺序）默认是一个大根堆。 112priority_queue模版类有三个模版参数，元素类型，容器类型，比较算子。 113其中后两个都可以省略，默认容器为vector，默认算子为less，即小的往前排，大的往后排（出队时序列尾的元素出队）。 114 115定义priority_queue对象的示例代码如下： 116priority_queue<int>q1; 117priority_queue<pair<int,int> >q2; 118priority_queue<int,vector<int>，greater<int> >q3; 119//定义小的先出队 120priority_queue的基本操作均与queue相同 121初学者在使用priority_queue时，最困难的可能就是如何定义比较算子了。 122如果是基本数据类型，或已定义了比较运算符的类，可以直接用STL的less算子和greater算子——默认为使用less算子， 123即小的往前排，大的先出队。如果要定义自己的比较算子，方法有多种， 124这里介绍其中的一种：重载比较运算符。优先队列试图将两个元素x和y代入比较运算符 125(对less算子，调用x<y，对greater算子，调用x>y)，若结果为真，则x排在y前面，y将先于x出队，反之，则将y排在x前面，x将先出队。 126 127看下面这个简单的示例： 128 #include<iostream> 129 #include<queue> 130 #include<stdlib.h> 131 using namespace std; 132 class T 133 { 134 public: 135 int x,y,z; 136 T(int a,int b,int c):x(a),y(b),z(c) 137 { 138 } 139 }; 140 bool operator<(const T&t1,const T&t2) 141 { 142 return t1.z<t2.z; int="" t="">q; 143 q.push(T(4,4,3)); 144 q.push(T(2,2,5)); 145 q.push(T(1,5,4)); 146 q.push(T(3,3,6)); 147 while(!q.empty()) 148 { 149 T t=q.top(); 150 q.pop(); 151 cout<<t.x<<endl; 152 } 153 }
栈的应用
①数制转换：
将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，很容易通过”除B取余法”来解决。
【例】将十进制数13转化为二进制数。
解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。
分析：由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此很容易用栈来解决。
具体算法如下：
1#include <STACK> //C++中使用栈要包含的头文件 2using namespace std;//这个也是要加的 3 4void conversion(int N,int B) 5{ 6 7 8 //假设N是非负的十进制整数，输出等值的B进制数 9 10 stack<int> S; //创建一个元素类型为int型的空栈 11 while(N) 12 { 13 S.push(N%B); //将转换后的数值，从底位到高位开始入栈 14 N=N/B; 15 } 16 while(!S.empty())//栈非空时退栈输出 17 { 18 printf("%d",S.top()); //打印栈顶元素 19 S.pop(); //将栈顶元素出栈 20 } 21} 22 23int main() 24{ 25 conversion(10,2); 26}
②表达式求值
表达式求值是程序设计语言编译中的一个最基本的问题。我们讨论一种简单直观的方法“算法优先级法”
算术四则运算的规则：
1、从左到右
2、先乘除后加减
3、先括号内，后括号外
【例】4 + 2*3 -10/5 每一步的计算顺序应该是：
4 + 2*3 -10/5 = 4 + 6 - 10/5 = 10 - 10/5 = 10 - 2 = 8
算法步骤：（我们假设表达式以字符‘#’结尾）
（1）首先，创建空运算符栈OPTR，将表达式起始符‘#’压入栈底，创建空操作数栈OPND
（2）依次读入表达式中的每个字符，若是操作数则进操作数栈，若是运算符则和运算符栈顶的运算符比较优先级后，做如下相应操作：
1.如果栈顶的运算符优先级较低，则把新的运算符压入OPTR；执行（2）
2.如果栈顶的运算符优先级较高，则将其 和 操作数栈的两个栈顶元素 退栈，计算3个元素组成的表达式的值，再压入操作数栈，然后继续判断；
3.如果栈顶的运算符优先级相等（除了#符外，只有‘(’和‘)’是相等的），则将‘（’出栈；执行（2）
（3）直到整个表达式求值完毕（即OPTR栈顶元素和当前读入的字符均为‘#’）
具体算法实现：
1#include <iostream> 2#include <stack>//C++中使用栈要包含的头文件 3 4using namespace std; 5 6//符号数组 7char symbol[7] = { 8 9 10 '+', '-', '*', '/', '(', ')', '#'}; 11 12//栈内元素的优先级 13int in[7] = { 14 15 16 3, 3, 5, 5, 1, 6, 0}; 17 18//栈外元素的优先级 19int out[7] = { 20 21 22 2, 2, 4, 4, 6, 1, 0}; 23 24/* 25 * 通过符号字符获取它的数组下标 26 */ 27int get(char c) 28{ 29 switch(c) 30 { 31 case '+': 32 return 0; 33 case '-': 34 return 1; 35 case '*': 36 return 2; 37 case '/': 38 return 3; 39 case '(': 40 return 4; 41 case ')': 42 return 5; 43 case '#': 44 return 6; 45 default: 46 return 6; 47 } 48} 49 50/* 51 * 比较栈内运算符c1和栈外运算符c2的优先级 52 */ 53char precede(char c1, char c2) 54{ 55 int i1 = get(c1); 56 int i2 = get(c2); 57 58 if(in[i1] > out[i2]) 59 { 60 return '>'; 61 } 62 else if(in[i1] < out[i2]) 63 { 64 return '<'; 65 } 66 else 67 { 68 return '='; 69 } 70} 71 72/* 73 * 计算基本表达式的值 74 */ 75int figure(int a, int theta, int b) 76{ 77 switch(theta) 78 { 79 case 0: 80 return a + b; 81 case 1: 82 return a - b; 83 case 2: 84 return a * b; 85 default: 86 return a / b; 87 } 88} 89 90/* 91 * 计算表达式的值 92 */ 93int EvaluateExpression(const char *exp) 94{ 95 stack<int> OPND; //操作数栈 96 stack<int> OPTR; //运算符栈 97 OPTR.push(get('#')); 98 99 int flag = 1; //表示正负号 1,表示正 0,表示负 100 int a, theta, b; 101 102 if(!('+' == *exp || '-' == *exp || '(' == *exp || isdigit(*exp))) 103 { 104 105 106 //如果不是以'+'、'-'、'('或者数字的其中一个开头，则表达式错误 107 cout << "表达式出错1" << endl; 108 return -1; 109 } 110 if('+' == *exp) 111 { 112 exp++;//指向下一个字符 113 } 114 else if('-' == *exp) 115 { 116 flag = 0; 117 exp++;//指向下一个字符 118 } 119 120 int index = OPTR.top(); //获取运算符栈顶元素在数组的下标号 121 while(*exp || symbol[index] != '#') //如果栈顶元素是'#'且当前元素为空结束计算 122 { 123 if(isdigit(*exp)) 124 { 125 126 127 //如果当前元素是数字，计算整个操作数的值，然后压入操作数栈 128 int sum = 0; 129 while(isdigit(*exp)) 130 { 131 132 133 //计算操作数的值 134 sum = sum * 10 + (*exp - '0'); 135 exp++; 136 } 137 if (!flag) //如果是负数 138 { 139 sum = -sum; 140 } 141 OPND.push(sum); 142 flag = 1; 143 } 144 else 145 { 146 147 148 //如果不是数字 149 switch(precede(symbol[OPTR.top()], *exp))//比较栈顶运算符和当前运算符的优先级 150 { 151 case '>' : 152 b = OPND.top(); 153 OPND.pop(); 154 a = OPND.top(); 155 OPND.pop(); 156 theta = OPTR.top(); 157 OPTR.pop(); 158 OPND.push(figure(a, theta, b)); 159 break; 160 case '<' : 161 OPTR.push(get(*exp)); 162 if(*exp) 163 { 164 exp++; 165 } 166 break; 167 case '=' : 168 OPTR.pop(); 169 if(*exp) 170 { 171 exp++; 172 } 173 break; 174 } 175 } 176 index = OPTR.top(); 177 } 178 return OPND.top(); 179} 180 181int main() 182{ 183 char c[50] = { 184 185 186 0}; 187 cout << "请输入一个表达式: "; 188 cin.getline(c,50); 189 cout << EvaluateExpression(c) << endl; 190 191 return 0; 192}
队列的应用
舞伴问题
1、问题叙述
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者，等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。
2、问题分析
先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。
在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。
3、具体算法及相关的类型定义
1#include <queue> 2//C++中使用队列要包含的头文件 3using namespace std; 4typedef struct 5{ 6 char name[20]; 7 char sex; //性别，'F'表示女性，'M'表示男性 8}Person; 9 10void DancePartner(Person dancer[],int num) 11{ 12 13 14 //结构数组dancer中存放跳舞的男女，num是跳舞的人数。 15 16 Person p; 17 queue<Person> Mdancers,Fdancers; 18 19 for(int i = 0; i < num; i++) 20 { 21 22 23 //依次将跳舞者依其性别入队 24 p=dancer[i]; 25 if(p.sex=='F') 26 Fdancers.push(p); //排入女队 27 else 28 Mdancers.push(p); //排入男队 29 } 30 printf("The dancing partners are: \n \n"); 31 while(!(Fdancers.empty()||Mdancers.empty())) 32 { 33 //依次输入男女舞伴名 34 p=Fdancers.front(); //获取女队第一人 35 Fdancers.pop(); //出队 36 printf("%s ",p.name); //打印出队女士名 37 38 p=Mdancers.front(); //获取男队第一人 39 Mdancers.pop(); //出队 40 printf("%s\n",p.name); //打印出队男士名 41 } 42 if(!Fdancers.empty()) 43 { 44 45 46 //输出女士剩余人数及队头女士的名字 47 printf("\n There are %d women waitin for the next round.\n",Fdancers.size()); 48 p=Fdancers.front(); //取队头 49 printf("%s will be the first to get a partner. \n",p.name); 50 } 51 else if(!Mdancers.empty()) 52 { 53 54 55 //输出男队剩余人数及队头者名字 56 printf("\n There are%d men waiting for the next round.\n",Mdancers.size()); 57 p=Mdancers.front(); 58 printf("%s will be the first to get a partner.\n",p.name); 59 } 60 else 61 { 62 printf("There is not person in the queue!"); 63 } 64}//DancerPartners 65 66int main() 67{ 68 Person p[] = { 69 70 71 { 72 73 74 "A",'F'},{ 75 76 77 "B",'F'},{ 78 79 80 "C",'M'},{ 81 82 83 "D",'M'}}; 84 DancePartner(p,4); 85}
本文同步分享在 博客“谙忆”（CSDN）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。