顺序栈

表示

#define MAXSIZE 100
typedef struct {
    SElemType *base; //栈底指针(表头端)
    SelemType *top;  //栈顶指针(表尾端)
    int stacksize;   //栈可用最大容量
}SqStack;

初始化

Status InitStack(SqStack &S) {
    //构造一个空栈
    S.base = (SElemType*)malloc(MAXSIZE*sizeof*(SElemType));
    if (!S.base) 
        exit (OVERFLOW);  //存储分配失败
    
    S.top = S.base;       //栈顶指针等于栈底指针
    S.stacksize = MAXSIZE;
    return OK;
}

判断是否为空

Status StackEmpty(SqStack S) {
    if (S.top == S.base)   //栈为空标志：S.top == S.base
        return TRUE;
    else
        return FALSE;
}

清空

Status ClearStack(SqStack &S) {
    if (S.base)
        S.top = S.base;
    return OK;
}

销毁

Status Destroy(SqStack &S) {
    if (S.base){
        free S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
}

入栈

Status Push(SqStack &S, SElemType e) {
    if (S.top - S.base == S.stacksize) //栈满
        return ERROR;
    *S.top++ = e;   //*S.top = e; S.top++;
    return Ok;
}

出栈

Status Pop(SqStack &S, SElemType &e) {
    if (S.top == S.base)   //栈为空
        return ERROR;
    e = *--S.top;  //--S.top; e = *S.top
    return OK;
}

获取栈顶元素值

Status GetTop(SqStack S, SElemType &e) {
    if (S.top == S.base)
        return ERROR;
    e = *(S.top-1);
    return OK;
}

链栈

表示

1. 链表的头指针就是栈顶
2. 不需要头结点
3. 基本不存在栈满的情况
4. 空栈相当于头指针指向空
5. 插入和删除仅在栈顶出执行

typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;

初始化

void InitStack(LinkStack &S) {
    S = NULL; //空栈，栈顶指针置空
    return OK;
}

判断是否为空

Status StackEmpty(LinkStack S) {
    if (S == NULL)
        return TRUE;
    else
        return FALSE;
}

入栈

Status Push(LinkStack &S, SElemType e) {
    StackNode *p;
    p->data = e;    //将新结点数据域置为 e
    p->next = S;    //将新结点插入栈顶
    S = p;          //修改栈顶指针
    return OK;
}

出栈

Status Pop(LinkStatck &S, SElemType e) {
    if (S == NULL)
        return ERROR;
    e = S->data;
    p = S;
    S = S->next;
}

C语言实现代码

顺序栈

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 5    /* 栈最大容量 */
#define Empty 0        /* 空 */
#define Full 1        /* 满 */
#define Avail -1    /* 可用 */

typedef struct sta
{
    int *top;            /* 栈顶指针 */
    int *base;        /* 栈底指针 */
    int stacksize;        /* 栈的最大容量 */
}SqStack;

SqStack InitStack (SqStack p);    // 初始化栈
SqStack Push (SqStack p);        //入栈
SqStack Pop (SqStack p);        // 出栈
void DisplyStack (SqStack p);    // 遍历栈中元素
int StackEmpty (SqStack p);    // 判断栈是否为空
int StackFull (SqStack p);    // 判断栈是否为满

int main()
{
    SqStack p;
    char ch;

    p.stacksize = MAX_SIZE;
    p = InitStack (p);    /* 初始化栈 */

    //入栈
    printf("你想要添加元素吗到栈吗? (Y/N)\n");
    scanf(" %c", &ch);
    while (ch == 'Y' || ch == 'y')
    {
        p = Push (p);    /* 入栈 */
        DisplyStack (p);/* 打印栈中元素 */
        printf("你想要添加元素吗到栈吗?(Y/N)\n");
        scanf(" %c", &ch);
    }

    //出栈
    printf("你想出栈吗？(Y/N)\n");
    scanf(" %c", &ch);
    while (ch == 'Y' || ch == 'y')
    {
        p = Pop (p);
        DisplyStack (p);
        printf("你想出栈吗？(Y/N)\n");
        scanf(" %c", &ch);
    }
    return 0;
}

//初始化
SqStack InitStack (SqStack p)
{
    p.base = (int *)malloc(p.stacksize * sizeof(int));
    if (p.base == NULL)
    {
        printf("初始化栈失败\n");
        exit(0);
    }
    p.top = p.base;
    p.stacksize = MAX_SIZE;

    return p;
}

//入栈
SqStack Push (SqStack p)
{
    int data;
    if (StackFull(p) == Full)
    {
        printf("栈空间已满，无法入栈");
        return p;
    }
    printf("输入数字：");
    scanf("%d", &data);
    *p.top = data;
    p.top++;      //*p.top++ = data

    return p;
}

//出栈
SqStack Pop (SqStack p)
{
    int data;
    if (StackEmpty(p) == Empty)
    {
        printf("栈为空栈，无法出栈 ");
        return p;
    }
   // p.top--;
   // printf("出栈元素为：%d\n", *p.top);
     data = *--p.top;
     printf("出栈元素为：%d\n",data);
    return p;
}

//判断栈是否为空
int StackEmpty (SqStack p)
{
    if (p.top == p.base)
    {
        return Empty;
    }
    else
    {
        return Avail;
    }
}

//判断栈是否为满
int StackFull (SqStack p)
{
    if (p.top - p.base == p.stacksize)
    {
        return Full;
    }
    else
    {
        return Avail;
    }
}

//遍历栈中元素，从栈顶到栈底
void DisplyStack (SqStack p)
{
    if (StackEmpty(p) == Empty)
    {
        printf("栈为空栈，无法遍历\n");
        return;
    }
    printf("栈中元素为:\n");
    printf("顶端      [");
    while (p.top != p.base)
    {
        //p.top--;
        //printf("%d",*p.top);
        printf("%d", *--p.top);
    }
    printf("]       底端\n");
}

链栈

#include <stdio.h>
#include <stdlib.h>

typedef struct lineStack {
    int data;
    struct StackNode *next;
}StackNode, *LineStack;

LineStack push(LineStack S, int a);  //入栈
LineStack pop(LineStack S);            //出栈

int main() {
    LineStack S = NULL;
    S = push(S, 1);
    S = push(S, 2);
    S = push(S, 3);
    S= push(S, 4);
    S = pop(S);
    S = pop(S);
    S= pop(S);
    S = pop(S);
    S = pop(S);
    return 0;
}


//入栈
LineStack push(LineStack S, int a) {
    //创建存储新元素的节点
    StackNode* line = (LineStack)malloc(sizeof(StackNode*));
    line->data = a;
    //新节点与头节点建立逻辑关系
    line->next = S;
    //更新头指针的指向
    S = line;
    return S;
}

//出栈
LineStack pop(LineStack S) {
    if (S) {
        //声明一个新指针指向栈顶节点
        StackNode* p = S;
        //更新头指针
        S = S->next;
        printf("出栈元素：%d ", p->data);
        if (S) {
            printf("新栈顶元素：%d\n", S->data);
        }
        else {
            printf("栈已空\n");
        }
        free(p);
    }
    else {
        printf("栈内没有元素(空栈)");
        return S;
    }
    return S;
}