栈

概念

栈是一种后进先出的线性表（LIFO）,根据存储结构可以分为顺序栈和链栈。

1. 顺序栈

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MaxSize 100

typedef int DataType;
typedef struct seqstack
{
    DataType * data;//栈中元素
    int top;//栈顶指针
    int size;//最大栈容量
}SeqStack;
//初始化
void Initailize(SeqStack * S)
{
    S->data = (DataType *)malloc(sizeof(DataType)*MaxSize);
    if(S->data == NULL)
    {
        puts("初始化失败");
        exit(1);
    }
    S->top = -1;
    S->size = MaxSize;



}
//判断栈是否为空
bool IsEmpty(SeqStack * S)
{
    if (S->top < 0)
        return true;
    else
        return false;

}
//判断栈是否满
bool IsFull(SeqStack * S)
{
    if(S->top == MaxSize - 1)
        return true;
    else
        return false;
}
//进栈
bool Push(SeqStack * S,DataType data)
{
    if (IsFull(S))
    {
        puts("栈已满，无法入栈");
        return false;
    }
    S->top++;
    S->data[S->top] = data;
    return true;
}
//出栈
DataType Pop(SeqStack * S)
{
    DataType x;
    if(IsEmpty(S))
    {
        puts("栈空，无法出栈");
        return NULL;
    }

    x = S->data[S->top];
    S->top--;
    return x;



}
//取栈顶元素
DataType GetTop(SeqStack * S)

{
    if (IsEmpty(S))
    {
        puts("空栈");
        return NULL;
    }
    return S->data[S->top];
}
//遍历栈元素
void Traverse(SeqStack * S)
{
    int n = S->top;
    int i;
    for (i = n; i >=0; i--)
        printf("%d ",S->data[i]);
    printf("\n");
}
//清空栈
void Clear(SeqStack * S)
{
    S->top = -1;
}
int main(void)
{
    SeqStack seqstack;
    Initailize(&seqstack);
    Push(&seqstack,2);
    Push(&seqstack,4);
    Push(&seqstack,5);
    Push(&seqstack,8);
    Traverse(&seqstack);
    Pop(&seqstack);
    Traverse(&seqstack);
    puts("取栈顶元素");
    int x = GetTop(&seqstack);
    printf("x is %d\n",x);
    return 0;
}

2.链栈

//链式栈
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int DataType;
//定义一个节点
typedef struct node
{
    DataType data;
    struct node * next;
}Node,*PNode;
//构造一个栈
typedef struct stack
{
    PNode pTop; //栈顶指针
    PNode pBottom;//栈底指针
}STACK,*PSTACK;

//创建一个空栈，里面没有任何有效数据；
void Create_Stack(PSTACK S)
{
    S->pBottom=(Node *)malloc(sizeof( Node));
    if(NULL==S->pBottom)
    {
        printf("Memory allocation failure");
        exit(-1);
    }
    S->pTop=S->pBottom;
    S->pTop->data=0;
    S->pTop->next=NULL;  //防止出现野指针
}

//进栈
void Push_Stack(PSTACK S,DataType val)
{
    PNode p=(Node *)malloc(sizeof(Node));
    if(NULL==p)
    {
        printf("Memory allocation failure");
        exit(-1);
    }
    p->data=val;
    p->next=S->pTop;  //让p的指针域指向上一个节点
    S->pTop=p;        //让pTop指针指向栈顶元素
}

void Traverse_Stack(PSTACK S)
{
    PNode p = S->pTop;
    printf("栈中的元素是：\n");
    while(p != S->pBottom)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

bool Is_Empty(PSTACK S)
{
    if(S->pTop == S->pBottom)
        return true;
    else
        return false;
}

bool Pop_Stack(PSTACK S,DataType * val)
{
    if(Is_Empty(S))
        return false;
    else
    {
        PNode p = S->pTop;
        *val = S->pTop->data;
        S->pTop = S->pTop->next;
        free(p);//释放p指针所指向的那个节点内存
        p = NULL;
        return true;
    }
}

void Clear_Stack(PSTACK S)
{
    if(Is_Empty(S))
        return;
    else
    {
        PNode p = NULL;
        while(S->pTop != S->pBottom)
        {
            p = S->pTop;
            S->pTop = S->pTop->next;
            free(p);
            p = NULL;
        }
    }
}

int main(void)
{
    Node  node;
    DataType data ;
    Create_Stack(&node);
    printf("进栈....\n");
    Push_Stack(&node,3);
    Push_Stack(&node,0);
    Push_Stack(&node,8);
    Push_Stack(&node,6);
    printf("进栈完成\n");
    printf("遍历栈\n");
    Traverse_Stack(&node);
    printf("删除栈顶元素\n");
    Pop_Stack(&node,&data);
    printf("被删除元素：%d\n",data);
    printf("遍历栈\n");
    Traverse_Stack(&node);
    return 0;

}