首页 > 代码库 > 数据结构与算法系列研究二——栈和队列
数据结构与算法系列研究二——栈和队列
栈和队列的相关问题分析
一、栈和队列定义
栈和队列是两种重要的数据结构。从结构特性角度看，栈和队列也是线性表，其特殊性在于它们的基本操作是线性表的子集，是操作受限的线性表，可称为限定性的数据结构；从数据类型角度看，其操作规则与线性表大不相同，是完全不同于线性表的抽象数据类型。
图1 栈的结构 图2 队列的结构
1.1、栈是限定在表的一端进行插入和删除操作的线性表。
插入：称为进栈（或压栈）。
删除：称为出栈（或退栈）。
栈顶（top）：允许进行插入和删除操作的一端。
栈底（bottom）：不允许插入和删除操作的一端。
基本操作：
Initstack(&s): 栈初始化
Destroystack(&s)： 撤消栈
Clearstack(&s)： 置栈空
Stackempty(s) ： 判栈空
Stacklength(S)： 求栈中元素个数
Gettop(S,&e)： 取栈顶元素
Push(&S,e)： 入栈
Pop(&S,&e)： 出栈
用线性链表表示栈的存储结构，称为链栈。链表头指针始终指向栈顶，同样用top表示。 无必要加头结点，栈空时：top=NULL入栈：每当一个元素进栈时，申请一个新结点，插入到表头。出栈：每当一个元素出栈时，从表头释放一个结点。
1.2、队列是限定在表的一端进行插入，在另一端进行删除的线性表。
队头（Front）：允许删除的一端。
队尾(Rear)：允许插入的一端。
基本操作：
InitQueue (&Q): 队列初始化
DestroyQueue (&Q)： 撤消队列
ClearQueue (&Q)： 置队列空
QueueEmpty(Q) ： 判队列空
Queuelength(Q)： 求队列元素个数
Gethead(Q,&e)： 取队列头元素
EnQueue (&Q,e)： 入队列
DeQueue (&Q,&e)： 出队列
二、用栈实现中缀式求解
编程实现中缀式求解，设算符只有+，-，*，/，（，）。操作数0~9（可当字符用）。
2.1、输入输出设计
1.输入 从控制台读进一个字符串，由于设计时运用了string类中的成员函数，故此此处省略‘#’，只读进一个字符串。读入的时候可能有不同的情况，此处简单起见，设置默认情况下读入的操作数为0~9，另外还有+，-，*，/运算符，但是要按照中缀式的顺序从左到右输入。
2.输出 此程序的功能是求一个中缀式的值，返回值应该是算式的结果，根据一系列的运算最终输出结果。其结果应该为一个实数值，适宜选用double类型存放。
2.2、关键数据结构与算法描述
数据结构：
通过对问题的分析，此处选用栈类型的存储结构最为适宜，因为其先进后出的特性可以模拟中缀式的计算过程。具体构造如下，此处构造为类的形式：
1 class Stack{ 2 public: 3 Stack(){top=-1;}//构造函数，进行初始化操作 4 ~Stack(){}//析构函数 5 bool IsEmpty(){ 6 if(top==-1) 7 return true; 8 else 9 return false; 10 }//判断栈是否为空 11 //返回栈顶元素 12 T gettop() 13 { 14 return a[top]; 15 } 16 //将元素压栈 17 void push(T num) 18 { 19 if(top>=MAXSIZE) 20 return; 21 a[++top]=num; 22 } 23 //将元素弹出栈 24 T pop() 25 { 26 if(top==-1) 27 return OVER; 28 return a[top--]; 29 } 30 private: 31 T a[MAXSIZE]; 32 int top; 33 };
此处运用C++语言对模板栈进行了定义，定义了指针top和数组a[MAXSIZE]；为以后的进栈和退栈操作提供了可能。
2.3、算法描述
要完成中缀式求值，最重要的是对读进的字符进行适当的处理，从而求出结果。
1.若读到字符就直接如数据栈；
2.若读进的是‘（’，直接入符号栈；
3.若读进的是‘）’，就要判断在‘（’前面有无符号，若有符号，就要进行循环每次将数据栈中的两个元素退栈，按照一定顺序和已经退栈的符号进行运算，运算结果再压入数据栈中，直至到‘（’或为空栈（正常情况下不可能），弹出‘（’；
4.若读进的是符号，就要判断优先级，若字符优先级高于符号栈的顶部优先级或者为空栈直接压入符号栈，否则进行循环，弹出顶部元素且再从数据栈弹出两个元素进行运算，结果压入数据栈。直至字符优先级大于栈顶元素或为空栈，此时再将字符压入符号栈中。一直循环上述步骤，直至字符串被读完，然后对符号栈进行查看，若不为空，则继续进行运算，直至最后为空，此时数据栈中必只有一个元素，此元素即为所求结果。输出即可。
具体算法如下：
1 double EvaluateExpression(string &s) 2 { 3 double answer; 4 for(int i=0;i<s.size();i++) 5 { 6 if(s[i]>=‘0‘&&s[i]<=‘9‘)//若为0~9字符，直接进数据栈 7 { 8 OPND.push(s[i]-‘0‘); 9 } 10 else 11 if(s[i]==‘(‘)//若为左括号直接进栈 12 { 13 OPTR.push(s[i]); 14 } 15 else if(s[i]==‘)‘)//若为右括号需判断 16 { 17 while((OPTR.gettop())!=‘(‘) 18 Count(); 19 OPTR.pop(); 20 } 21 else if(OPTR.IsEmpty()||Rank(s[i])>Rank(OPTR.gettop())）//优先级高直接入栈 22 { 23 OPTR.push(s[i]); 24 } 25 else 26 { 27 while(Rank(s[i])<=Rank(OPTR.gettop())&&!OPTR.IsEmpty())//否则，先计算已有元素 28 Count(); 29 OPTR.push(s[i]);//然后再进栈 30 } 31 } 32 while(!OPTR.IsEmpty())//若运算符栈为空，就要计算 33 { 34 Count(); 35 } 36 37 answer=OPND.pop();//得到最后结果，清空栈 38 return answer; 39 }
2.4、测试与理论
（注意，此处的除号是数学意义上的除法，不是c语言上的整除）
测试数据有： 理论结果为：
2+（4-1）/2*5； 9.5
（2+3-5/2）*5/1+8 20.5
（（3+5）*6+1）/7 7
((2+2)/2+3*5-8/2)/2-1 5.5
运行程序得到的结果为：
2.5、源代码（附录）
中缀式求解的代码：
1 #include"iostream" 2 #include"string" 3 using namespace std; 4 #define MAXSIZE 200 5 #define OVER -2 6 //创建模板栈，因有两个栈 7 template <typename T> 8 class Stack{ 9 public: 10 Stack(){top=-1;}//构造函数，进行初始化操作 11 ~Stack(){}//析构函数 12 bool IsEmpty(){ 13 if(top==-1) 14 return true; 15 else 16 return false; 17 }//判断栈是否为空 18 19 //返回栈顶元素 20 T gettop() 21 { 22 return a[top]; 23 } 24 //将元素压栈 25 void push(T num) 26 { 27 if(top>=MAXSIZE) 28 return; 29 a[++top]=num; 30 } 31 //将元素弹出栈 32 T pop() 33 { 34 if(top==-1) 35 return OVER; 36 return a[top--]; 37 } 38 private: 39 T a[MAXSIZE]; 40 int top; 41 }; 42 //定义两个栈 43 Stack<char> OPTR; 44 Stack<double> OPND; 45 //比较优先级，优先级越高，就越先计算 46 int Rank(char c) 47 { 48 if((c==‘(‘)||(c==‘)‘)) 49 return 1; 50 else 51 if((c==‘+‘)||(c==‘-‘)) 52 return 2; 53 else if((c==‘*‘)||(c==‘/‘)) 54 return 3; 55 else 56 return -1; 57 } 58 //对式子中的加减乘除进行计算 59 void Count() 60 { 61 double temp; 62 switch(OPTR.pop()) 63 { 64 case‘+‘: 65 temp=OPND.pop(); 66 temp+=OPND.pop(); 67 OPND.push(temp); 68 break; 69 case‘-‘: 70 temp=OPND.pop(); 71 temp=OPND.pop()-temp; 72 OPND.push(temp); 73 break; 74 case‘*‘: 75 temp=OPND.pop(); 76 temp=OPND.pop()*temp; 77 OPND.push(temp); 78 break; 79 case‘/‘: 80 temp=OPND.pop(); 81 temp=OPND.pop()/temp; 82 OPND.push(temp); 83 break; 84 default: 85 cout<<"操作符有误"<<endl; 86 break; 87 } 88 } 89 /********************核心算法，计算表达式的算法*************/ 90 double EvaluateExpression(string &s) 91 { 92 double answer; 93 for(int i=0;i<s.size();i++) 94 { 95 if(s[i]>=‘0‘&&s[i]<=‘9‘)//若为0~9字符，直接进数据栈 96 { 97 OPND.push(s[i]-‘0‘); 98 } 99 else 100 if(s[i]==‘(‘)//若为左括号直接进栈 101 { 102 OPTR.push(s[i]); 103 } 104 else if(s[i]==‘)‘)//若为右括号需判断 105 { 106 while((OPTR.gettop())!=‘(‘) 107 Count(); 108 OPTR.pop(); 109 } 110 else if(OPTR.IsEmpty()||Rank(s[i])>Rank(OPTR.gettop()))//优先级高直接入栈 111 { 112 OPTR.push(s[i]); 113 } 114 else 115 { 116 while(Rank(s[i])<=Rank(OPTR.gettop())&&!OPTR.IsEmpty())//否则，先计算已有元素 117 Count(); 118 OPTR.push(s[i]);//然后再进栈 119 } 120 } 121 while(!OPTR.IsEmpty())//若运算符栈为空，就要计算 122 { 123 Count(); 124 } 125 126 answer=OPND.pop();//得到最后结果，清空栈 127 return answer; 128 } 129 /**********主函数用于测试************************/ 130 int main() 131 { 132 string s; 133 double answer1; 134 char c; 135 while(1) 136 { 137 138 cout<<"请输入一个中缀式："<<endl; 139 cin>>s; 140 141 answer1=EvaluateExpression(s); 142 cout<<endl<<s<<"="<<answer1<<endl; 143 cout<<"是否继续？(Y||N)"<<endl; 144 cin>>c; 145 if(c==‘N‘||c==‘n‘) 146 break; 147 } 148 return 0; 149 }
将中缀式转换为后缀式
1 void ShowChange( string &s) 2 { 3 for(int i=0;i<s.size();i++) 4 { 5 if(s[i]>=‘0‘&&s[i]<=‘9‘) 6 { 7 cout<<s[i]; 8 } 9 else if(s[i]==‘(‘) 10 { 11 OPTR.push(s[i]); 12 } 13 else if(s[i]==‘)‘) 14 { 15 while(OPTR.gettop()!=‘(‘&&!OPTR.IsEmpty()) 16 { 17 cout<<OPTR.pop( ); 18 } 19 OPTR.pop( ); 20 } 21 else if(Rank(s[i])<=Rank(OPTR.gettop())) 22 { 23 while(OPTR.gettop()!=‘(‘&&!OPTR.IsEmpty()) 24 cout<<OPTR.pop(); 25 OPTR.push(s[i]); 26 } 27 else if(Rank(s[i])>Rank(OPTR.gettop())) 28 { 29 OPTR.push(s[i]); 30 } 31 } 32 while(!OPTR.IsEmpty()) 33 { 34 cout<<OPTR.pop(); 35 } 36 }
将中缀式转换为前缀式
1 void Z2QChange(string &s) 2 { 3 for(int i=s.size()-1;i>=0;i--) 4 { 5 if(s[i]>=‘0‘&&s[i]<=‘9‘) 6 { 7 OPND.push(s[i]); 8 } 9 else if(s[i]==‘)‘) 10 { 11 OPTR.push(s[i]); 12 } 13 else if(s[i]==‘(‘) 14 { 15 while(OPTR.gettop()!=‘)‘&&!OPTR.IsEmpty()) 16 { 17 OPND.push(OPTR.pop()); 18 } 19 OPTR.pop(); 20 } 21 else if(Rank(s[i])>=Rank(OPTR.gettop())||OPTR.IsEmpty()||OPTR.gettop()==‘)‘) 22 { 23 OPTR.push(s[i]); 24 } 25 else 26 { 27 while(Rank(s[i])<Rank(OPTR.gettop())&&!OPTR.IsEmpty()) 28 OPND.push(OPTR.pop()); 29 OPTR.push(s[i]); 30 31 } 32 } 33 while(!OPTR.IsEmpty()) 34 { 35 OPND.push(OPTR.pop()); 36 } 37 while(!OPND.IsEmpty()) 38 { 39 cout<<OPND.pop(); 40 } 41 }
三、入栈出栈问题
入栈次序1，2，3，4，则2在3前面出栈的情况有多少种？
解：根据树状图将所有弹出的次序找出来，从中找到符合要求的情况
易得结果共有7种，出栈情况分别为1234，1243，2134，2143，2314，2341，2431。
四、约瑟夫问题
链表实现：
1 #include<stdio.h> 2 #include<malloc.h> 3 typedef struct List 4 { 5 int data; 6 struct List *next; 7 }LinkList; 8 int main() 9 { 10 LinkList *L,*r,*s; 11 L = (LinkList *)malloc(sizeof(LinkList)); 12 r =L; 13 int n,i; 14 int k; 15 scanf("%d%d",&n,&k); 16 for(i = 1;i<=n;i++) 17 { 18 s = (LinkList *)malloc(sizeof(LinkList)); 19 s->data =http://www.mamicode.com/ i; 20 r->next = s; 21 r= s; 22 } 23 24 r->next =L->next; 25 LinkList *p; 26 p = L->next; 27 28 while(p->next != p) 29 { 30 for(i = 1;i<k-1;i++) 31 { 32 p = p->next; 33 } 34 p->next = p->next->next; 35 p = p->next; 36 } 37 printf("%d",p->data); 38 return 0; 39 }
数组队列实现：
#include<stdio.h>
int main()
{
int n, k;
scanf("%d%d", &n, &k);
int i;
int a[1001];
int dead = 0;
int num = 0;
for (i = 1; i<=n; i++)
{
a[i] = i;
}
for (i = 1;; i++)
{
if (i > n)
{
i = i%n;
}
if (a[i] > 0)
num++;
if (k == num && dead != n-1)
{
num = 0;
a[i] = 0;
dead++;
}
else if(k == num && dead == n-1)
{
printf("%d", a[i]);
break;
}
}
return 0;
}
公式法实现：
1 #include <iostream> 2 using namespace std; 3 const int m = 3; 4 int main() 5 { 6 int n, f = 0; 7 cin >> n; 8 for (int i = 1; i <= n; i++) f = (f + m) % i; 9 cout << f + 1 << endl; 10 }
数据结构与算法系列研究二——栈和队列