Stack and Queue

0 : 本博客所有代码源文件以及重命名

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

1：俩栈共享空间：适用于俩个栈的空间需求有相反的关系：一个栈增长时另一个栈再缩短

1.1：图示

1.2：具体创建代码

typedef struct
    {
        SElemType data[MAXSIZE];
        int top1;/*栈1栈顶指针*/
        int top2;
    }SqDoubleStack;

2：入栈操作

实现代码

/*入栈*/
Status Push(SqDoubleStack *s,SElemType e,int stackNumber)
{
    if( (s->top1)+1==s->top2)/*俩个栈都满了，不能再加东西了*/
        return ERROR;
    if(stackNumber==1)
        s->data[++s->top1]=e;
    if(stackNumber==2)
        s->data[--s->top2]=e;
    return OK;
}

不懂的地方:用SqDoubleStack *s,Push(s,10,1)会报错，用SqDoubleStack s，Push(&s,10,1)就好了

int e;
    SqDoubleStack *s;

    Push(s,10,1);
    Pop(s,&e,1);/*int e,然后用*e会报错*/
    printf("%d",e);

3：出栈操作Status Pop(SqDoubleStack *s,SElemType *e,int stackNumber)

具体实现代码：

/*若栈不空，则删除栈顶元素，用e返回其值，并返回OK*/
Status Pop(SqDoubleStack *s,SElemType *e,int stackNumber)
{
    if(stackNumber==1)
    {
        if(s->top1==-1)/*规定栈为空时栈顶为-1*/
            return ERROR;
        *e=s->data[s->top1--];/*栈顶元素出栈，且将栈顶元素赋值给e*/
    }
    else if(stackNumber==2)
    {
        if(s->top2==MAXSIZE)
            return ERROR;
        *e=s->data[s->top2];
    }

    return OK;
}

不懂的地方：用e得到出栈的栈顶元素

int e;
Pop(s,&e,1);/*int e,然后用*e会报错*/
printf("%d",e);

细节：int e,别用Pop(s,*e,1);用Pop(s,&e,1);

int e;
Pop(s,&e,1);/*int e,然后用*e会报错*/
printf("%d",e);

若是*e，报错如下：

unary：一元的。

2：栈的链式存储结构及实现

2.1：栈的链式存储结构图示

2.2：具体创建代码

typedef struct StackNode
{
    SElemType data;/*该node具体含有的值*/
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;/*栈顶指针*/
    int len;/*栈的长度*/
}LinkStack;

2.3:插入操作

1:图示：

2:具体代码：

/*插入元素e,使其作为新的栈顶元素*/
Status Push(LinkStack *s,SElemType e)
{
    LinkStackPtr ne=(LinkStackPtr)malloc(sizeof(StackNode))/*ne是一个指针,创建一个新的node*/
    ne->data=e;/*给新的node赋值*/
    ne->next=s->top;/*s是要被插入的链表,把原来栈顶node作为新的要插入的node的 后继 */
    s->top=ne;/*被插入的链表已经改变，栈顶node变成插入的node*/
    s->len++;/*被插入的链表的长度加一*/
    
    return OK;
}

2.4出栈操作

1:图示

2:具体代码

status Pop(LinkStack *s,SElemType *e)
{
    LinkStackPtr p;/*P是临时的，只是为了记录被踢出的栈顶元素，和e的作用一样*/
    if(StackEmpty(*s))
        return ERROR;
    *e=s->top->data;/*将栈的头结点的值赋给e*/
    p=s->top;/*将栈顶节点赋值给p*/
    s->top=s->top->next;/*使得栈顶结点下移一位，指向后一节点*/
    free(p);
    s->len--;
    
    return OK;    
}

2.5：链式栈的出栈入栈解析：简单，O(1)

2.6：与顺序栈对比：如果栈元素的变化在可控范围内，建议使用顺序栈。链式栈每个元素都有指针域，空间消耗大

3：栈的作用;代替数组，而且高级语言有封装，更方便

4:栈的应用

4.1：递归

4.2：四则运算表达式求值：后缀表示法

5：队列

5.0:图示

5.1：循环队列：顺序存储结构

5.2：队列的链式存储结构及实现：线性表的单链表，但是只能头进尾出，也叫链队列

5.2.1:链队列构造代码

typedef struct QNode/*节点结构：跟链表差不多*/
{
    QElemType data;
    struct QNode *next;/*后继指针*/
}QNode,*QueuePtr;

typedef struct
{
    QueuePtr fr,rear;/*队头，队尾指针，都是指针*/
}LinkQueue;

5.2.2链队列push操作具体代码

/*插入元素，就是在链表尾部插入node,因为队列只能在尾部加入新元素,使新的node成为新的尾部node*/
Status pushQueue(LinkQueue *Q,QElemType ne)
{
    QueuePtr ne=(QueuePtr) malloc (sizeof(QNode));
    if(!ne)                 /*存储分配失败*/
        exit(overflow_error);
    ne->data=e;   //给新加入的node赋值
    ne->next=NULL;//队尾元素的后继指针为NULL
    
    Q->rear->next=ne;/*把新node作为原来队列队尾的后继*/
    Q->rear=ne;/*使新node作为队列的队尾*/
    
    return OK;
    
}

5.2.3:链队列pop操作代码

Status popQueue(LinkQueue *Q,QElemType *e)
{
    if(Q->fr==Q->rear)/*队首队尾指针相同*/
        return ERROR;
    QueuePtr p=Q->fr->next;/*临时指针p,节省书写*/
    
    *e=p->data;/*取值，取队列队首的值*/
    
    Q->fr->next=p->next;/*删除队首操作，同时更新*/
    
    if(Q->rear==p)/*在删除前，如果当该队列只有一个node,即队尾与队首相等*/
        Q->rear=Q->fr;/*将尾指针指向头指针*/
    free(p);
    
    return OK;
}

5.3.4:图示

链队列图示

push()图示

pop()图示

空链队列图示

5.3:链式与顺式循环队列的选择问题:在可以确定队列长度最大值的情况下,用循环队列.