数据结构栈和队列部分代码c

文章目录

栈
- 顺序栈
- 链式栈
队列
- 队列的顺序存储结构
- 队列的链式存储结构
栈和队列的应用

栈

顺序栈

init

#include
#include
#include

#define MaxSize 10

typedef int ElemType;
typedef struct{//定义栈中元素的最大个数
    ElemType data[MaxSize];//静态数组存放栈中元素
    int top;//栈顶指针，顺序栈中表示数组下标,初始化的时候为-1
}SqStack;

// init a stack
void InitStack(SqStack *s){
    (*s).top=-1;//初始化栈顶指针
}

// judge
bool StackEmpty(SqStack s){
    if(s.top==-1)
        return true;
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

push

// push
bool Push(SqStack *s,ElemType x){
    if((*s).top==MaxSize-1)//栈满，报错
        return false;
    (*s).top=(*s).top+1;
    (*s).data[(*s).top]=x;
    return true;
}
// 按照后进先出的顺序输出
void printfStack(SqStack s){
    if(s.top==-1)//空栈
        return;
    for(int i=s.top;i>=0;i--)
        printf("%d->",s.data[i]);
    printf("\n");
}
void test(){
    SqStack s;
    InitStack(&s);
    if(StackEmpty(s))
        printf("yes!");

    for(int i=0;i<4;i++){
        Push(&s,i+1);
    }
    printfStack(s);
    
}
void main(){
    test();
}
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
28
29
30
31

// pop
bool Pop(SqStack *s,ElemType *x){
    if((*s).top==-1)//栈空
        return false;
    *x=(*s).data[(*s).top];
    (*s).top--;
    return true;
}
1
2
3
4
5
6
7
8

这里对于栈的顺序存储结构的实现要注意的是push和pop的实现过程中，先对top指针进行加减操作还是先存/取数据

读栈顶元素

// 读取栈顶元素的操作,和pop的区别在于要不要删除top的元素
bool Gettop(SqStack s,ElemType *x){
    if(s.top==-1)//栈空
        return false;
    *x=s.data[s.top];
    return true;
}
1
2
3
4
5
6
7

以上代码中，top的初始条件是top==-1，但是也有另外的一种初始条件为top==0，这个表示top指向下一个可以存储数据的位置，如果初始条件是这种，那么对于push和pop的实现过程（先改变top还是先存取数据）和原本的实现刚好相反

// --------------------华丽的分界线----------------------
void InitStack2(SqStack *s){
    (*s).top=0;//表示下一个可以存储的位置
}
bool Push2(SqStack *s,ElemType x){
    if((*s).top==MaxSize)//栈满
        return false;

    (*s).data[(*s).top++]=x;
    return true;
}
bool Pop2(SqStack *s,ElemType *x){
    if((*s).top==0)//栈空
        return false;
    *x=(*s).data[--(*s).top];
    return true;
}
void printfStack2(SqStack s){
    if(s.top==0)
        return;
    for(int i=(s.top-1);i>=0;i--){
        printf("%d->",s.data[i]);
    }
    printf("\n");
}
void test(){
    SqStack s;
    InitStack2(&s);

    for(int i=0;i<4;i++){
        Push2(&s,i+1);
    }
    printfStack2(s);
    ElemType x=0;
    Pop2(&s,&x);
    printfStack2(s);
    
}
void main(){
    test();
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41

共享栈

栈满条件是top0+1==top1。这里代码很明显是有冗余的，实际上我们可以设定一个值为index，用来指定当前如果的栈顶指针，如果index=0说明是top0，如果index=1说明是top1，这样两个push函数可以简化为bool Push(ShStack *s,int index ElemType x)函数内部对index的合法性以及对栈满判断，最后使用一个switch语句就可以实现把两个push函数合并为一个push函数，在应用中，这个可以简化代码接口，所以这个是尤为重要的。类似对pop也可以有同等实现思路。

#include
#include
#include

#define MaxSize 10//定义栈中元素的最大个数

typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];//静态数组存放栈中元素
    int top0;//栈顶指针，顺序栈中表示数组下标,初始化的时候为-1
    int top1;
}ShStack;

void InitStack3(ShStack *s){
    (*s).top0=-1;
    (*s).top1=MaxSize;
}

bool Push_0(ShStack *s,ElemType x){
    if((*s).top0+1>=(*s).top1){//栈满,溢出
        return false;
    }
    (*s).data[++(*s).top0]=x;
    return true;
}
bool Push_1(ShStack *s,ElemType x){
    if((*s).top0+1>=(*s).top1){//栈满,溢出
        return false;
    }
    (*s).data[--(*s).top1]=x;
    return true;
}
bool Pop_0(ShStack *s,ElemType *x){
    if((*s).top0==-1)//栈空
        return false;
    *x=(*s).data[(*s).top0--];
    return true;
}
bool Pop_1(ShStack *s,ElemType *x){
    if((*s).top1==MaxSize)//栈空
        return false;
    *x=(*s).data[(*s).top1++];
    return true;
}

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

链式栈

使用不带头结点的单链表来实现链式栈，对应的push就是头插法建立单链表，pop操作就是逐个删除头结点，和单链表的实现没有区别。

#include
#include
#include
// 链栈，不带头结点的情况
typedef int ElemType;
typedef struct LinkNode{
    ElemType data;//数据域
    struct LinkNode *next;
}LinkNode,*LinkStack;


bool InitStack4(LinkStack *s){
    *s=NULL;//栈空,不带头结点
    return true;
}
bool Push4(LinkStack *s,ElemType x){
    LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL)
        return false;
    p->data=x;
    // 这一步很容易错
    p->next=(*s);
    (*s)=p;
    return true;
}
bool Pop4(LinkStack *s,ElemType *x){
    if((*s)==NULL)//空表
        return false;
    LinkNode *p=*s;
    *s=(*s)->next;
    *x=p->data;
    free(p);

    return true;
}
void printfStack4(LinkStack s){
    // s=NULL;
    LinkNode *p=s;
    while(p!=NULL){
        printf("%d->",p->data);
        p=p->next;
    }
    printf("\n");
}
void test4(){
    LinkStack s;
    InitStack4(&s);
    // printfStack4(s);
    Push4(&s,1);
    Push4(&s,2);
    printfStack4(s);
    ElemType x=0;
    Pop4(&s,&x);
    printfStack4(s);

}
void main(){
    test4();
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

队列

队列的顺序存储结构

#include
#include
#include

#define MaxSize 10//定义栈中元素的最大个数

typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int front,rear;//front指向队头元素，rear指向队尾的下一个位置（也就是下一个应该插入的位置
}SqQueue;

void InitSqQueue(SqQueue *Q){
    (*Q).rear=(*Q).front=0;
}
bool SqQueueEmpty(SqQueue Q){
    if(Q.rear==Q.front)
        return true;
    else
        return false;
}
// 入队
// 对于队满的判断，我们初始化的时候认为，队空是说队头指针等于队尾指针这就说明我们必须要牺牲掉一个存储单元来区分空和满的状态
// 链表的指针的走向和循环队列的相同
bool EnSqQueue(SqQueue *Q,ElemType x){
    if((*Q).front==((*Q).rear+1)%MaxSize)//队满：尾指针的后一个位置和头指针相等
        return false;
    (*Q).data[(*Q).rear]=x;
    (*Q).rear=((*Q).rear+1)%MaxSize;
    return true;
}

// 出队
bool DeSqQueue(SqQueue *Q,ElemType *x){
    if((*Q).rear==(*Q).front)
        return false;
    *x=(*Q).data[(*Q).front];
    (*Q).front=((*Q).front+1)%MaxSize;
    return true;
}
// 获取但不删除队头
bool GetHead(SqQueue Q,ElemType *x){
    if(Q.rear==Q.front){
        return false;
    }
    *x=Q.data[Q.front];
    return true;
}
void printfSqQueue(SqQueue Q){
    if(Q.rear==Q.front)//队空
        return;
    while(Q.rear!=Q.front){
        printf("%d<-",Q.data[Q.front]);
        Q.front=(Q.front+1)%MaxSize;
    }
    printf("\n");
}
void test5(){
    SqQueue Q;
    InitSqQueue(&Q);
    printfSqQueue(Q);
    for(int i=1;i<=4;i++){
        printf("入队顺序：%d\n",i);
        EnSqQueue(&Q,i);
    }
    printfSqQueue(Q);
    ElemType x=0;
    while(!SqQueueEmpty(Q)){
        DeSqQueue(&Q,&x);
        printf("出队顺序：%d\n",x);
    }
}
void main(){
    test5();
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

前面这种队列以牺牲一个存储空间为代价来区分队满和队空状态，如果不想要牺牲存储空间，可以增加一个size字段来动态维护当前队列的长度。这样初始化的时候rear=front=0;size=0，对于插入(删除)操作size++(size--);对于队满和(队空)操作size==MaxSize(size==0);

#define MaxSize 10//定义栈中元素的最大个数

typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int front,rear;//front指向队头元素，rear指向队尾的下一个位置（也就是下一个应该插入的位置
    int size;
}SqQueue;
1
2
3
4
5
6
7
8

还有一种方案就是设置一个状态值tag=0，对于删除操作令tag=0；对于插入操作令tag=1，这个时候队满的条件是front==rear&&tag==1，队空的条件是front==rear&&tag==0，总之无论是什么方案，至少都需要花费一定的空间的代价。实现如下：

#ifndef T1_H
#define T1_H

#include
#include
#include

#define MaxSize 10//定义栈中元素的最大个数

typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int front,rear;//front指向队头元素，rear指向队尾的下一个位置（也就是下一个应该插入的位置
    int tag;//0表示出队操作，1表示入队操作，只有在指针相同且是出队操作才表示空，在指针相同的入队操作表示满
}SqQueue;

void InitSqQueue(SqQueue *Q);//初始化
bool EnSqQueue(SqQueue *Q,ElemType x);//入队操作
bool DeSqQueue(SqQueue *Q,ElemType *x);//出队操作

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

#include "t1.h"

void InitSqQueue(SqQueue *Q){
    (*Q).rear=(*Q).front=0;
    (*Q).tag=0;
}
bool EnSqQueue(SqQueue *Q,ElemType x){
    if((*Q).rear==(*Q).front&&(*Q).tag==1)//队列满
        return false;

    (*Q).data[(*Q).rear]=x;
    (*Q).rear=((*Q).rear+1)%MaxSize;
    (*Q).tag=1;
    return true;
}
bool DeSqQueue(SqQueue *Q,ElemType *x){
    if((*Q).rear==(*Q).front&&(*Q).tag==0)//队空
        return false;

    (*Q).tag=0;
    *x=(*Q).data[(*Q).front];
    (*Q).front=((*Q).front+1)%MaxSize;
    return true;
}
void printfSqQueue(SqQueue Q){
    if(Q.rear==Q.front&&Q.tag==0)
        return;

    do{
        printf("%d<-",Q.data[Q.front]);
        Q.tag=0;
        Q.front=(Q.front+1)%MaxSize;
    }while(Q.rear!=Q.front&&Q.tag==0);
    printf("\n");
}
void test1(){
    SqQueue Q;
    InitSqQueue(&Q);
    
    ElemType x=0;
    scanf("%d",&x);
    while(x!=999){
        EnSqQueue(&Q,x);
        scanf("%d",&x);
    }
    // printf("%d-%d\n",Q.front,Q.rear);
    printfSqQueue(Q);
    DeSqQueue(&Q,&x);
    printfSqQueue(Q);
}
void main(){
    test1();
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

以上所有的代码都是基于rear指向队尾元素的后一个位置也就是下一个需要插入的位置，但是也有一种方案是rear直接指向队尾元素，这种的入队操作、初始化操作和判空操作会有所不同，具体来说：

入队操作：

Q.rear=(Q.rear+1)%MaxSize;
Q.data[Q.rear]=x
1
2

初始化操作：

Q.front=0;
Q.rear=MaxSize-1
1
2

判空条件：

(Q.rear+1)%MaxSize==front
1

队满操作：

和上面一个，要么牺牲一个存储单位，要么增加辅助变量。

队列的链式存储结构

#include
#include
#include

typedef int ElemType;
typedef struct LinkNode{//链式队列结点
    ElemType data;
    struct LinkNode *next;
}LQNode;
typedef struct{//链式队列
    LQNode *front,*rear;
}LQueue;
// 带头结点的初始化
void InitLQueue_withHead(LQueue *Q){
    (*Q).front=(LQNode *)malloc(sizeof(LQNode));
    (*Q).rear=(*Q).front;
    (*Q).front->next=NULL;
}
void InitLQueue_withoutHead(LQueue *Q){
    (*Q).front=NULL;
    (*Q).rear=NULL;
}
bool LQueueEmpty(LQueue Q){
    if(Q.front==NULL)
        return true;
    return false;
}

// 入队
void EnLQueue_withHead(LQueue *Q,ElemType x){
    LQNode *s=(LQNode *)malloc(sizeof(LQNode));
    s->data=x;
    s->next=NULL;
    (*Q).rear->next=s;
    (*Q).rear=s;//修改表尾指针
}
void EnLQueue_withoutHead(LQueue *Q,ElemType x){
    LQNode *s=(LQNode *)malloc(sizeof(LQNode));
    s->data=x;
    s->next=NULL;
    if((*Q).front==NULL){
        (*Q).front=s;
        (*Q).rear=s;
    }else{
        (*Q).rear->next=s;
        (*Q).rear=s;//修改表尾指针
    }
}
// 出队
bool DeLQueue_withHead(LQueue *Q,ElemType *x){
    if((*Q).front==(*Q).rear)//空队
        return false;

    LQNode *p=(*Q).front->next;
    *x=p->data;
    (*Q).front->next=p->next;
    if((*Q).rear==p)//最后一个结点出队
        (*Q).rear=(*Q).front;
    free(p);
    return true;
}
bool DeLQueue_withoutHead(LQueue *Q,ElemType *x){
    if((*Q).front==NULL)//空队列
        return false;
    LQNode *p=(*Q).front;
    *x=p->data;
    (*Q).front=p->next;//对于不带头结点和带头结点，这一部分是有区别的
    if(p==(*Q).rear){//说明这是最后一个结点
        (*Q).rear=NULL;
    }
    free(p);
    return true;
}
// printf：两个打印操作的区别不大，可以合并为一个打印操作
void printfLQueue_withHead(LQueue Q){
    if(Q.front==Q.rear)
        return;

    LQNode *p=Q.front->next;
    while(p!=NULL){
        printf("%d<-",p->data);
        p=p->next;
    }
    printf("\n");
}
void printfLQueue_withoutHead(LQueue Q){
    if(Q.front==NULL)
        return;
    LQNode *p=Q.front;
    while(p!=NULL){
        printf("%d<-",p->data);
        p=p->next;
    }
    printf("\n");
}
void test6(){
    LQueue Q;
    InitLQueue_withHead(&Q);
    ElemType x=0;
    scanf("%d",&x);
    while(x!=999){
        EnLQueue_withHead(&Q,x);
        scanf("%d",&x);
    }
    printfLQueue_withHead(Q);
    DeLQueue_withHead(&Q,&x);
    printfLQueue_withHead(Q);

    LQueue L;
    InitLQueue_withoutHead(&L);
    scanf("%d",&x);
    while(x!=999){
        EnLQueue_withoutHead(&L,x);
        scanf("%d",&x);
    }
    printfLQueue_withoutHead(L);
    DeLQueue_withoutHead(&L,&x);
    printfLQueue_withoutHead(L);
}
void main(){
    test6();
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

队列长度：

对于循环队列，队列长度=(Q.rear+MaxSize-Q.front)%MaxSize

对于链表存储的队列，可以在定义数据结构的时候，增加一个辅助变量size来维护队列长度

typedef int ElemType;
typedef struct LinkNode{//链式队列结点
    ElemType data;
    struct LinkNode *next;
}LQNode;
typedef struct{//链式队列
    LQNode *front,*rear;
    int size;//队列长度
}LQueue;
1
2
3
4
5
6
7
8
9

栈和队列的应用

栈在括号匹配中的应用

思路：遇到左括号入栈

遇到有括号，出栈匹配，同一类型括号且左右括号匹配成功，其他失败

全部匹配成功且栈为空，匹配成功

#ifndef LISTACK_H
#define LISTACK_H
#include
#include
#include
// 链栈，不带头结点的情况
typedef char ElemType;
typedef struct LinkNode{
    ElemType data;//数据域
    struct LinkNode *next;//这里的定义是有问题的，在栈中应该设计一个top指针，但是考虑到手比脑快代码都写完了就不改了，介意的话把next改名为top就可以了
}LinkNode,*LinkStack;

bool InitStack4(LinkStack *s);//初始化不带头结点的栈
bool Push4(LinkStack *s,ElemType x);//入栈
bool Pop4(LinkStack *s,ElemType *x);//出栈
void printfStack4(LinkStack s);//打印
bool EmptyStack4(LinkStack s);//空栈
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include "listack.h"


bool InitStack4(LinkStack *s){
    *s=NULL;//栈空,不带头结点
    return true;
}
bool EmptyStack4(LinkStack s){
    if(s==NULL){
        return true;
    }
    return false;
}
bool Push4(LinkStack *s,ElemType x){
    LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL)
        return false;
    p->data=x;
    // 这一步很容易错
    p->next=(*s);
    (*s)=p;
    return true;
}
bool Pop4(LinkStack *s,ElemType *x){
    if((*s)==NULL)//空表
        return false;
    LinkNode *p=*s;
    *s=(*s)->next;
    *x=p->data;
    free(p);

    return true;
}
void printfStack4(LinkStack s){
    // s=NULL;
    LinkNode *p=s;
    while(p!=NULL){
        printf("%c->",p->data);
        p=p->next;
    }
    printf("\n");
}
// void test4(){
//     LinkStack s;
//     InitStack4(&s);
//     // printfStack4(s);
//     Push4(&s,1);
//     Push4(&s,2);
//     printfStack4(s);
//     ElemType x=0;
//     Pop4(&s,&x);
//     printfStack4(s);

// }
// void main(){
//     test4();
// }
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include "listack.h"
// 假设字符串中只有三种括号 {} [] ()
bool ifMatch(char c[],int len){
    if(len==0)
        return true;
    if(len%2!=0)//括号一定是成对的
        return false;

    LinkStack s;
    InitStack4(&s);
    for(int i=0;i<len;i++){
        if(c[i]=='{'||c[i]=='('||c[i]=='['){//左括号入栈
            Push4(&s,c[i]);
        }else{
            if(EmptyStack4(s))//如果是右括号需要被匹配但是栈空，直接返回false
                return false;
            char temp=' ';
            Pop4(&s,&temp);
            if(c[i]=='}'&&temp!='{')
                return false;
            else if(c[i]==']'&&temp!='[')
                return false;
            else if(c[i]==')'&&temp!='(')
                return false;   
        }
    }
    if(!EmptyStack4(s))//所有都正常匹配，但是左括号还有多余的
        return false;

    return true;

}
void test7(){
    char c[11]="((((()))){}";
    if(ifMatch(c,11))
        printf("YES");
    else
        printf("NO");
}
void main(){
    test7();
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

栈在括号匹配中的应用其实不仅仅是局限在括号匹配，对于常遇到的检验对称性的数据，都可以使用类似的思路去实现，比如检验回文序列等，在不同的应用中会有不同的表达，但是总体都是一个思路。

栈在表达式求值中的应用

实现从中缀表达式转换到后缀表达式

虽然这里使用的是c语言编写的代码，但是我个人更加建议使用更高级的语言去实现这个代码，因为比如说c不能直接给出数组长度，我们需要用sizeof(ElemType[])/sizeof(ElemType)才可以实现求值长度，但是使用更高级语言就可以直接len(array)多方便。

#ifndef LISTACK_H
#define LISTACK_H
#include
#include
#include
// 链栈，不带头结点的情况
typedef char ElemType;
typedef struct LinkNode{
    ElemType data;//数据域
    struct LinkNode *next;//这里的定义是有问题的，在栈中应该设计一个top指针，但是考虑到手比脑快代码都写完了就不改了，介意的话把next改名为top就可以了
}LinkNode,*LinkStack;

bool InitStack4(LinkStack *s);//初始化不带头结点的栈
bool Push4(LinkStack *s,ElemType x);//入栈
bool Pop4(LinkStack *s,ElemType *x);//出栈
void printfStack4(LinkStack s);//打印
bool EmptyStack4(LinkStack s);//空栈
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include "listack.h"


bool InitStack4(LinkStack *s){
    *s=NULL;//栈空,不带头结点
    return true;
}
bool EmptyStack4(LinkStack s){
    if(s==NULL){
        return true;
    }
    return false;
}
bool Push4(LinkStack *s,ElemType x){
    LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL)
        return false;
    p->data=x;
    // 这一步很容易错
    p->next=(*s);
    (*s)=p;
    return true;
}
bool Pop4(LinkStack *s,ElemType *x){
    if((*s)==NULL)//空表
        return false;
    LinkNode *p=*s;
    *s=(*s)->next;
    *x=p->data;
    free(p);

    return true;
}
void printfStack4(LinkStack s){
    // s=NULL;
    LinkNode *p=s;
    while(p!=NULL){
        printf("%c->",p->data);
        p=p->next;
    }
    printf("\n");
}
// void test4(){
//     LinkStack s;
//     InitStack4(&s);
//     // printfStack4(s);
//     Push4(&s,1);
//     Push4(&s,2);
//     printfStack4(s);
//     ElemType x=0;
//     Pop4(&s,&x);
//     printfStack4(s);

// }
// void main(){
//     test4();
// }
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include "listack.h"

/*
初始化一个栈用来保存暂时还不能确定运算顺序的运算符
从左到右处理各个元素，直到末尾
 如果遇到操作数，直接加入后缀表达式
 如果遇到界限符，"("，直接入栈，遇到")"则依次弹出站内运算符并加入后缀表达式，直到弹出"("为止
 遇到运算符，依次弹出栈中优先级高于或者等于当前运算符的所有运算符，并依次加入后缀表达式中，若碰到"("或者栈空就停止，再把当前的运算符入栈。
处理完所有的字符后将栈中剩余运算符依次弹出，加入到或后缀表达式中

*这里要注意的是，连续弹出运算符都是依次弹出的
优先级高于或者等于的都要弹出，除非是带括号（
*/
bool ifNum(char c);
// 采用16进制，也就是A表示10，以此类推，只表示16个数
void postfitExpression(char c[],char result[],int length){
    LinkStack s;//初始化一个空栈来存储还不能确定顺序的运算符
    InitStack4(&s);
    int index=0;
    char temp=' ';//弹出的数据存储

    LinkStack l;
    InitStack4(&l);//用来临时存储低优先级的运算符
    for(int i=0;i<length;i++){
        if(ifNum(c[i])){//如果是操作数，直接加入后缀表达式
            result[index]=c[i];
            // printf("------------");
            index++;
            // index++;
        }else if(c[i]=='('){
            Push4(&s,c[i]);
        }else if(c[i]==')'){
            // 依次弹出栈中的运算符，直到遇到第一个'('
            temp=' ';//避免脏数据
            while(temp!='('&&!EmptyStack4(s)){
                // if(EmptyStack4(s))
                //     break;
                Pop4(&s,&temp);
                if(temp!='(')
                    result[index++]=temp;
            }
        }else{//除了数字和左右括号，其他都是运算符，默认不使用大括号和花括号
            // 遇到运算符，依次弹出栈中优先级高于或者等于当前运算符的所有运算符，并依次加入后缀表达式中，若碰到"("或者栈空就停止，再把当前的运算符入栈。
            temp=' ';//避免脏数据
            while(temp!='('&&!EmptyStack4(s)){
                Pop4(&s,&temp);
                if(c[i]=='+'||c[i]=='-'){//所有的运算符都是相同或者高的优先级
                    if(temp!='(')
                        result[index++]=temp;
                }else{
                    if(temp=='+'||temp=='-')
                        Push4(&l,temp);
                    else if(temp=='*'||temp=='/')
                        result[index++]=temp;
                }
            }
            if(temp=='(')//如果是（，就要放回去，可以直接用getTop()，但是这里没有实现这个函数就麻烦点
                Push4(&s,temp);
            while(!EmptyStack4(l)){//把低优先级的依次放回原来的栈中
                Pop4(&l,&temp);
                Push4(&s,temp);
            }
            Push4(&s,c[i]);
        }
    }
    // 处理完所有的字符后将栈中剩余运算符依次弹出，加入到或后缀表达式中
    while(!EmptyStack4(s)){
        Pop4(&s,&temp);
        result[index++]=temp;
    }
    // for(int i=0;i
    //     printf("%c",result[i]);
    // }
    // return result;
}

bool ifNum(char c){
    if(c>='0'&&c<='9')//0-9
        return true;
    else if(c>='A'&&c<='E')//A-E
        return true;
    else
        return false;
}

void test8(){
    char c[]="((2/(7-(1+1)))*3)-(2+(1+1))";
    int length=27;
    char result[27]=".";
    postfitExpression(c,result,length);
    for(int i=0;i<length;i++){
        printf("%c",result[i]);
    }
}
void main(){
    test8();
}


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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

少见的输出结果展示：

PS D:\workspaces\CWorkspace\project408\chapter3> cd "d:\workspaces\CWorkspace\project408\chapter3\" ; if ($?) { gcc *.c -o postfit_expression } ; if ($?) { .\postfit_expression }
2711+-/3*211++-
PS D:\workspaces\CWorkspace\project408\chapter3>
1
2
3

利用后缀表达式计算

/*
遇到操作数，入栈
遇到运算符，两个元素出栈，运算结果入栈
*/
void calculation(char result[],int length){
    
}
1
2
3
4
5
6
7

中缀表达式的计算

中缀表达式计算=中缀变后缀+利用后缀计算

/*
用栈实现中缀表达式的计算
初始化两个栈，操作数栈和运算符栈
	若扫描到操作数，压入操作数栈
	若扫描到运算符或者界限符，按照“中缀转到后缀”的相同逻辑压入运算符栈（期间也会弹出运算符，每弹出一个运算符就需要弹出两个操作数栈的元素来进行相应的运算，运算结果再压回操作数栈中，注意先弹出的元素在运算符左边，后弹出的在运算符右边）
*/
1
2
3
4
5
6

栈在递归调用中的应用

队列在层次遍历中的应用

树的层次遍历、图的广度优先遍历都是相同的思想

/*
根节点入队
队列的第一个节点出队，并且访问其直接后继结点，如果有直接后继结点就依次入队
循环以上步骤直到队空
*/
1
2
3
4
5

相关阅读:
js基础笔记学习254事件的捕获2
rhce练习题
 D. Bandit in a City(DFS + 叶子节点数目)
C语言经典基础题目100题
 央企施工企业数字化转型的灵魂是什么
 音频频谱动画的原理与实现（一）
外包干了2个月，技术退步明显...
android开发获取View坐标位置的几种方式
 XJSON 是如何实现四则运算的？
mindspore如何处理数据集加载多进程(multiprocessing)错误
原文地址：https://blog.csdn.net/CodePlayMe/article/details/126402807

数据结构 栈和队列部分代码c