关于栈和队列

因为有程设知识的铺垫，虽然铺垫得不多手搓得也不多，但是不至于太陌生艰涩。
所以整理栈和队列应该不会很难。

栈

栈的特性

栈本质是限定在表尾进行插入和删除的线性表。

LIFO（先进后出）
栈顶和栈底
压栈和出栈都在栈顶
空栈和栈满
栈满后再压栈会发生栈溢出

栈的存储结构

栈可以用数组和链表实现。用数组实现的弹性大于链表。

栈类型	实现方法
顺序栈	数组
链栈	链表

栈的算法

顺序栈

静态栈。

栈结构体

#define MAX_SIZE 100
typedef int ELemtype;

typedef struct
{
    Elemtype data[MAX_SIZE];
    int top;
}SqStack;
```  

💡一定要注意栈满栈空时top指针指向哪里。  
这里规定空栈时top指针指向位置a1（标记为0），栈满时top指针指向位置a5（标记为MAX_SIZE）。
- 初始化栈  
```.c
void initialize(SqStack* S)
{
    S->top=0;
}

判断栈空

bool isEmpty(SqStack* S)
{
    if(S->top==0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

判断栈满

bool isFull(SqStack* S)
{
    if(S->top==MAX_SIZE)
    {
        return true;
    }
    else
    {
        return false;
    }
}

入栈

Status Push(SqStack* S,Elemtype e)
{
    if(S->top==MAX_SIZE)
    {
        return ERROR;
    }
    
    S[top]=e;
    S->top++;
    //上述两行代码可简化成：S[top++]=e;
    return OK;
    
}

出栈

Status Pop(SqStack* S,int* ptr)
//注意要传指针进来，才能在函数销毁后也能保存栈顶元素。
{
    if(isEmpty(S))
    {
        return ERROR;
    }
    *ptr=S->data[S->top-1];//用指针保存被弹出的栈顶元素
    S->top--;
    return OK;
}

💡读取栈顶元素可用该出栈函数。但要注意代价是栈顶元素会被弹出。

链栈

动态栈。是一种链式存储结构。

栈结构体

typedef struct
{
    int data;
    Node* next;
}Node;

定义链栈
1
2
3
4
struct LinkStack
{
Node* top;
}
💡这里规定top在栈空时为NULL，在栈满时为栈顶元素的指针。

初始化链栈

void initialize(LinkStack* LS)
{
    LS->top=NULL;
}

创建新节点

Node* CreateNode(int e)
{
    Node* p=(Node*)malloc(sizeof(Node));
    p->data=e;
    p->next=NULL;
    return p;
}

判断栈空

bool isEmpty(LinkStack* LS)
{
    if(LS->top==NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

入栈

void Push(LinkStack* LS,int d)
{
    Node* newnode=CreateNode(d);
    if(isEmpty(LS))
    {
        LS->top=newnode;
    }
    newnode->next=LS->top;
    LS->top=newnode;
}

出栈
Status Pop(LinkStack* LS,Node* topnode)
{
if(isEmpty(LS))
{
return ERROR;
}
*topnode=LS->top;
LS->top=LS->top->next;
return OK;
}
💡这种出栈方式能保留栈顶元素,该片内存没被清除。
💡这里的next的方向是指从栈顶到栈底的顺序方向。
出栈（不保留栈顶元素）
Status Pop(LinkStack* LS)
{
if(isEmpty(LS))
{
return ERROR;
}
Node* tmp=LS->top;
LS->top=LS->top->next;
free(tmp);
return OK;
}

共享栈

暂定（~~不太想写。。。~~）

栈的应用

一定牢记栈先进后出的特性！！！

数值转换（顺序栈）

将10进制数转换成b进制数

void conversion(int b)
{
    SqStack* S;
    initialize(S);
    int a;
    scanf("%d",&a);

    while(a)
    {
        Push(S,a%b);
        a=a/b;
    }

    //输出b进制数
    while(!isEmpty(S))
    {
        int* tmp;
        Pop(S,tmp);
        printf("%d ",tmp->data);
    }
}

括号匹配的检验（顺序栈）

bool Match_Brackets(char* brackets)
{
    SqStack* S;
    initialize(S);
    int i=0;
    for(;brackets[i]!='\0';i++)
    {
        char ch=brackets[i];
        if((ch=='(')||(ch='[')||(ch='{'))
        {
            Push(S,ch);//注意此时栈的结构体内data为char类型。
        }
        else if(ch==')')
        {
            char* x;
            Pop(S,x);
            if(x->data!='(')
            {
                return false;
            }
        }
        else if(ch==']')
        {
            char* x;
            Pop(S,x);
            if(x->data!='[')
            {
                return false;
            }
        }
        else if(ch=='}')
        {
            char* x;
            Pop(S,x);
            if(x->data!='{')
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
    if(S->top!=NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
}

递归调用

函数调用的工作本质
递归调用的工作开销

Stack_and_Queue