数据结构：栈（C语言实现）

栈的定义

栈是一种特殊的线性表，它的逻辑结构和线性表相同，只是运算规则与线性表相比有了更多的限制，其实之后会接触的一种数据结构——队列也是特殊的线性表，但队列不在本篇讨论的范围了。栈与队列都可以称作运算受限的线性表

具体来讲它的定义，栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，而距离栈顶最远的（即另一个固定端）称为栈底，当表中没有元素时成为空栈。因为只能在一端插入或删除，所以我们可以说栈是按“后进先出”的规则进行操作，称为后进先出的线性表，简称LIFO表。栈的插入操作我们称为进栈，又叫做入栈；栈的删除操作我们称为出栈，又叫做弹栈。

如上图，栈像极了一个容器，我们可以往里面放东西，而要拿东西出来的时候，我们只能拿位于容器上面的东西。那按照这种说法，是不是最先进栈的元素一定最后一个出栈呢？答案是非也。

我们举个例子，现有三个元素1、2、3，要将这三个元素依次进栈，出栈的顺序有几种呢。

• 1、2、3依次进栈，出栈的顺序就是3、2、1。
• 1进，2进，2出，1出，3进，3出，出栈的顺序是2、1、3。
• 1进，1出，2进，3进，3出，2出，出栈的顺序是1、3、2。
• 1进，2进，2出，3进，3出，1出，出栈的顺序是2、1、3。
• 1进，1出，2进，2出，3进，3出，出栈的顺序是1、2、3。

上述情况可知，元素出栈的形式是多变的。

栈的基本操作

我们在上面说过：栈是一种特殊的线性表，那么也和线性表一样分为两类：顺序栈、链栈（下图）。

定义

顺序栈我们可以用数组来表示，通常来说，0 下标端设为栈底，并且用一个栈顶指针top来表示，比如当栈内有 5 个元素，那么栈顶元素的下标就是 4，即 top = 4 ，由此推出，若栈此时为空栈时，栈顶指针 top = -1 ，入栈时，栈顶指针加 1。

// define Status
typedef enum Status {
	ERROR = 0, SUCCESS = 1
} Status;

// define element type
typedef int ElemType;

// define struct of stack
typedef struct SqStack {
	ElemType *elem;
	int top;
	int size;			//定义栈的大小
} SqStack;
           

链栈和链表就差不多了，与顺序栈相比，同样是需要一个栈顶指针指向栈顶，进栈和出栈采用类似链表中的插入、删除接口来完成，值得注意的是，栈的主要运算是在栈顶插入、删除，显然在链表的头部作栈顶最方便（插入采用前插法）。

// define Status
typedef enum Status {
    ERROR = 0, SUCCESS = 1
} Status;

// define element type
typedef int ElemType;

// define struct of stack
typedef struct StackNode
{
	ElemType data;
	struct StackNode *next;
}StackNode, *LinkStackPtr;

//define pointer of stack
typedef struct LinkStack{
	LinkStackPtr top;
	int	count;
}LinkStack;
           

初始化

链栈中我们为 s->top 申请了内存空间，而这个空间是指针的空间，不是栈的空间， s->top 只是一个指针，s-> top->next才是 s->top指针所指的栈顶元素。

//基于数组的顺序栈
Status initStack(SqStack *s,int sizes)
{
	s->elem = (ElemType*)malloc(sizes * sizeof(ElemType));
	if (!s->elem)
		return ERROR;
	s->top = -1;
	s->size = sizes;
	return SUCCESS;
}

//基于链表的链栈
Status initLStack(LinkStack *s)
{
	s->top = (LinkStackPtr)malloc(sizeof(StackNode));
	if (!s->top)
		return ERROR;
	s->count = 0;
	return SUCCESS;
}
           

判断栈是否为空

这个接口其实特别简单，要判断栈是否为空，顺序栈就是看 s->top 是不是等于 -1；链栈就是看 s->count 是不是等于 0（也可以看 s->top->next 是否为NULL）

//基于数组的顺序栈
Status isEmptyStack(SqStack *s)  
{
	return s->top == -1;
}

//基于链表的链栈
Status isEmptyLStack(LinkStack *s)  
{
	return s->count == 0;
}
           

读栈顶元素

当然是要瞧瞧栈顶指针指的那个位置啦

//基于数组的顺序栈
Status getTopStack(SqStack *s,ElemType *e) 
{
	if (s->top == -1)
		return ERROR;
	*e = s->elem[s->top];
	return SUCCESS;
}

//基于链表的链栈
tatus getTopLStack(LinkStack *s,ElemType *e) 
{
	if(s->count == 0 || !s->top)
		return ERROR;
	*e = s->top->next->data;
	return SUCCESS;
}
           

清空

这里的清空并不是销毁，清空只是把所有元素出栈而已，栈还是可以继续使用的。

//基于数组的顺序栈
Status clearStack(SqStack *s) 
{
	if (!s)
		return ERROR;
	s->top = -1;
	return SUCCESS;
}

//基于链表的链栈
Status clearLStack(LinkStack *s) 
{
	LinkStackPtr ptem, p = s->top->next;			//p指向栈顶元素
	if (!s->top)
		return ERROR;
	while (p){						//这里也可以循环调用出栈接口
		ptem = p->next;
		free(p);					//free栈顶元素
		p = ptem;
	}
	s->count = 0;					//计数器归零
	return SUCCESS;
}
           

销毁

要把我们申请的内存空间全部free

//基于数组的顺序栈
Status destroyStack(SqStack *s)
{
	if (!s)
		return ERROR;
	free(s->elem);
	return SUCCESS;
}

//基于链表的链栈
Status destroyLStack(LinkStack *s) 
{
	LinkStackPtr ptem, p = s->top->next;
	if (!s->top)
		return ERROR;
	while (s->count != 0){			//这里也可以调用清空接口
		ptem = p->next;
		free(p);
		s->top->next = ptem;
		s->count--;
	}
	free(s->top);
	return SUCCESS;
}
           

栈长

栈的长度直接看 s->top 和 s->count 的值就可以啦

//基于数组的顺序栈
Status stackLength(SqStack *s,int *length)  
{
	if (!s)
		return ERROR;
	*length = s->top + 1;
	return SUCCESS;
}

//基于链表的链栈
Status LStackLength(LinkStack *s,int *length)
{
	if (!s->top)
		return ERROR;
	*length = s->count;
	return SUCCESS;
}
           

进栈

因为顺序栈需要我们事先定义栈的大小，所以在进栈操作前，要先判断栈是否已满；而链栈在某个层面上说是没有大小限制的，可以随便进栈，除非内存满了。

//基于数组的顺序栈
Status pushStack(SqStack *s,ElemType data) 
{
	if (!s || s->top == s->size - 1)		//判断栈是否已满
		return ERROR;
	s->top++;
	s->elem[s->top] = data;
	return SUCCESS;
}

//基于链表的链栈
Status pushLStack(LinkStack *s,ElemType data)
{
	StackNode *p;
	if(!s->top)
		return ERROR;
	p = (StackNode*)malloc(sizeof(StackNode));
	p->data = data;
	p->next = s->top->next;
	s->top->next = p;
	s->count++;
	return SUCCESS;
}
           

出栈

出栈也要判断一下栈是否已空

//基于数组的顺序栈
Status popStack(SqStack *s)  
{
	if (!s || s->top == -1)		//这里也可以调用 “判断栈是否为空” 接口
		return ERROR;
	s->top--;
	return SUCCESS;
}

//基于链表的链栈
Status popLStack(LinkStack *s, ElemType *data)
{
	LinkStackPtr ptem, p = s->top->next;
	if(!s->top || s->count == 0)			//这里也可以调用 “判断栈是否为空” 接口
		return ERROR;
	*data = p->data;						//出栈的元素存储到 data
	ptem = p->next;
	free(p);
	s->top->next = ptem;
	s->count--;
	return SUCCESS;
}
           

参考：

算法与数据结构（C语言版） 主编·邓玉洁