栈的实现(C语言)

栈的定义

栈是一种只能在一端进行插入或删除操作的线性表。
运行插入或删除操作的一端称为栈顶，栈的插入和删除一般叫入栈和出栈。栈用顺序存储结构则称为顺序栈，用链式存储结构则称为链栈。

特点

先进后出，后进先出

栈结构

以下是个简单的栈结构

struct stack{
    int data[10];
    int top;
};

顺序存储结构

下面是用顺序存储结构实现的栈源码

#include<stdio.h>
#include<stdbool.h>  
#define maxsize 10
struct stack{
    int data[maxsize];
    int top;
};
//栈初始化
void init(struct stack *);
//判断是否为空
bool empty(struct stack);
//判断是否满
bool full(struct stack);
//入栈
void push(struct stack *,int);
//出栈
int pop(struct stack *);
//取栈顶元素
int get_data(struct stack);
//销毁栈
void destory();
int main(){
    struct stack s;
    int i=0,data;
    printf("初始栈\n");
    init(&s);
    printf("入栈\n");
    for(i;i<10;i++){
        push(&s,i);
    }
    printf("取栈顶元素\n");
    data = get_data(s);
    printf("栈顶元素是%d\n",data);
    printf("出栈\n");
    for(i=0;i<10;i++){
        printf("%d ",pop(&s));
    }
    return 0;
}

void init(struct stack * s){
    
    (*s).top = -1;
}

bool empty(struct stack s){
    if(s.top==-1){
        return true;
    }
    return false;
}

bool full(struct stack s){
    if(s.top==maxsize-1){
        return true;
    }
    return false;
}

void push(struct stack * s,int data){
    if(!full((*s))){
        (*s).top++;
        (*s).data[(*s).top] = data;
    }else{
        printf("栈已满\n");
    }
}

int pop(struct stack * s){
    if(!empty(*s)){
        int data = (*s).data[(*s).top];
        (*s).top--;
        return data;
    }else{
        printf("栈已空\n");
    }
}

int get_data(struct stack s){
    if(empty(s)){
        printf("栈已空\n");
    }else{
        return s.data[s.top];
    }
}

链式存储结构

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

typedef struct stack{
    int data;
    struct stack * next;
}link_stack;

void init(link_stack *);
void push(link_stack *,int);
int pop(link_stack *);
void print_stack(link_stack *);
int main(){
    link_stack s;
    init(&s);
    push(&s,11);
    push(&s,22);
    push(&s,33);
    push(&s,44);
    print_stack(&s);
    return 0;
}

void init(link_stack * s){
    s = (link_stack *)malloc(sizeof(link_stack));
    s->next = NULL;
}

void push(link_stack * s,int data){
    link_stack * p = (link_stack *)malloc(sizeof(link_stack));
    p->data = data;
    p->next = s->next;
    s->next = p;
}

int pop(link_stack * s){
    link_stack * p = s->next;
    int data = p->data;
    free(p);
    s->next = p->next;
    return data;
}

void print_stack(link_stack * s){
    link_stack * p;
    p = s->next;
    printf("输出栈\n");
    while(p){
        printf("%d ",p->data);
        p = p->next;
    }
}