栈

1）栈的基本概念

只能从栈顶进行插入或者删除操作的线性表

2）栈的基本操作

InitStack(&S);

DestroyStack(&L);

Push(&S,x);

Pop(&S,&x);

GetTop(S,&x);

StackEmpty(S);

3）顺序栈的实现

#include <stdio.h>
#define MaxSize 10
typedef struct
{
    int data[MaxSize];
    int top;
}SeqStack;
//初始化
void InitStack(SeqStack &S)
{
    S.top=-1;
}
//栈空判断
bool StackEmpty(SeqStack S)
{
    return(S.top==-1);
}
//入栈
bool Push(SeqStack &S,int x)
{
    if(S.top==MaxSize-1) return false;
    S.data[++S.top]=x;
    return true;
}
//出栈
bool Pop(SeqStack &S,int &x)
{
    if(S.top==-1) return false;
    x=S.data[S.top--];
    return true;
}
//读取栈顶元素
bool GetTop(SeqStack S,int &x)
{
    if(S.top==-1) return false;
    x=S.data[S.top];
    return true;
}

//上述代码top指针初始指向栈顶
int main()
{
    SeqStack S;
    InitStack(S);
    printf("%d\n",StackEmpty(S));
    Push(S,2);
    printf("%d\n",StackEmpty(S));
    int x;
    Pop(S,x);
    printf("%d,%d\n",StackEmpty(S),x);
    Push(S,3);
    GetTop(S,x);
    printf("%d,%d\n",StackEmpty(S),x);
    return 0;
}

缺点：存储容量不可改变

4）链式栈

#include <stdio.h>
#include <stdlib.h>
//定义栈结点
typedef struct SNode{
    int data;
    SNode * next;
}*LinkStack,SNode;
//初始化栈（不带头结点）
bool InitStack(LinkStack &S)
{
    S=NULL;
    return true;
}
//判空
bool StackEmpty(LinkStack S)
{
    return (S==NULL);
}
//入栈操作
bool Push(LinkStack &S,int x)
{
    //在头部插入元素
    SNode * p=(SNode *)malloc(sizeof(SNode));
    //这里并不需要区分是不是第一个结点，两者操作时一致的！！！
    p->data=x;
    p->next=S;
    S=p;
    return true;
}
//出栈操作（不带头结点）
bool Pop(LinkStack &S,int &x)
{
    if(S==NULL) return false;
    SNode * p=S;
    x=S->data;
    S=S->next;
    free(p);
    return true;
}
//打印栈中元素（不带头结点）
void PrintStack(LinkStack S)
{
    if(S==NULL) return;
    while(S!=NULL)
    {
        printf("%d ",S->data);
        S=S->next;
    }
    printf("\n");
}

//对于链式存储结构实现的栈（不带头结点）进行增删改查操作
int main(void)
{
    int x;
    LinkStack S;
    InitStack(S);
    printf("%d\n",StackEmpty(S));
    Push(S,1);
    Push(S,2);
    Push(S,5);
    Push(S,1);
    PrintStack(S);
    Pop(S,x);
    Pop(S,x);
    PrintStack(S);
    return 0;
}