首页 > 代码库 > 简单的栈
简单的栈
栈是一种常见的数据结构,主要特点是“后进先出”。以下是用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; }
本文出自 “chhquan” 博客,请务必保留此出处http://chhquan.blog.51cto.com/1346841/1568504
简单的栈
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。