数据结构C语言——栈的实现（顺序、链式结构）

2 栈

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

栈是只允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为先进后出表。

2.1 顺序结构的栈

构思：首先考虑若使用顺序结构来实现栈，则栈的数据域是是个定长的数组，另外需要一个指示栈顶元素位置的整型数字，初始化栈时讲栈顶指针赋值为-1，表示无栈中无元素，这也是判断空栈的条件。入栈则需要将栈顶指针加1（注意是否溢出），然后将数据压入栈中；出栈则需要将栈顶元素取出后，将栈顶指针减1（注意是否为空栈）。

• C 语言实现

Makefile

all:sqstack

sqstack:sqstack.o main.o
	$(CC) $^ -o $@

clean:
	rm *.o sqstack -rf

sqstack.h

#ifndef SQSTACK_H__
#define SQSTACK_H__

#define MAXSIZE 5

typedef int datatype;
typedef struct node_st  sqstack;


struct node_st{
    datatype data[MAXSIZE];
    int top;
};


sqstack *stack_create();

int stack_isempty(sqstack *);

int stack_push(sqstack *, datatype *);

int stack_pop(sqstack *, datatype *);

int stack_top(sqstack *, datatype *);

void stack_travel(sqstack *);

void stack_destroy(sqstack *st);



#endif

sqstack.c

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

#include "sqstack.h"



sqstack *stack_create(){
    sqstack *st;
    st = malloc(sizeof(*st));
    if(st == NULL){
        return NULL;
    }
    
    st->top = -1;
    return st;
}

int stack_isempty(sqstack *st){
    return (st->top == -1);
}

int stack_push(sqstack *st, datatype *data){
    if(st->top == (MAXSIZE-1)){
        return -1;
    }
    st->data[++st->top] = *data;
    return 0;
}

int stack_pop(sqstack *st, datatype *data){
    if(stack_isempty(st)){
        return -1;
    }
    *data = st->data[st->top--];
    return 0;
}

int stack_top(sqstack *st, datatype *data){
    if(stack_isempty(st)){
        return -1;
    }
    *data = st->data[st->top];
    return 0;
}

void stack_travel(sqstack *st){
    if(stack_isempty(st)){
        return ;
    }
    for(int i = 0; i <= st->top; i++){
        printf("%d ", st->data[i]);
    }
    printf("\n");
    return ;
}

void stack_destroy(sqstack *st){
    free(st);
    st = NULL;
    return ;
}

main.c

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

#include "sqstack.h"


int main(){

    datatype arr[] = {23,435,64,123,12};
    sqstack *stack;
    stack = stack_create();

    for(int i = 0; i < sizeof(arr)/sizeof(*arr); i++){
        stack_push(stack, &arr[i]);
    }

    stack_travel(stack);

    datatype tmp = 1;
    int ret;
    ret = stack_push(stack, &tmp);
    if(ret != 0){
        printf("stack_push failed!\n");
    }
    else{
        stack_travel(stack);
    }


    while(stack_pop(stack, &tmp) == 0){
        printf("%d ", tmp);
    }
    printf("\n");
    

    stack_destroy(stack);

    return 0;
}

测试通过qwq

2.2 链式结构的栈

链式结构借助 上一篇文章面向对象封装中的变长结构体中的双向环链来实现。

思想：考虑每次我们只对环链进行头节点的前插入，并对用户进行链表的数据结构隐藏，用户所看见的就是完全符合栈的数据结构的链表，先进后出。

• C 语言实现

Makefile

all:llist

llist:llist.o main.o stack.o
	$(CC) $^ -o $@

clean:
	rm *.o llist -rf

将 llist.h 和 llist.c 拷贝到工程目录下

stack.h

#ifndef STACK_H__
#define STACK_H__

#include "llist.h"

typedef LLIST   STACK;

STACK *stack_create(int size);

int stack_push(STACK *ptr, const void *data);

int stack_pop(STACK *ptr, void *data);

void stack_destroy(STACK *);

#endif

stack.c

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

#include "stack.h"


STACK *stack_create(int size){
    return llist_creat(size);
}


int stack_push(STACK *ptr, const void *data){
    return llist_insert(ptr, data, LLIST_FORWARD);
}

//构造匹配函数保证每次都匹配双向环链的第一个元素
static int always_macth(const void *data1, const void *data2){
    return 0;
}


int stack_pop(STACK *ptr, void *data){
    return llist_fetch(ptr, (void *)0, always_macth,data);//(void *)0匹配参数
}

void stack_destroy(STACK *ptr){
    llist_destroy(ptr);
}

main.c

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

#include "stack.h"

#define NAMESIZE    32

typedef struct score_st SCORE;

struct score_st{
      
    int id;
    char name[NAMESIZE];
    int math;
    int chinese;
           
};

void print_s(const void *record){
    const SCORE *r = record;
    printf("%d %s %d %d\n", r->id, r->name, r->math, r->chinese);
}

int main(){

    STACK *st;
    SCORE tmp, *data = NULL;
    int ret, id = 3;
    char *del_name = "stu6";

    st = stack_create(sizeof(SCORE));
    if(st == NULL){
        exit(-1);
    }


    for(int i = 0; i < 7; i++){
        tmp.id = i;
        snprintf(tmp.name, NAMESIZE, "stu%d", i);
        tmp.math = rand() % 100;
        tmp.chinese = rand() % 100;

        ret = stack_push(st, &tmp);
        if(ret != 0){
            exit(-1);
        }
    }

    while(1){
        ret = stack_pop(st, &tmp);
        if(ret != 0){
            break;
        }
        print_s(&tmp);
    }


    stack_destroy(st);

    return 0;
}

本人亲测有效

测试通过qwq

转载：https://blog.csdn.net/baidu_39049318/article/details/105738224