【数据结构】——栈

速通回忆

下面是一个链表栈的演示，数组栈的演示放在最后面

如果你不知道什么是链表栈，建议先别看这个“速通回忆”，先看一下理论部分

如果你之前学过链表，可以直接看我下面的这个项目，实现了下面专题中所有内容；

如果你是个新手，建议先不要看下面这个项目，先好好看一下下面每一个部分的代码思路，并尝试自己去写一下

/* 
 * 功能：链表栈操作
 * 作者：此乃刘同学（www.liustu.com.cn）
 */

#include "stdio.h"
#include "stdlib.h"

/* 数据结构体 */
typedef struct node_data{
    int num;
    struct node_data *next;
}node;

/* 链表栈结构体 */
typedef struct{
    node *top;
    int count;
}Link_Stack;

/* 链表栈初始化 */
Link_Stack *LinkStackInit(){
    Link_Stack *temp = (Link_Stack*)malloc(sizeof(Link_Stack));
    if(temp==NULL){
        printf("ERROR\n");
        return NULL;
    }  
    temp->top = NULL;
    temp->count = 0;
    return temp;
}

/* 链表栈入栈 */
void LinkStackPush(Link_Stack *stack, int push_num){
    /* 动态分配数据的存储空间 */
    node *node_temp = (node *)malloc(sizeof(node));
    /* 存放数字到结构体中 */
    node_temp->num = push_num;
    node_temp->next = NULL;
    /* 入栈操作 */
    node_temp->next = stack->top;
    stack->top = node_temp;
    stack->count ++; 
}

/* 链表栈出栈操作 */
int LinkStackPop(Link_Stack *stack){
    if(stack->top == NULL){
        printf("栈为空，无法出栈\n");
        /* 返回一个特殊值表示栈为空 */
        return -1;
    }
    int temp_data;
    /* 读取栈顶的数据 */
    node *temp = stack->top;
    temp_data = temp->num;
    /* 栈顶指针指向下一个节点 */
    stack->top = stack->top->next;
    /* 计数器减一 */
    stack->count--;
    /* 释放存储空间 */
    free(temp);
    return temp_data;
}

/* 链表栈显示 */
void LinkStackShow(Link_Stack *stack){
    node *node_temp = stack->top;
    int count_temp = stack->count;
    printf("栈的遍历显示，是从上往下比较\n");

    while(count_temp--){
        printf("————————\n");
        printf("| %d   |\n",node_temp->num);
        node_temp= node_temp->next;
    }
    printf("————————\n");
}

int main()
{
    Link_Stack *stack = LinkStackInit();
    if(stack == NULL){
        return -1;
    }

    LinkStackPush(stack, 10);
    LinkStackPush(stack, 20);
    LinkStackPush(stack, 30);

    printf("当前栈的内容：\n");
    LinkStackShow(stack);

    printf("出栈元素：%d\n", LinkStackPop(stack));
    printf("出栈元素：%d\n", LinkStackPop(stack));

    printf("当前栈的内容：\n");
    LinkStackShow(stack);

    LinkStackPush(stack, 40);
    printf("当前栈的内容：\n");
    LinkStackShow(stack);

    printf("出栈元素：%d\n", LinkStackPop(stack));
    printf("出栈元素：%d\n", LinkStackPop(stack));
    printf("出栈元素：%d\n", LinkStackPop(stack)); // 尝试从空栈中出栈

    free(stack);

    return 0;
}

栈的概念

栈是一种先进后出的数据结构

真男人，直接从最复杂的开始学习
其实学会了最复杂的，简单的一看就明白

栈的结点设计

栈分为数组栈和链表栈
其区别是数组栈使用数组进行功能的模拟，实现较为快速和便利；而链表栈使用链表的思路去设计，实现较为麻烦，但是其稳定不易出错

在链表栈中又分为静态链表栈和动态链表栈
静态链表栈给定栈的空间大小，不允许超过存储超过给定数据大小的元素；而动态栈使用的是自动创建空间的方法进行创建

我们可以设计出两个结构体，

一个结构体Node表示结点，其中包含有一个data域和next指针

目前的设计如同单链表，接下来，为这个进行限制性的设计，我们额外添加一个结构体，其包括了一个永远指向栈头的指针top和一个计数器count记录元素个数

//栈的结点设计
//单个结点设计，数据和下一个指针
typedef struct node     
{
    int data; 
    struct node *next;
} Node;
//利用上面的结点创建栈，分为指向头结点的top指针和计数用的count
typedef struct stack    
{
    Node *top;
    int count;
} Link_Stack;

入栈

入栈(push)操作时，我们只需要将新的结点的next指针指向top指针，再将top指针转移，指向新的结点

//入栈 push
Link_Stack *Push_stack(Link_Stack *p, int elem)
{
    if (p == NULL)
        return NULL;
    Node *temp;
    temp=(Node*)malloc(sizeof(Node));
    //temp = new Node;
    temp->data = elem;
    temp->next = p->top;
    p->top = temp;
    p->count++;
    return p;
}

出栈

是在栈不为空的情况下，将栈顶的元素删除，同时top指针，next向下

//出栈 pop
Link_Stack *Pop_stack(Link_Stack *p)
{
    Node *temp;
    temp = p->top;
    if (p->top == NULL)
    {
        printf("错误：栈为空");
        return p;
    }
    else
    {
        p->top = p->top->next;
        free(temp);
        //delete temp;
        p->count--;
        return p;
    }
}

遍历

在栈不为空的情况下，一次从栈顶元素向下访问，直到指针指向空

//遍历栈：输出栈中所有元素
int show_stack(Link_Stack *p)
{
    Node *temp;
    temp = p->top;
    if (p->top == NULL)
    {
        printf("");
        printf("错误：栈为空");
        return 0;
    }
    while (temp != NULL)
    {
        printf("%d\t", temp->data);
        temp = temp->next;
    }
    printf("\n");
    return 0;
}

数组栈演示

/* 
 * 功能：数组栈操作
 * 作者：此乃刘同学（www.liustu.com.cn）
 */

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define MAX 100

typedef struct{
    int nums[MAX];
    int top;
}stack;

/* 数组栈初始化 */
stack *stack_Init(){
    stack *temp = (stack *)malloc(sizeof(stack));
    if(temp == NULL){
        printf("ERROR\n");
        return NULL;
    }
    memset(temp->nums, 0, sizeof(temp->nums));
    temp->top = 0;
    return temp;
}

void StackPush(stack *s, int num){
    if(s->top < MAX){
        s->nums[s->top++] = num;
    } else {
        printf("栈已满，无法入栈\n");
    }
}

int StackPop(stack *s){
    int num_temp;
    if(s->top!=0){
        num_temp = s->nums[--s->top];
        s->nums[s->top] = 0;
        return num_temp;
    }else{
        printf("栈为空\n");
        return -1;
    }
}

void StackShow(stack *s){
    printf("|________|\n");
    for(int i=s->top; i>0; i--){
        printf("|   %d   |\n",s->nums[i-1]);
        printf("|________|\n");
    }
    printf("|________|\n");
}

int main(){
    stack *s = stack_Init();
    if(s == NULL){
        return -1;
    }

    StackPush(s, 10);
    StackPush(s, 20);
    StackPush(s, 30);

    printf("当前栈的内容：\n");
    StackShow(s);

    printf("出栈元素：%d\n", StackPop(s));
    printf("出栈元素：%d\n", StackPop(s));

    printf("当前栈的内容：\n");
    StackShow(s);

    StackPush(s, 40);
    printf("当前栈的内容：\n");
    StackShow(s);

    printf("出栈元素：%d\n", StackPop(s));
    printf("出栈元素：%d\n", StackPop(s));
    printf("出栈元素：%d\n", StackPop(s)); // 尝试从空栈中出栈

    free(s);
    return 0;
}