用C语言实现简单的栈

企鹅博客 2019年7月13日23:07:59 发表评论 370 views

栈是一种常见的数据结构,主要特点是“后进先出”。以下是用C语言实现的简单的栈。

头文件 stack.h ,定义栈的结构体和相关的操作:

#ifndef STACK_H
#define STACK_H
 
enum { STACK_OK = 0, STACK_OVERFLOW, STACK_ERROR, };
 
typedef int ElemType;
 
struct stack {
    ElemType *data;
    ElemType *top;
    int capability;
};
 
 
void stack_init(struct stack *st, int capability);
void stack_destroy(struct stack *st);
int stack_push(struct stack *st, ElemType elem);
int stack_pop(struct stack *st);
ElemType stack_top(const struct stack *st);
int stack_size(const struct stack *st);
int stack_capability(const struct stack *st);
int stack_full(const struct stack *st);
int stack_empty(const struct stack *st);
void stack_clear(struct stack *st);
 
#endif

C文件 stack.c,实现stack的相关操作。

#include "stack.h"
#include <assert.h>
#include <stdlib.h>
 
void stack_init(struct stack *st, int capability)
{
    assert(st && capability > 0);
    st->data = (ElemType *)malloc(sizeof(ElemType) * capability);
    assert(st->data);
    st->top = st->data;
    st->capability = capability;
}
 
void stack_destroy(struct stack *st)
{
    assert(st);
    if (st->data)
        free(st->data);
    st->data = 0;
    st->top = 0;
    st->capability = 0;
}
 
int stack_push(struct stack *st, ElemType elem)
{
    assert(st);
    if (stack_full(st))
        return STACK_OVERFLOW;
    *(st->top++) = elem;
    return STACK_OK;
}
 
int stack_pop(struct stack *st)
{
    assert(st);
    if (stack_empty(st))
        return STACK_OVERFLOW;
    st->top--;
    return STACK_OK;
}
 
ElemType stack_top(const struct stack *st)
{
    assert(st);
    if (stack_empty(st))
        return (ElemType)0;
    else
        return *(st->top - 1);
}
 
int stack_size(const struct stack *st)
{
    assert(st);
    return (st->top - st->data);
}
 
int stack_capability(const struct stack *st)
{
    assert(st);
    return st->capability;
}
 
int stack_full(const struct stack *st)
{
    return (stack_size(st) == stack_capability(st));
}
 
int stack_empty(const struct stack *st)
{
    return (stack_size(st) == 0);
}
 
void stack_clear(struct stack *st)
{
    assert(st);
    st->top = st->data;
}

上面在stack.h 中定义了ElemType为int,是简单的数据类型。上面的实现也是针对简单数据库类型的,对于一些稍复杂的数据类型,上面的实现不适用。例如,如果栈元素需要用某个函数来销毁,则stack_clear就不适用了。

实现中也用到了assert,不过我不大喜欢用assert,因为会使程序中止。其实可以用if来作检测而不中止,或是不作检测,靠使用者自行判断。

上面实现也没有用到 STACK_ERROR 这个值。

下面是提供测试的main.c

#include <stdio.h>
#include "stack.h"
 
int main()
{
    struct stack st;
    int i;
    stack_init(&st, 5);
 
    printf("-------------- init stack ----------------\n");
    printf("stack capability: %d\n", stack_capability(&st));
    printf("stack size: %d\n", stack_size(&st));
    printf("stack empty ? %s\n", stack_empty(&st) ? "Y" : "N");
    printf("stack full ? %s\n", stack_full(&st) ? "Y" : "N");
 
    printf("-------------- pushing elements ----------------\n");
    for (i = 0; i < 10; ++i) {
        printf("push %i OK ? %s\n", i,
            (stack_push(&st, i) == STACK_OK ? "Y" : "N"));
        printf("stack size: %d\n", stack_size(&st));
        printf("stack empty ? %s\n", stack_empty(&st) ? "Y" : "N");
        printf("stack full ? %s\n", stack_full(&st) ? "Y" : "N");
    }
 
    printf("-------------- poping elements ----------------\n");
    while (!stack_empty(&st)) {
        printf("top: %d\n", stack_top(&st));
        printf("pop OK? %s\n", stack_pop(&st) == STACK_OK ? "Y" : "N");
        printf("stack size: %d\n", stack_size(&st));
        printf("stack empty ? %s\n", stack_empty(&st) ? "Y" : "N");
        printf("stack full ? %s\n", stack_full(&st) ? "Y" : "N");
    }
 
    printf("-------------- clear stack ----------------\n");
    stack_clear(&st);
    printf("stack capability: %d\n", stack_capability(&st));
    printf("stack size: %d\n", stack_size(&st));
    printf("stack empty ? %s\n", stack_empty(&st) ? "Y" : "N");
    printf("stack full ? %s\n", stack_full(&st) ? "Y" : "N");
 
    printf("-------------- destroy stack --------------\n");
    stack_destroy(&st);
 
    return 0;
}

C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码 http://www.linuxidc.com/Linux/2014-05/101227.htm

读C++ Primer 之构造函数陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm

读C++ Primer 之智能指针 http://www.linuxidc.com/Linux/2011-08/40177.htm

读C++ Primer 之句柄类 http://www.linuxidc.com/Linux/2011-08/40175.htm

  1. Linux-C成长之路(一):Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
  2. Linux-C成长之路(二):基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
  3. Linux-C成长之路(三):基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
  4. Linux-C成长之路(四):运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
  5. Linux-C成长之路(五):控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
  6. Linux-C成长之路(六):函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
  7. Linux-C成长之路(七):数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
  8. Linux-C成长之路(八):存储类,动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
  9. Linux-C成长之路(九):复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
  10. Linux-C成长之路(十):其他高级议题

除非注明,否则均为@企鹅博客原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.qieseo.com/180578.html

weinxin
欢迎加入中国SEO站长博客之家
本站的所有资源都会上传分享到博客之家,希望大家互相学习交流进步。
企鹅博客

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: