什么是栈？
栈（stack）又名堆栈，它是一种运算受限的线性表。
其限制是仅允许在表的一端进行插入和删除运算。
这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈，
它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，
使其相邻的元素成为新的栈顶元素。
用双向通用链表来封装一个栈
由上可知道，栈只需要使用双向链表的一部分功能，其他功能
都可以直接不用就好了。
基本思路
定义一个栈的结构体，结构体里面只需要定义一个指向通用双端
链表的指针就好，栈的其他操作，只需要调用双向链表的一些函数
就好了。
在封装前就必须要提前写好通用双端链表的声明和操作
dlist.h
dlist.c
栈的声明文件
源代码请看stack.h1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#ifndef _STACK_H_
#define _STACK_H_
#include "dlist.h"
#include "tools.h"
typedef struct Stack{
Dlist *dlist; //用双端链表的控制信息去模仿栈的控制信息
}Stack;
//关于栈的接口
Stack *init_stack(void) ; //初始化栈
void destroy_stack(Stack **stack) ; //销毁栈
Boolean is_empty(Stack *stack) ; //判空
void push(Stack *stack, void *value) ; //入栈
Boolean pop(Stack *stack) ; //出栈
Boolean get_top(Stack *stack, void **value); //得到栈顶元素
int get_count(Stack *stack) ; //得到栈的个数
#endif
栈的各个函数的实现
源代码请看stack.c1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80#include "stack.h"
//栈的接口实现
Stack *init_stack(void) //初始化栈
{
// stackoverflow
//
//
// sourceforge
//
// -----
// --- ---
// --- ---
// ---
// | ---|
// | ---|
// | ---|
// | ---|
// |————|
Stack *stack = (Stack *)Malloc(sizeof(Stack));
stack->dlist = (Dlist *)malloc(sizeof(Dlist));
if(stack->dlist == NULL){
free(stack);
fprintf(stderr, "the memory is full!\n");
exit(1);
}
return stack;
}
void destroy_stack(Stack **stack) //销毁栈
{
if(stack == NULL || *stack == NULL){
return ;
}
//先释放stack里的dlist，再释放stack
destroy_dlist(&((*stack)->dlist));
free(*stack);
*stack = NULL;
}
Boolean is_empty(Stack *stack) //判空
{
return stack->dlist->count == ZERO;
}
void push(Stack *stack, void *value) //入栈
{
if(stack == NULL || value == NULL){
return ;
}
push_front(stack->dlist, value); //入栈操作封装了双端链表的头部插入
}
Boolean pop(Stack *stack) //出栈
{
if(stack == NULL || is_empty(stack)){
return FALSE;
}
return pop_front(stack->dlist);
}
Boolean get_top(Stack *stack, void **value) //得到栈顶元素
{
if(stack == NULL || is_empty(stack)){
return FALSE;
}
if(value != NULL){
get_front(stack->dlist, value);
}
return TRUE;
}
int get_count(Stack *stack) //得到栈的个数
{
if(stack == NULL){
return -1;
}
return get_dlist_count(stack->dlist);
}