C语言实现顺序栈-一一网

栈图解

栈的示意图

顺序栈的常规操作

/********************* 顺序栈的常规操作 **************************/

Stack      InitStack();                // 初始化栈
int        StackFull();                // 判断栈满
int        StackEmpty();               // 判断栈空
int        StackLength();              // 求栈长(栈元素个数)
int        Push();                     // 入栈 压栈
ElemType   Pop();                      // 出栈 弹栈

/***************************************************************/
复制代码

定义顺序栈结构体

#include "stdio.h"
#include "malloc.h"

#define  TRUE  1
#define  FALSE 0
#define  MAXSIZE 100        // 顺序栈的最大存储量

typedef int ElemType;        // 顺序栈存储元素的数据类型

/*
 *    定义顺序栈结构体
*/
typedef struct SeqStack{
    ElemType datas [MAXSIZE];
    int top;    // 栈顶指针
}*Stack;
复制代码

注意：这里 栈顶指针top，指向的是元素的上一个位置，也只可以指向元素当前位置。

如果指向元素当前位置，初始化顺序栈的时候可以把 top = -1;

栈顶指针top，指向的是元素的上一个位置（初始 top = 0）。

入栈（Push），先把元素放入栈中，后让 栈顶指针top 后移 ++
- s -> datas[s -> top] = data;
- s -> top++;
出栈（Pop），先让 栈顶指针(top) 前移 -- ，后让栈顶元素出栈
- s -> top--;
- return s -> datas[s -> top];

栈顶指针top，指向的是元素的当前位置（初始 top = -1）。

入栈（Push），，先把 栈顶指针top 后移 ++ ，后让元素放入栈中
- s -> top++;
- s -> datas[s -> top] = data;
出栈（Pop），先取出栈顶元素，后让 栈顶指针(top) 前移 --
- data = s -> datas[s -> top];
- s -> top--;
- return data;

初始化顺序栈

/*
 *    初始化顺序栈
*/
Stack InitStack(){
    // 分配顺序栈内存空间
    Stack s = (Stack)malloc(sizeof(struct SeqStack));
    s -> top = 0;
    return s;
}
复制代码

顺序栈判满

/*
 *    顺序栈判满
 *    s 顺序栈
*/
int StackFull(Stack s){
    if(s == NULL){
        return FALSE;
    }
    return s -> top == MAXSIZE;
}
复制代码

顺序栈判空

/*
 *   顺序栈判空
 *   s 顺序栈
*/
int StackEmpty(Stack s){
    if(s == NULL){
        return FALSE;
    }
    return s -> top == 0;
}
复制代码

计算顺序栈的长度

/*
 *   求顺序栈的长度（元素的个数）
 *   s 顺序栈
*/
int StackLength(Stack s){
    if(s == NULL){
        return FALSE;
    }
    return s -> top;
}

复制代码

顺序栈入栈（Push）

/*
 *  入栈 压栈
 *  s 顺序栈
 *  data 入栈数据
*/
int Push(Stack s, ElemType data){
    // 顺序栈判满
    if(StackFull(s)){
        return FALSE;
    }
    s -> datas[s -> top] = data;
    s -> top ++;
    return TRUE;
}
复制代码

顺序栈出栈（Pop）

/*
 *   出栈 弹栈
 *   s 顺序栈
*/
ElemType Pop(Stack s){
    int data;
    // 判栈空
    if(StackEmpty(s)){
        return FALSE;
    }
    s -> top--;
    data = s -> datas[s -> top];
    return data;
}
复制代码

顺序栈各操作测试

int main(int argc, char const *argv[])
{
    Stack s = InitStack();

    printf("StackEmpty():%d\n", StackEmpty(s));
    printf("StackLength():%d\n\n", StackLength(s));

    // 入栈元素
    ElemType datas[] = {2, 4, 6, 8, 10};

    // 动态计算入栈元素个数
    int len = sizeof(datas) / sizeof(datas[0]);    

    // for循环依次入栈
    printf("Push():");
    for(int i = 0; i < len; i++){
        printf("%d\t", datas[i]);
        Push(s, datas[i]);
    }
    printf("\nStackEmpty():%d\n", StackEmpty(s));
    printf("StackLength():%d\n\n", StackLength(s));

    // 出栈 弹栈
    printf("Pop():");
    for(int i = 0; i < len; i++){
        printf("%d\t", Pop(s));
    }
    printf("\nStackEmpty():%d\n", StackEmpty(s));
    printf("StackLength():%d\n\n", StackLength(s));
    return 0;
}
复制代码

结果如下：

StackEmpty():1
StackLength():0

Push():2        4       6       8       10
StackEmpty():0
StackLength():5

Pop():10        8       6       4       2
StackEmpty():1
StackLength():0
复制代码