用C语言实现简单的栈
栈是一种常见的数据结构，主要特点是“后进先出”。以下是用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语言梳理一下，分布在以下10个章节中：
- Linux-C成长之路（一）：Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
- Linux-C成长之路（二）：基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
- Linux-C成长之路（三）：基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
- Linux-C成长之路（四）：运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
- Linux-C成长之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
- Linux-C成长之路（六）：函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
- Linux-C成长之路（七）：数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
- Linux-C成长之路（八）：存储类，动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
- Linux-C成长之路（九）：复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
- Linux-C成长之路（十）：其他高级议题