栈和队列

栈一 定义二 代码结构【1】静态分布【2】动态分布【3】初始化【4】入栈【5】出栈【6】建立完整栈，实现入栈出栈 链栈一 定义二 结构代码【1】建立结构【2】初始化【3】入栈【4】出栈【5】总体建立，实现出栈入栈 栈的应用一.数制转换【1】思想：【2】代码： 二.括号匹配【1】思想【2】代码 三.迷宫求解【1】思想【2】算法导图【3】算法代码 四. 四则运算【1】算法思想【2】代码

栈

一 定义

1.栈：限定仅在表尾进行插入或删除操作的线性表 2 栈底固定不变，后进先出

二 代码结构

【1】静态分布

typedef struct link//定义一个栈 { ElemType elem[maxleng];//栈中的数据 int top;//栈的头结点 }sqstack;

【2】动态分布

#define maxleng 100//限定栈的最长长度 typedef int ElemType;//用ElemType代替int类型 typedef struct link//定义一个栈 { ElemType elem[maxleng];//栈中的数据 int top;//栈的头结点 }sqstack;

【3】初始化

void initstack(sqstack &s)//初始化栈，让top指向头 { s.top=0; }

【4】入栈

int seg_push(sqstack &s,ElemType e)//入栈 { if(s.top>maxleng) { cout<<"满了"<< endl; return 1; } s.elem[s.top]=e; s.top++; return 1; }

【5】出栈

void seg_pop(sqstack &s)//出栈 { while(s.top!=0) { printf("%d",s.elem[s.top-1]); s.top--; } }

【6】建立完整栈，实现入栈出栈

#include <iostream> #include <bits/stdc++.h> using namespace std; #define maxleng 100//限定栈的最长长度 typedef int ElemType;//用ElemType代替int类型 typedef struct link//定义一个栈 { ElemType elem[maxleng];//栈中的数据 int top;//栈的头结点 }sqstack; void initstack(sqstack &s)//初始化栈，让top指向头 { s.top=0; } int seg_push(sqstack &s,ElemType e)//入栈 { if(s.top>maxleng) { cout<<"满了"<< endl; return 1; } s.elem[s.top]=e; s.top++; return 1; } void seg_pop(sqstack &s)//出栈 { while(s.top!=0) { printf("%d",s.elem[s.top-1]); s.top--; } } int main()//主函数 { int n,m,j,e; scanf("%d",&n); sqstack s; initstack(s); for(int i=0;i<n;i++) { scanf("%d",&e); seg_push(s,e); } /*if(s.top==0) printf("error！！"); else for(int i=0;i<n;i++) { printf("%d",s.elem[s.top-1]); s.top--; }*/ Seg_pop(s); return 0; }

链栈

一 定义

1.栈的链式储存结构为链栈 2.他的运算是受限的单链表，其插入和删除操作仅限制在表头位置上进行，由于智能在链表 头部进行操作，故链表没有必要像单链表那样附加头结点。栈的顶指针就是链表的头指针

二 结构代码

【1】建立结构

#define maxleng 100 typedef int ElemType; typedef struct link { ElemType elem; struct link *next; }* linkstack;

【2】初始化

void initstack (linkstack &s) { s=NULL; }

【3】入栈

void push_link(linkstack &s,ElemType e) { linkstack p; p=new link; p->elem=e; p->next=s; s=p; }

【4】出栈

void pop_link(linkstack &s) { linkstack p; while(s!=NULL) { p=s;printf("%d",p->elem);s=s->next; } }

【5】总体建立，实现出栈入栈

#include <iostream> #include <bits/stdc++.h> using namespace std; #define maxleng 100 typedef int ElemType; typedef struct link { ElemType elem; struct link *next; }* linkstack; void initstack (linkstack &s) { s=NULL; } void push_link(linkstack &s,ElemType e) { linkstack p; p=new link; p->elem=e; p->next=s; s=p; } void pop_link(linkstack &s) { linkstack p; while(s!=NULL) { p=s;printf("%d",p->elem);s=s->next; } } int main() { linkstack s; initstack(s); ElemType n,m,i; scanf("%d" ,&n); for(i=0;i<n;i++) { scanf("%d",&m); push_link(s,m); } pop_link(s); return 0; }

栈的应用

一.数制转换

【1】思想：

利用$m=\left(N/d\right)\times d+n\%d$

【2】代码：

#include <iostream> #include <bits/stdc++.h> using namespace std; #define maxleng 100 typedef int ElemType; #define k 2//表示二进制 typedef struct link { ElemType elem; struct link *next; }* linkstack; void initstack (linkstack &s) { s=NULL; } void push_link(linkstack &s,ElemType e) { linkstack p; p=new link; p->elem=e; p->next=s; s=p; } void pop_link(linkstack &s) { linkstack p; while(s!=NULL) { p=s;printf("%d",p->elem);s=s->next; } } int main() { linkstack s; initstack(s); ElemType n,m,i; scanf("%d",&n); while(n>0) { push_link(s,n%k); n=n/k; } pop_link(s); return 0; }

二.括号匹配

【1】思想

由于正确的是{【（）（）】}这种所以我们可以将左括号压入栈，然后遇到右括号时，将顶栈取值与右括号进行匹配（函数match）如果匹配成功那么将顶部栈取出重复上述，知道结束或者发现不匹配的括号，如果不匹配则直接return跳出

【2】代码

void BracketMatch(char *str) { Stack S; int i; char ch; InitStack(&S); for(i=0; str[i]!='\0'; i++) {switch(str[i]) {case '(': case '[': case '{': Push(&S,str[i]); break; case ')': case ']': case '}': if(IsEmpty(S)) { printf("\n右括号多余!"); return;} else GetTop (&S,&ch); if(Match(ch,str[i])) Pop(&S,&ch); else { printf(“\n对应的左右括号不同 类!"); return; } } } /*switch*/ } /*for*/ if(IsEmpty(S)) printf("\n括号匹配!"); else printf("\n左括号多余!"); }

三.迷宫求解

【1】思想

从入口出发，先顺某一 方向向前探索，若能走通， 则继续往前走；否则原路退 回，按一定的顺序换方向再 继续探索，直至到达出口或 者所有可能的通路都探索过 为止。

【2】算法导图

【3】算法代码

Status MazePath ( MazeType maze, PosType start, PosType end ) { // 若迷宫maze中存在从入口start到出口end的通道， // 则求得一条存放在栈中（从栈底到栈顶），并返回TRUE；否则返回FALSE InitStack(S)；curpos = start; // 设定“当前位置”为“入口位置” curstep=1; // 探索第一步 do { if ( Pass(curpos) ) { Footprint(curpos) e=( curstep, curpos, 1 ); Push(S,e); // 加入路径 if ( curpos==end ) return( TRUE ); // 到达终点（出口） curpos=NextPos( curpos, 1 ); // 下一位置是当前位置的东邻 curstep++; // 探索下一步 } // if else { //当前位置不能通过 if ( !StackEmpty( S ) ) { Pop( S, e ); while ( e.di==4 && !StackEmpty( S ) ) { MarkPrint( e.seat ); Pop( S, e ); // 留下不可通标记，并退回一步 } // while if ( e.di<4 ) { e.di++; Push( S, e ); //换下一个方向探索 curpos=NextPos( e.seat, e.di ); // 令新方向上的邻块为当前位置 } // if } // if } // else } while ( !StackEmpty( S ) ); return( FALSE ); } // MazePath

四. 四则运算

【1】算法思想

算法思想： 设：OPND----操作数栈,存放暂不运算的数和中间结果 OPTR----算符栈,存放暂不运算的算符

置OPND, OPTR为空栈；开始符#进OPTR ；从表达式读取“单词”w----操作数/算符当w!=‘#’ || OPTR的顶算符!=‘#’ 时, 重复： 3.1 若w为操作数，则w进OPND,读取下一“单词”w； 3.2 若w为算符，则： 3.2.1 若 prio(OPTR的顶算符(1)) < prio(w(2)), 则: w进OPTR ；读取下一“单词”w； 3.2.2 若 prio(OPTR的顶算符(1))=prio(w(2)) ，且w=“)”， 则:去括号， pop(OPTR)； 读取下一“单词”w； 3.2.3 若 prio(OPTR的顶算符(1)) > prio(w(2))，则： { pop(OPND,a)；pop(OPND,b)；pop(OPTR,op)； c=b op a； push(OPND,c)； /op为1/ }OPND的栈顶元素为表达式的值。

【2】代码

OperandType EvaluateExpression( ) { InitStack( OPTR ); InitStack( OPND ); while ( c!='#' || GetTop( OPTR )!='#' ） { if ( !In( c, OP )) { // 设0P为算符集合，可存储在字符串中并用strchr函数判断 Push( OPND, c ); c=GetSymbol( ); } // 不是算符，则进找 else switch ( Precede( GetTop( OPTR ), c )) { case '<': // 栈顶元素优先权低 Push( OPTR, c ); c=GetSymbol( ); break; case '=': // 脱括号并接收下一字符 Pop( OPTR, x ); c=GetSymbol( ); break; case ‘>’: // 出栈并将运算结果进栈 Pop( OPTR, theta ); Pop( OPND, b ); Pop( OPND, a ); Push( OPND, Operate( a, theta, b ) ); break; } // switch } // while return GetTop( OPND ); } // EvaluateExpression