用C语言实现先进后出的数据结构---栈

数据结构----栈

一、基本概念

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

                                                      ---百度百科

二、用C语言实现栈

1.定义栈的结构体

typedef struct Stack{
    struct Stack *bottom;//栈顶指针指向底部
    int size;//栈内元素的个数
    int top_elem;//栈顶元素的值
}S;

2.定义创建栈的函数

S *create_Stack(){
    S *Stack = (S *)malloc(sizeof(S));
    Stack->bottom = NULL;
    Stack->size = 0;
    return Stack;
}

3.定义创建栈内元素的函数

因为创建的元素只能在栈顶进行入栈操作，所以也可将其称为栈顶元素。

S *create_new_Elem(int data)//创建栈顶元素
{
    S *new_elem = (S *)malloc(sizeof(S));
    new_elem->bottom = NULL;
    new_elem->top_elem = data;
    return new_elem;
}

4.入栈

void push(S *Stack, S *new_elem)//入栈
{
    new_elem->bottom = Stack->bottom;
    Stack->bottom = new_elem;
    Stack->size++;
}

5.出栈

void pop(S *Stack)//出栈,只允许在栈顶操作
{
    Stack->size--;
    S *current = Stack->bottom;
    S *prev = Stack;
    if(Stack->size <= 0){
        printf("栈顶为空，无法出栈");
    }
    else{
        prev->bottom = current->bottom;
        free(current);//此处不能直接free(Stack)!
    }
}

6.获取栈顶元素

int top(S *Stack)//获取栈顶元素
{
    if(Stack->size == 0){
        printf("栈顶为空，无法获取!\n");
        return -1;
    }
    else{
        return Stack->bottom->top_elem;
    }
}

7.打印整个栈内的元素

void Print_Stack(S *Stack)//打印整个栈内的元素
{
    while(Stack->bottom != NULL){
        printf("%d\n↓\n", top(Stack));
        Stack = Stack->bottom;
    }
}

三、代码实现

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

typedef struct Stack{
    struct Stack *bottom;//栈顶指针指向底部
    int size;//栈内元素的个数
    int top_elem;//栈顶元素的值
}S;

S *create_Stack(){
    S *Stack = (S *)malloc(sizeof(S));
    Stack->bottom = NULL;
    Stack->size = 0;
    return Stack;
}

S *create_new_Elem(int data)//创建栈顶元素
{
    S *new_elem = (S *)malloc(sizeof(S));
    new_elem->bottom = NULL;
    new_elem->top_elem = data;
    return new_elem;
}

void push(S *Stack, S *new_elem)//入栈
{
    new_elem->bottom = Stack->bottom;
    Stack->bottom = new_elem;
    Stack->size++;
}

void pop(S *Stack)//出栈,只允许在栈顶操作
{
    Stack->size--;
    S *current = Stack->bottom;
    S *prev = Stack;
    if(Stack->size <= 0){
        printf("栈顶为空，无法出栈");
    }
    else{
        prev->bottom = current->bottom;
        free(current);//此处不能直接free(Stack)!
    }
}

int top(S *Stack)//获取栈顶元素
{
    if(Stack->size == 0){
        printf("栈顶为空，无法获取!\n");
        return -1;
    }
    else{
        return Stack->bottom->top_elem;
    }
}

void Print_Stack(S *Stack)//打印整个栈内的元素
{
    while(Stack->bottom != NULL){
        printf("%d\n↓\n", top(Stack));
        Stack = Stack->bottom;
    }
}

int main()
{
    S *My_stack = create_Stack();
    push(My_stack, create_new_Elem(10));
    push(My_stack, create_new_Elem(20));
    push(My_stack, create_new_Elem(30));
    push(My_stack, create_new_Elem(40));
    push(My_stack, create_new_Elem(50));
    // pop(My_stack);
    // pop(My_stack);
    // pop(My_stack);
    // pop(My_stack);
    // pop(My_stack);
    Print_Stack(My_stack);
    free(My_stack);
    return 0;
}