一、栈
（一）、定义
顺序栈(main)
-
定义
#define MaxSize 50 typedef struct{ ElementType data[MaxSize]; int top; }SqStack;
共享栈
- 定义:定义一个数组,选择某个位置作为栈底,两边向内生长
栈的链式存储结构
-
定义:
typedef struct Linknode{ ElementType data; struct Linknode *next; }*LiStack;
（二）、操作
初始化
-
功能:初始化栈
-
code
void initStack(SqStack &s){ s.top=-1; }
判栈空
-
功能:判断栈是否为空
-
code
bool stackEmpty(SqStack s){ if(s.top!=-1){ return false; }else{ return true; } }
进栈
-
功能:进栈
-
code
bool push(SqStack &s,ElementType e){ if(s.top==MaxSize){ //判断栈满 return false; } s.data[++s.top]=e; return true; }
出栈
-
功能:出栈
-
code
bool pop(SqStack &s,ElementType &e){ if(s.top==-1){ //判断栈空 return false; } e=s.data[s.top--]; return true; }
读栈顶元素
-
功能:获取栈顶元素
-
code
bool getTop(SqStack s,ElementType &e){ if(s.top==-1){ return false; } e=s.data[s.top]; return true; }
二、队列
（一）、定义
顺序队列
-
定义
typedef struct{ ElementType data[MaxSize]; int front,rear; }SqQueue; -
特点:
- 队空:
Q.front=Q.rear - 队满:无法使用Q.rear==MaxSize
- 队空:
循环队列(main)
-
定义
typedef struct{ ElementType data[MaxSize]; int front,rear; }SqQueue; -
特点:
- 队空:
Q.front==NULL&&Q.rear!=NULL - 队满:
Q.front==NULL&&Q.rear!=NULL
- 队空:
-
由于队空队满条件相同的三种处理:
-
牺牲一个队列单元来区分队空还是队满
- 队满:
(Q.rear+1)%MaxSize=Q.front - 队空:
Q.front==Q.rear
- 队满:
-
类型中增加表示元素个数的数据成员
-
类型中设置
tag数据成员思想:通过多设置一个
tag来区分不同状态下的队满或队空条件-
tag=0,若因删除导致Q.front==Q.rear,则为队空 -
tag=1,若因插入导致Q.front==Q.rear,则为队满
-
-
链式存储
-
定义
typedef struct{ ElementType data; struct LinkNode *next; }LinkNode; typedef struct{ LinkNOde *front,*rear; }LinkQueue; -
特点:
- 队空:
Q.front==NULL&&Q.rear==NULL - 队满:无
- 队空:
-
注:
- 建议带头结点
-
LinkQueue中实际只有front和rear两个节点
（二）、操作
循环队列
初始化
-
功能:初始化
-
code
void initQueue(SqQueue &q){ q.front=0; q.rear=0; }
判队空
-
功能:判队空
-
code
bool isEmpty(SqQueue Q){ if(q.front==q.rear) return true; else return false; } -
注意:循环队列下判空条件依然为
q.front==q.rear
入队
-
功能:入队
-
code
bool EnQueue(SqQueue &q,ElementType x){ if((q.rear+1)%MaxSize==q.front) return false; //验满 q.rear=(q.rear+1)%MaxSize; q.data[q.rear]=x; return true; }
出队
-
功能:出队
-
code
bool deQueue(SqQueue &q,ElementType &x){ if(q.rear==q.front) return false; //验空 x=q.data[q.front]; q.front=(q.front+1)%MaxSize; }
链式存储
初始化
-
定义:初始化
-
code
void initQueue(LinkQueue &q){ q->front=q->rear=(LinkNode *)malloc(sizeof(LinkNOde)); q.front.next=NULL; //设置首节点的next为NULL } -
注:链式存储下的q中实际只有
front和rear两个结点
判队空
-
定义:判队空
-
code
void isEmpty(LinkQueue Q){ if(q.front==q.rear) return true; else return false; }
入队
-
定义:入队
-
code
void enQueue(LinkQueue &q,ElementType x){ //不用判队空 LinkNode *temp=(LinkNode *)malloc(sizeof(LinkNode)); temp->data=x; temp->next=NULL; q.rear->next=temp; q.rear=q.rear->next; }
出队
-
定义:出队
-
code
bool deQueue(LinkQueue &q,ElementType &x){ //判空 if(q.rear==q.front) return false; LinkNode *temp=q.front->next; x=temp->data; q.front=q.front->next; if(q.rear==temp){ return true; //保持一个节点,最后一个不释放 } free(temp); return true; }
三、应用
（一）、中缀表达式转后缀
-
规则
- 如果遇到普通的数输出
- 遇到
(,直接入栈 - 遇到
),将运算符弹出栈直到遇到) - 遇到一般运算符
s,根据运算符的优先级:匹配栈顶的运算符t,出栈直到遇到优先级比s低的运算符
-
code
#include <stdio.h> #include <stdlib.h> #include <iostream> #include <algorithm> #include <cstring> #include <stack> #include <map> using namespace std; stack<char> s; map<char,int> mp; void init(){ //初始化map,定义运算符号优先级 mp[‘*‘]=2; mp[‘/‘]=2; mp[‘+‘]=1; mp[‘-‘]=1; } string toSuffixExpression(string str){ int len=str.length(); string ans=""; for(int i=0;i<len;i++){ if(str[i]<=‘9‘&&str[i]>=‘0‘){ ans+=str[i]; //对于数值直接输出,因为对于中缀转后缀数字的相对位置不变 //cout << "num:" << str[i] << endl; } else if(str[i]==‘(‘){ s.push(str[i]); } else if(str[i]==‘)‘){ while(s.top()!=‘(‘){ ans += s.top(); s.pop(); } s.pop(); } else{ while(s.size()!=0&&mp[str[i]]<=mp[s.top()]){ //cout << "str:" << str[i] << endl; //cout << "pop:" << s.top() << endl; ans += s.top(); s.pop(); } s.push(str[i]); } } while(s.size()!=0){ //如果栈内还有运算符,追加到式子后面 ans+=s.top(); s.pop(); } return ans; } int main(){ init(); string str; cin >> str; cout << toSuffixExpression(str); } -
注:无法将
(和）使用运算符的优先级进行操作-
(直接入栈,所以必然是优先级最低的运算符 -
)必须匹配到(,如果将)设置为最低优先级的运算符,则每次遇到)必然会将栈中所有运算符都弹出
-