栈和队列

栈的顺序存储实现

#define STACK_INIT_SIZE 80
#DEFINE STACK_INCREMENT 10

typedef struct
{
    elemtype *base;
    elemtype *top;
    int stacksize;//栈长度（有多少元素），不是sizeof
}SqStack;

Sqstack s;

Status StackInit (Sqstack *s) //传入结构体指针变量
{
    if(!(s->base = (elemtype*)malloc(sizeof(elemtype)*STACK_INIT_SIZE)))
        //对于线性表，分配内存空间是给L直接分配，因为L自身的含义就是头指针的地址，并且线性表是多个结构体指针变量连起来的，而对于顺序栈来说，他只有一个正常的结构体，结构体里面才包含头尾指针，所有的操作都是在这个结构体内部，使用这一个结构体的成员变量完成的
    	return ERROR;
    s->top = s->base;
    	return OK;   
}

顺序栈的使用

//入栈
Status Push(Sqstack *s, elemtype e)
{
    //第一步，先处理一下栈容量够不够的问题
    if(s->top-s->base >= s->stacksize )//c语言指针的运算，减出来结果等于sizeof(elemtype)
    {
        s->base = (elemtype*)realloc(s->base,(stacksize+STACK_INCREMENT)*sizeof(elemtype));
        if(!(s->base))
            return ERROR;
        s->top = s->base + s->stacksize;
        s->stacksize += STACK_INCREMENT;
    }
    //入栈
    *(s->top) = e;  //正确的解引用方式，不要把它写成   s-> *top  ,这不是正确的解引用方式
    s -> top++;
    return OK;
}

//出栈
Status Pop(Sqstack *s, elemtype*e)
{
    //第一步，先判断栈是否为空
    if(s->base == s->top)
        return ERROR;
    //出栈
    *e = *(--(s -> top));  //同样的，对top进行操作，现在前面加上s->,而不是写成  s-> --top
   	*(s->top) = 0; //这一步可以省略
    return OK;
}

链栈的实现

typedef struct SNode
{
    elemtype data;
    struct SNode *next;
}SNode,*LinkStack;

//init
LinkStack s;

Status LinkStackInit (LinkStack *s) //如果使用&s，则函数内可以直接使用s，
    							 //不用加*号，使用指针的话则必须加上*号
{
    if(!(*s = (SNode*)malloc(sizeof(SNode))))
        return ERROR;
    （*s） -> next = NULL;
    return OK;
}

链栈的基本使用

//入栈
Status Push(LinkStack *s, elemtype e)
{
    SNode* p;
    if(!(p=(SNode*)malloc(sizeof(SNode))))
        return ERROR;
    p->next = *s;
    p->data = e;
    *s = p;
    return OK;
}

//出栈
Status Pop(LinkStack *s, elemtype *e)
{
    if(*s == NULL)
        return EMPTY;
    *e = (*s)->data;
    LinkStack p = *s;
    *s = (*s)->next;
    free(p);
    return OK;       
}

栈的应用举例

数制转换

数值转换的思路都是把一个数不断除以进制n，从晚到早 的余数排列就是 从高到低 的新数位

int main()
{
    int a; //进制
    int num; //数字
    scanf("%d",&a);
    scanf("%d",&num);
        
    LinkStack s = NULL; //初始化栈顶指针要让他为NULL
    while(num > 0)  //如果这个地方用 num%a!=0 作为判断条件，有可能回导致最后一次判断失误（如果正好除尽）
    {
        int b = num%a;
        num /= a;
        Push(&s,b);
	}
    while(s != NULL)
    {
        int temp;
        pop(&s,&temp);
        printf("%d",temp);
	}
}

括号匹配的检验

设计算法检验表达式中所使用括号的合法性

思路：括号的合法，指的就是 左右成对出现，也就是

一直入栈，如果上一个左括号和下一个右括号匹配，则二者出栈，看最后能不能出完

typedef struct 
{
    struct SNode *next;
    char c;
}SNode,*LinkStack;
pop(LinkStack *s,char*e); //出栈
{
    if(*s == NULL)
    return EMPTY;
    *e = (*s)->data;
    LinkStack p = *s;
    *s = (*s)->next;
    free(p);
    return OK;  
}
push(LinkStack *s); //入栈
{
    SNode* p;
    if(!(p=(SNode*)malloc(sizeof(SNode))))
        return ERROR;
    p->next = *s;
    p->data = e;
    *s = p;
    return OK;
}
getelem(LinkStack s); //读取当前栈顶元素，但是不取出
int main()
{
    char str[50];
    scanf("%s",str);
    int i =0;
    LinkStack s = NULL;//初始化为空，切记
    while(str[i]!='\0')
    {
        if (str[i] == '(' || str[i] =='[' || str[i] == '{')
        {
            push(&s);
        }
        else if(str[i] == ')' || str[i] ==']' || str[i] == '}')
        {
            if(str[i] == ')')
            {
                char c;
                getelem(s,&c);
                if(c == '(')
                    pop(&s);
            }
            else if(str[i] == ']')
            {
                char c;
                getelem(s,&c);
                if(c == '[')
                    pop(&s);
            }            
            else if(str[i] == '}')
            {
                char c;
                getelem(s,&c);
                if(c == '{')
                    pop(&s);
            }            
		}
        i++;
	}
    if(isEmpty(s))
        printf("CORRECT");
    else
        printf("SOMETHING WENT WRONG");
    return 0;
}

迷宫问题

思路：

1. 先确定一个顺序（如，对于一个元素而言，在其周围遍历的顺序是从右上角开始，顺时针）
2. 建立一个栈，这个栈用来存放当前坐标信息，对于一个元素而言，找到一个0，就把这个0入栈，然后把这个0 当作当前的中心，同时把上一个0标记成-1，代表出口不能从他这找
3. 如果当前的0周围没有找到出口，那么退栈，重新以上一个0为中心继续找周围下一个0进行尝试，如果一圈都不行，把这个也退栈，以此类推
4. 为了让这个算法能够适用于迷宫阵的角角落落，把周围一圈补上1

#define STACK_INIT_SIZE 80
#define STACK_INCREASMENT 10

#define ROW 7
#define COL 8

typedef struct 
{
    int Stack[STACK_INIT_SIZE][2];
    int *base;
    int *top;
}SNode;

SNode s;

//定义迷宫数组
int maze[ROW][COL] = {
    {0, 1, 1, 0, 0, 0, 1, 0},  
    {0, 0, 0, 1, 1, 0, 0, 0},
    {1, 1, 0, 0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0, 0, 0, 0},
    {1, 1, 0, 0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 1, 0},
    {0, 1, 1, 1, 0, 0, 0, 0}
};
int maze_after[ROW+2][COL+2];

void maze_increase(int(*maze)[COL], int(*maze_after)[COL+2])//用指针传递二维数组的方法
{
    for (int i = 0; i <= (ROW + 1); i++)
    {
        for (int j = 0; j <= (COL + 1); j++)
        {
            if (i == 0 || i == (ROW + 1))
            {
                maze_after[i][j] = 1;
            }
            else if (j == 0 || j == (COL + 1))
            {
                maze_after[i][j] = 1;
            }
            else
            {
                maze_after[i][j] = maze[i - 1][j - 1];
            }
        }
    }

    //test
    for (int i = 0; i <= ROW+1; ++i)
    {
        for (int j = 0; j <= COL+1; ++j)
        {
            printf("%d", maze_after[i][j]);
        }
        printf("\n");
    }
}

//现在，maze_after已经是修正以后的迷宫了

//下面是迷宫具体算法
void check(SNode s, int(*maze_after)[COL + 2])
{
    int x = 1; //标记行位置
    int y = 1; //标记列位置
    int i = 0; //标记栈元素个数
    s.Stack[0][0] = 1; //栈初始化第一个元素（起点行）
    s.Stack[0][1] = 1;//（起点列）
    maze_after[1][1] = -1; //标记起点位置为走过的
    while (s.Stack[0][0] != 0) //只要别没有路，导致把起点给退栈了，就一直循环
    {
        if (s.Stack[i - 1][0] == ROW && s.Stack[i - 1][1] == COL) //栈走到终点了
        {
            printf("找到一条\n");
            for (int n = 0; n <= i; n++)
            {
                printf("%d,%d\n", s.Stack[n][0], s.Stack[n][1]); //输出栈
            }
            break;
        }
        if (maze_after[x][y] == 0 || maze_after[x][y] == -1) //当前的元素自身是通路
        {
            printf("当前以x=%d,y=%d为中心\n",x, y);
            maze_after[x][y] = -1;
            if (maze_after[x - 1][y + 1] == 0)  //如果右上方的是通路，开始入栈
            {
                i++; 
                s.Stack[i][0] = x - 1;
                s.Stack[i][1] = y + 1;
                x--;
                y++;
                maze[x - 1][y + 1] = -1;
                printf("    x=%d,y=%d进栈了\n", x, y);

            }
            else if (maze_after[x][y + 1] == 0)
            {
                i++;
                s.Stack[i][0] = x;
                s.Stack[i][1] = y + 1;
                y++;
                maze[x][y + 1] = -1;
                printf("    x=%d,y=%d进栈了\n", x, y);
            }
            else if (maze_after[x + 1][y + 1] == 0)
            {
                i++;
                s.Stack[i][0] = x + 1;
                s.Stack[i][1] = y + 1;
                x++;
                y++;
                maze[x + 1][y + 1] = -1;
                printf("    x=%d,y=%d进栈了\n", x, y);
            }
            else if (maze_after[x + 1][y] == 0)
            {
                i++;
                s.Stack[i][0] = x + 1;
                s.Stack[i][1] = y;
                x++;
                maze[x + 1][y] = -1;
                printf("    x=%d,y=%d进栈了\n", x, y);
            }
            else if (maze_after[x + 1][y - 1] == 0)
            {
                i++;
                s.Stack[i][0] = x + 1;
                s.Stack[i][1] = y - 1;
                x++;
                y--;
                maze[x + 1][y - 1] = -1;
                printf("    x=%d,y=%d进栈了\n", x, y);
            }
            else if (maze_after[x][y - 1] == 0)
            {
                i++;
                s.Stack[i][0] = x;
                s.Stack[i][1] = y - 1;
                y--;
                maze[x][y - 1] = -1;
                printf("    x=%d,y=%d进栈了\n", x, y);
            }
            else if (maze_after[x - 1][y - 1] == 0)
            {
                i++;
                s.Stack[i][0] = x - 1;
                s.Stack[i][1] = y - 1;
                x--;
                y--;
                maze[x - 1][y - 1] = -1;
                printf("    x=%d,y=%d进栈了\n", x, y);
            }
            else
            {
                printf("x=%d,y=%d退栈了\n", x, y);   //转了一圈没通路，把当前的给退栈
                s.Stack[i][0] = 0;
                s.Stack[i][1] = 0;
                maze_after[x][y] = -1;
                i--;
                x = s.Stack[i][0];
                y = s.Stack[i][1];
                printf("退栈完成\n");
            }
        }
    }

}

int main()
{
    maze_increase(maze, maze_after);
    check(s, maze_after);
    return 0;
}

表达式求值

设置两个栈，一个存储操作数，一个存储操作符

运算符栈底初始化为“#”，便于定位操作始末（实际上是把表达式始末设置为“#”）

遇到数字，入栈

遇到符号：

1. new>top,入栈
2. new=top,去除一对括号，或者结束（只有 “（” ， “）” 或者两个“#” 优先级一样）
3. new<top,取出数字栈两个元素，和栈顶元素，进行运算得到一个新的数字存回数字栈

#include<stdio.h>
#include<string.h>

//定义栈
typedef struct 
{
    char *top_opera;
    char opera[20];
    int opera_length;
}OPERA;
OPERA opera;



    typedef struct
    {
        int*top_num;
        int num[20];
        int num_length;
    }NUM;
NUM num;


int main()
{
    init_opera(&opera);//初始化别忘了加&符号
    init_num(&num);
    char temp_c = '0';
    char c ='0';
    int a =0;
    int b =0;
    char exps [50];
    printf("请输入一个表达式");
    scanf("%s",exps);
    int length = strlen(exps);
    //开始操作
    opera.opera[0]='#';
    for(int i =0;i<length;i++)
    {
        //if((((int)exps[i])>=48)&&(((int)exps[i])<=57))
        if((exps[i]>='0')&&(exps[i]<='9')) //更易读
        {
            //应使用push_num代替
            *(num.top_num)=exps[i]-'0'; //存 //切记，先点号，再星号
            num.top_num++;				//移
            num.num_length++;			//加
            if(num.num_length>=20)
            {
                //重新分配内存
			}
        }
        else if((exps[i]=='+')||(exps[i]=='-')||(exps[i]=='*')||(exps[i]=='/')||(exps[i]=='(')||(exps[i]==')')||(exps[i]=='#'))
        {
            if(exps[i]=='#')
                return(GetTop(num));
            //使用自定义函数compare来比较符号优先级
			switch(compare(GetTop(opera),exps[i]))
            {
                    case'<':push_opera(opera,exps[i]);
                        	break;
                    case'=':pop_opera(opera,temp_c);
                    		pop_opera(opera,temp_c);
                    		break;
                    case'>':pop_num(num,a);
                    		pop_num(num,b);
                    		pop_oprea(opera,c);
                    		push(num,operate(a,c,b));
            }
        }
        else
        {
            printf("error input");
		}

    }
    
    return 0;

}

队列

特点：先进先出，只允许在队头删除，只允许在队尾插入

• 分析：出队顺序就是入队顺序，即bdcfea，也是出栈顺序 ，入栈顺序是abcdef，后入先出
• a入栈，b入栈，b出栈，c入栈，d入栈，d出栈，c出栈，e，f入栈，fe出栈，a出栈，最小栈容量至少为3

链队列实现

思考：链栈和链队列定义上的区别是什么？是什么造成了区别？

• 在定义链栈的时候，把栈结点结构体定义为指针类型，同时上一个结点中包含指向新结点的指针，形成链，栈的名字 s，永远是指向栈顶元素的指针

• 在定义链队列的时候，也是把队列节点定义为指针类型，上一个节点包含指向下一个节点的指针，队列的名字Q无意义，而是要读取Q.front 和Q.rear 来判断队列头尾指针

• 造成区别的原因：

  栈只需要始终找栈顶元素即可，因此栈名就是指向栈顶元素的指针，而队列要有头有尾，头出尾进，因此新定义一个结构体来表示

//栈队列结点类型定义
typedef struct Qnode
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr
    
//栈队列实现
typedef struct
{
    QueuePtr front; //队头指针
    QueuePtr rear; //队尾指针
}LinkQueue;

//带头结点的队列始化
LinkQueue Q;
Q.front = NULL;
Q.rear = NULL;
Status InitQueue (LinkQueue *Q) //传入要初始化的队列
{
    QueuePtr q1; //一个temp临时q1
    if(!(q1 = (QNode*)malloc(sizeof(QNode)))) //分配内存
    	return error;
    q1->next = NULL;
    Q->front = q1;
    Q->rear = q1;
}


//带头结点的队列插入算法
Status QueueInsert (LinkQueue *Q,elemtype e)
{
    QueuePtr q1;
    if(!(q1=(*QNode)malloc(sizeof(QNode))))
        exit(OVERFLOW);
    q1->data = e;
    
    Q.rear->next =q1;
    Q.rear=q1;
    return OK;
}

//出队
Status DelQueue(LinkQueue *Q,elemtype *e)
{
    QueuePtr q1;
    q1=Q.front->next;
    *e = *(q1.data); //哈哈
    Q.front = q1->next;
    free(q1);
    return OK;
}

循环队列

初始化循环队列

//初始化循环队列

#define MAXSIZE 10

typedef struct 
{
    elemtype queue [];//QElemType *base;
    int front;
    int rear;
    // elemtype *front;   //误区：头尾指针，究其作用还是“指向”
    //elemtype *rear;	  //不一定非要是指针类型，对于由数组实现的数据结构	
    //整型数字的指向功能反而更好
    int count;
}Queue;

Queue Q;

Status InitQueueCurl(Queue *q)
{
    if(!((q->queue)=(elemtype*)malloc(MAXSIZE*sizeof(elemtype))))
        exit (OVERFLOW);
    (*q).front = 0;
    (*q).rear = 0;
    (*q).count = 0;

}

循环队列 入队的两种思路

//入循环队列


//方法一：count法
Status QueueInsert(Queue *q,elemtype e)
{
    if ((*q).count!=MAXSIZE)
    {
        (*q).queue[(*q).rear]=e;
		if((*q).rear = MAXSIZE)  
        {
            (*q).rear = 0;
            (*q).count++;
        }
        else
        {
            (*q).rear++;
            (*q).count++;
		}
        return OK;
	}
    else
        return ERROR;
}


//方法二：整除判断法
Status QueneInsert(Queue *q,elemtype e)
{
    if((((*q).rear)+1)%MAXSIZE == (*q).front)
        //尾指针加1，取余最大长度，是否等于头指针
        return ERROR;
    (*q).queue[(*q).rear]=e;
    (*q).rear = ((*q).rear+1)%MAXSIZE;//尾指针加一，取余最大长度（小于最大长度									
    								//就相当于没取余，大于最大长度了就相当于再来一轮）
    return OK;
}

循环队列长度求法

//求循环队列长度的算法
int ququelenth(Queue q)
{
    int answer = (q.rear-q.front+MAXSIZE)%MAXSIZE; //  rear - fount 表示两者距离之差，加上maxsize一定为正数，再取余
    
    //这里也提供了 环形结构 求两个元素之间的距离，加绝对值时候的一种算法思路，就是先减出一个符号不定的距离，然后加上最大长度，再取余最大长度
    
    return answer;
}

循环队列应用之回文数