数据结构——栈：顺序栈和链栈

顺序栈(基于数组的顺序栈)

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

typedef enum Status 
{
	error, success
} Status;

typedef int ElemType;

typedef struct SqStack 
{
	ElemType *elem;//存放栈元素(数组)
	int top;//存放栈顶元素的下标
	int size;//栈的长度
} SqStack;

//函数声明
//基于数组的顺序栈
Status initStack(SqStack *s, int sizes);//初始化栈
Status isEmptyStack(SqStack *s);//判断栈是否为空
Status getTopStack(SqStack *s, ElemType *e); //得到栈顶元素
Status clearStack(SqStack *s);//清空栈
Status destroyStack(SqStack *s);//销毁栈
Status stackLength(SqStack *s,int *length);//检测栈长度
Status pushStack(SqStack *s, ElemType data);//入栈
Status popStack(SqStack *s, ElemType *data);//出栈
void show(void);//显示窗口
int judge_int(void);//使用户输入整数

Status initStack(SqStack *s, int sizes)
{
    s->elem = (int *)malloc(sizeof(int) * sizes);
    s->size = sizes;
    s->top = -1;
    return success;
}

Status isEmptyStack(SqStack *s)
{
    if(s->top == -1)
    {
        return success;
    }
    else
    {
        return error;
    }
}

Status getTopStack(SqStack *s, ElemType *e)
{
    if(s->elem == NULL)
    {
        return error;
    }
    else 
    {
        if(s->top == -1)
        {
            printf("当前栈为空\n");
            return success;
        }
        else
        {
            *e = *s->elem + s->top;
            printf("当前栈顶元素是：%d\n", *e);
            return success;
        }
    }
}

Status clearStack(SqStack *s)
{
    if(s->elem == NULL)
    {
        return error;
    }
    else 
    {
        if(s->top == -1)
        {
            return success;
        }
        else 
        {
            s->top = -1;
            return success;
        }
    }
}

Status destroyStack(SqStack *s)
{
    if(s->elem == NULL)
    {
        return error;
    }
    else 
    {
        free(s->elem);
        s->elem = NULL;
        return success;
    }
}

Status stackLength(SqStack *s, int *length)
{
    if(s->elem == NULL)
    {
        return error;
    }
    else
    {
        length = &s->top;
        printf("当前栈的长度为%d\n", *length + 1);
        return success;
    }
    
}

Status pushStack(SqStack *s, ElemType data)
{
    s->top++;
    *(s->elem + s->top) = data;
    return success;
}

Status popStack(SqStack *s, ElemType *data)
{
    if(s->top == -1)
    {
        printf("栈为空\n");
        return error;
    }
    else
    {
        *data = *s->elem + s->top;
        s->top--;
        return success;
    }
}

void show(void)
{
    printf("\n\n\n\n        顺序栈\n\n");
    printf("     1.初始化栈\n");
    printf("     2.判断栈是否为空\n");
    printf("     3.得到栈顶元素\n");
    printf("     4.清空栈\n");
    printf("     5.销毁栈\n");
    printf("     6.检测栈的长度\n");
    printf("     7.入栈\n");
    printf("     8.出栈\n");
    printf("     9.退出\n\n");
    printf("请输入对应的数字(1-9)：");
}

int judge_int(void)  //防止用户乱输入其他的字符
{
    int len, num = 0, arg = 1;
    char word[10];  
    int m, j= 1, k;
    while(j)
    {
        scanf("%s", word);
        len = strlen(word);
        for(m = 0;m<len;m++)
        {
            if(word[m]<'0' || word[m]>'9')  //检验是否有乱输入其他字符
            {
                printf("请输入整数：");
                break;
            }
            else
            {
                if(m == len-1)
                    j = 0;
            }
        }
    }
    j = len-1;
    for(m=0;m<len;m++)  // 将字符重新转换为数字
    {
        for(k=0;k<j;k++)
            arg *= 10;
        num += (word[m]-'0')*arg;
        arg = 1;
        j--;
    }
    return num;
} 

int main(void)
{
    SqStack s;
    s.elem = NULL;
    int choice, size;
    ElemType data;
    ElemType *p = NULL;//用于检测栈的长度
    ElemType temp;//用于获取栈顶元素以及储存出栈的元素

    do
    {
        show();
        choice = judge_int();
        system("cls");
        switch(choice)
        {
            case 1://初始化栈
            {
                printf("请输入栈的长度：");
                scanf("%d", &size);
                if(initStack(&s, size))
                {
                    printf("初始化成功\n");
                }
                else 
                {
                    printf("初始化失败\n");
                }
                break;
            }
            case 2://判断栈是否为空
            {
                if(s.elem == NULL)
                {
                    printf("请先初始化栈\n");
                }
                else 
                {
                    if(isEmptyStack(&s))
                    {
                        printf("栈为空\n");
                    }
                    else 
                    {
                        printf("栈非空\n");
                    }
                }
                break;
            }
            case 3://得到栈顶元素
            {
                if(!getTopStack(&s, &temp))
                {
                    printf("请先初始化栈\n");
                }
                break;
            }
            case 4://清空栈
            {
                if(clearStack(&s))
                {
                    printf("清空完成\n");
                }
                else 
                {
                    printf("请先初始化栈\n");
                }
                break;
            }
            case 5://销毁栈
            {
                if(destroyStack(&s))
                {
                    printf("栈销毁完成\n");
                }
                else 
                {
                    printf("请先初始化栈\n");
                }
                break;
            }
            case 6://检测栈的长度
            {
                if(!stackLength(&s, p))
                {
                    printf("请先初始化栈\n");
                }
                break;
            }
            case 7://入栈
            {
                if(s.elem == NULL)
                {
                    printf("请先初始化栈\n");
                }
                else if(s.top == s.size - 1)
                {
                    printf("栈满\n");
                    printf("入栈失败\n");
                }
                else 
                {
                    printf("请输入数据：");
                    scanf("%d", &data);
                    if(!pushStack(&s, data))
                    {
                        printf("入栈失败\n");
                    }
                    else 
                    {
                        printf("入栈完成\n");
                    }
                }
                break;
            }
            case 8://出栈
            {
                if(s.elem == NULL)
                {
                    printf("请先初始化栈\n");
                }
                else
                {
                    if(popStack(&s, &temp))
                    {
                        printf("出栈成功\n");
                    }
                    else 
                    {
                        printf("出栈失败\n");
                    }
                }
                break;
            }
            case 9://退出程序
            {
                break;
            }
            default:
            {
                printf("请重新输入数字！(1-9)\n");
                break;
            }
        }
    } while (choice != 9);

	system("pause");
    return 0;
}

链栈

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

#define STACK_H_INCLUDED

typedef enum Status 
{
    error, 
	success
} Status;

typedef int ElemType;

typedef struct StackNode
{
	ElemType data;
	struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack
{
	LinkStackPtr top;
	int	count;
}LinkStack;

//函数的声明
//链栈
Status initLStack(LinkStack *s);//初始化栈
Status isEmptyLStack(LinkStack *s);//判断栈是否为空
Status getTopLStack(LinkStack *s,ElemType *e);//得到栈顶元素
Status clearLStack(LinkStack *s);//清空栈
Status destroyLStack(LinkStack *s);//销毁栈
Status LStackLength(LinkStack *s,int *length);//检测栈长度
Status pushLStack(LinkStack *s,ElemType data);//入栈
Status popLStack(LinkStack *s,ElemType *data);//出栈
void show(void);//显示界面
int judge_int(void);//使用户输入整数

Status initLStack(LinkStack *s)
{
    s->top = NULL;
    s->count = 0;
    return success;
}

Status isEmptyLStack(LinkStack *s)
{
    if(s->top == NULL)
    {
        return success;
    }
    else
    {
        return error;
    }
}

Status getTopLStack(LinkStack *s,ElemType *e)
{
    if(s->top == NULL)
    {
        printf("栈为空\n");
        return error;
    }
    else
    {
        *e = s->top->data;
        printf("栈顶元素为：%d\n", *e);
        return success;
    }
}

Status clearLStack(LinkStack *s)
{
    if(s->top == NULL)
    {
        printf("栈为空\n");
        return error;
    }
    else
    {
        s->top = NULL;
        return success;
    }
}

Status destroyLStack(LinkStack *s)
{
    while(!isEmptyLStack(s))
    {
        LinkStackPtr temp;
        temp = s->top;
        s->top = s->top->next;
        free(temp);
    }
    return success;
}

Status LStackLength(LinkStack *s,int *length)
{
    if(s->top == NULL)
    {
        return error;
    }
    else
    {
        length = &s->count;
        printf("当前栈的长度为%d\n", *length);
        return success;
    }
}

Status pushLStack(LinkStack *s,ElemType data)
{
    LinkStackPtr new = (LinkStackPtr)malloc(sizeof(StackNode));
    if(new == NULL)
    {
        printf("内存分配失败\n");
        return error;
    }
    new->data = data;
    new->next = s->top;
    s->top = new;
    s->count++;
    return success;
}

Status popLStack(LinkStack *s,ElemType *data)
{
    if(s->top == NULL)
    {
        printf("栈为空\n");
        return error;
    }
    else
    {
        LinkStackPtr temp;
        *data = s->top->data;
        temp = s->top;
        s->top = s->top->next;
        free(temp);
        s->count--;
        return success;
    }
}

void show(void)
{
    printf("\n\n\n\n        链栈\n");
    printf("     (栈已初始化)\n\n");
    printf("     1.判断栈是否为空\n");
    printf("     2.得到栈顶元素\n");
    printf("     3.清空栈\n");
    printf("     4.销毁栈\n");
    printf("     5.检测栈的长度\n");
    printf("     6.入栈\n");
    printf("     7.出栈\n");
    printf("     8.退出\n\n");
    printf("请输入对应的数字(1-8)：");
}

int judge_int(void)  //防止用户乱输入其他的字符
{
    int len, num = 0, arg = 1;
    char word[10];  
    int m, j= 1, k;
    while(j)
    {
        scanf("%s", word);
        len = strlen(word);
        for(m = 0;m<len;m++)
        {
            if(word[m]<'0' || word[m]>'9')  //检验是否有乱输入其他字符
            {
                printf("请输入整数：");
                break;
            }
            else 
            {
                if(m == len-1)
                    j = 0;
            }
        }
    }
    j = len-1;
    for(m=0;m<len;m++)  // 将字符重新转换为数字
    {
        for(k=0;k<j;k++)
            arg *= 10;
        num += (word[m]-'0')*arg;
        arg = 1;
        j--;
    }
    return num;
} 

int main(void)
{
    int choice;
    int *len = NULL;
    ElemType data;
    LinkStack s;
    ElemType temp;//用于获取栈顶元素及储存出栈的元素
    
    if(!initLStack(&s))
    {
        printf("栈初始化失败\n");
    }

    do
    {
        show();
        choice = judge_int();
        system("cls");
        switch(choice)
        {
            case 1://判断栈是否为空
            {
                if(isEmptyLStack(&s))
                {
                    printf("栈为空\n");
                }
                else
                {
                    printf("栈非空\n");
                }
                break;
            }
            case 2://得到栈顶元素
            {
                if(!getTopLStack(&s, &temp))
                {
                    printf("获取失败\n");
                }
                break;
            }
            case 3://清空栈
            {
                if(clearLStack(&s))
                {
                    printf("清空完成\n");
                }
                else
                {
                    printf("清空失败\n");
                }
                break;
            }
            case 4://销毁栈
            {
                if(destroyLStack(&s))
                {
                    printf("销毁完成\n");
                }
                else
                {
                    printf("销毁失败\n");
                }
                break;
            }
            case 5://检测栈的长度
            {
                if(!LStackLength(&s, len))
                {
                    printf("栈为空\n");
                }
                break;
            }
            case 6://入栈
            {
                printf("请输入数据：");
                scanf("%d", &data);
                if(!pushLStack(&s, data))
                {
                    printf("入栈失败\n");
                }
                break;
            }
            case 7://出栈
            {
                if(popLStack(&s, &temp))
                {
                    printf("出栈完成\n");
                }
                else
                {
                    printf("出栈失败\n");
                }
                break;
            }
            case 8://退出程序
            {
                break;
            }
            default:
            {
                printf("请重新输入数字！(1-8)\n");
                break;
            }
        }
    } while (choice != 8);

	system("pause");
    return 0;
}

学习链栈后，可以利用链栈实现逆波兰计算器(本博主的另一篇文章)

数据结构——栈：顺序栈和链栈

继续阅读

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

CRC32和CRC8校验代码，C语言版

241 Different Ways to Add Parentheses（C代码版）

[转]ISUP信令的IAM消息详细内容

C语言：初学者必定看懂的注释！！！猴子吃桃问题。猴子第一天摘下若干个桃子，每天都吃了前一天剩下的一半零一个，到第10天早上想再吃的时候，就剩下一个桃子. 求第一天共摘多少个桃子。

[转]九大排序算法——C语言实现及详解

笔试面试题目：滑动窗口(二)

while 循环、do- while 循环和 for 循环之间的那点事C语言自学之三种循环比较

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

结构体：typedef与struct的区别

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器

hdu7108哈希