栈

一种特殊的线性表，既只允许在一端进行插入或删除操作的线性表。

重要术语：栈顶，栈底，空栈
特点：后进先出(LIFO)

上溢：栈满还存

下溢：栈空还取

顺序栈

表示方法

1
2
3
4
5


#define maxsize 10;
typedef struct{
	Elemtype data[maxsize];
	int top;
}SqStack;

初始化

1
2
3


void InitStack(Sqstack &S){
	S.top=-1 //初始化栈顶指针
}

入栈

1
2
3
4
5
6
7
8
9


bool Push(SqStack &S,Elemtype x){
    if(S.top==maxsize-1){
        return false;
    } //栈满报错
    S.top =S.top+1;
    S.data[S.top]=x;
    //这两句可以写成 S.data[++S.top]=x;
    return true;
}

出栈

1
2
3
4
5
6
7
8
9


bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1){
        return false;
    }
	x=S.data[S.top];
    S.top = S.top-1;
    //这里同样可以写成 x=S.data[S.top--];
    return true;
}

顺序栈缺点：栈的大小不可变
改进：共享栈

共享栈

两个栈共享一片空间，正是由于这个特性，当一个栈本来快要存满，不采用共享栈的话，继续存入将导致上溢，但使用共享栈，可以使用对方的部分区域进行存储，降低上溢风险。

表示方法

1
2
3
4
5
6


#define maxsize 10;
typedef struct{
    ElemType data[maxsize];
    int top0;
    int top1;
}SqStack;

初始化

1
2
3
4


void InitStack(ShStack &S){
	S.top0=-1;
	S.top1=maxsize;
}

判满

1

S.top0+1==S.top1;

降低了发生上溢的可能

链栈

表示方法

1
2
3
4


typedef struct _LinkNode{
	ElemType data;
	struct _LinkNode *next;
}*LiStack, LinkNode;

推荐使用不带头节点实现，如果使用带头节点实现，记住头结点的next指向的就是栈顶元素！

初始化

1
2
3


void InitStack(LiStack S){
    S->next=NULL;
}

进栈

这里的链栈采用了虚拟头节点的表示方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


//C语言这里传入的是指向栈顶指针的指针！C++写法直接使用引用类型传参，这样就可以不使用*解析运算符
bool Push(LiStack *S,int x){
    LinkNode* p;
    p=(LiStack)malloc(sizeof(LinkNode));
    p->data=x;
    p->next=NULL;
    if(length<maxsize){ //当栈长度小于栈容量
        if((*S)==NULL){ //为栈空栈
            (*S)=p;     //直接将栈顶指针指向p
        }else{
            p->next=(*S)->next; //带头节点的链栈进栈操作在此处有所不同
            (*S)->next=p;		//头节点的next永远指向栈顶元素！
        }
        length++;
        return true;
    }else{
        return false;
    }
}

出栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


bool Pop(LiStack *S){
	if((*S==NULL){
		return false;
	}
	LinkNode *q=(*S)->next;
    Elemtype x=q->x;
    (*S)->next=q->next;
    free(q);
    return true;
}

获取栈顶元素

1
2
3


ElemType getop(LiStack S){
    return S->x
}

括号匹配

最后出现的左括号最先被匹配(LIFO)

每出现一个右括号就出栈一个左括号

算法实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


#define maxsize 10
typedef struct{
    char data[maxsize];
    int top;
}*SqStack;
bool bracketCheack(char str[],int length){
    SqStack S;
    S=InitStack(S);
    for(int i=0;i<length;i++){
        if(str[i]=='('||str[i]=='['||str[i]=='{'){
            Push(S,str[i]);
        }else if(str[i]==')'||str[i]==']'||str[i]=='}'){
            if(StackEmpty(S)){
                return false;
            }
            char topElem;
            topElem=Pop(S);
            if(str[i]==')'&&topElem!='(')
                return false;
            if(str[i]=='}'&&topElem!='{')
                return false;
            if(str[i]==']'&&topElem!='[')
                return false;
        }
    }
    return StackEmpty(S);
}

匹配失败的情况

左括号单身
右括号单身
左右括号不匹配

中缀表达式转后缀表达式

遇到操作数直接输出
如果遇到(，直接入栈
如果遇到)，将栈中的运算符弹出加入到后缀表达式，直到出现(，删除一个(即可
如果遇到除括号外的其他运算符，优先级大于栈顶运算符的入栈(isp<icp)，否则(isp>icp)从栈顶开始依次弹出比当前运算符优先级高或相等的运算符，直到遇到一个低优先级或(

运算符	(	*，/	+，-	)
isp	1	5	3	6
icp	6	4	2	1

isp：栈内优先级