抽象数据类型允许用户在不了解数据类型在计算机中的表示方式的情况下操作数据类型。换句话说，就用户而言，他需要知道的只是可以对数据类型执行的操作。实现数据类型的人可以自由地更改其实现，而不会影响用户。

作为一个线性列表的堆栈，其中的项在一端添加并从同一端删除。这一想法是由一个放在桌子上的“一叠盘子”来说明的，一个放在另一个上面。当需要一个盘子时，它从栈顶取下。当一个盘子被清洗时，它被添加到堆栈的顶部。请注意，如果现在需要一个盘子，那么这个“最新”的盘子就是所取的盘子。堆栈显示“后进先出”属性。

堆栈就是一种抽象数据类型。

栈的应用场景（保存暂时不用的数据或存储地址）：I 软件撤销功能，浏览器后退、前进功能；II 括号匹配、表达式求值；III 数制转换；IV 函数调用、递归调用；V 辅助其它数据结构，如二叉树遍历；VI 迷宫求解；

堆栈可以用链表实现，也可以用数组实现：

1 用结构体来定义栈（当然类是一种更好的抽象数据类型）

typedef struct {int top;//记录数组下标位置int ST[MaxStack];} StackType, *Stack;

2 栈初始化

Stack initStack() {Stack sp = (Stack) malloc(sizeof(StackType));sp -> top = -1;return sp;}

3 用初始来定义一个栈变量

Stack S = initStack();

4 判断栈是否为空

int empty(Stack S) {return (S -> top == -1);}

5 在栈顶增加元素

void push(Stack S, int n) {if (S -> top == MaxStack - 1) {printf("\nStack Overflow\n");exit(1);}++(S -> top);//下标移动S -> ST[S -> top] = n;}

如做以下操作：

push(S,3);push(S,36);push(S,15);push(S,52);push(S,23);

6 在栈顶删除元素

int pop(Stack S) {if (empty(S)) return RogueValue; //a symbolic constantint hold = S -> ST[S -> top];--(S -> top);//下标移动return hold;}

完整代码：

#include <stdio.h>#include <stdlib.h>#define RogueValue -9999#define MaxStack 10typedef struct {	int top;	int ST[MaxStack];} StackType, *Stack;Stack initStack();int empty(Stack);void push(Stack, int);int pop(Stack);int main() {	int n;	Stack S = initStack();	printf("Enter some integers, ending with 0\n");	scanf("%d", &n);	while (n != 0) {		push(S, n);		scanf("%d", &n);	}	printf("Numbers in reverse order\n");	while (!empty(S))		printf("%d ", pop(S));	system("pause");	printf("\n");} //end mainStack initStack() {	Stack sp = (Stack) malloc(sizeof(StackType));	sp -> top = -1;	return sp;} //end initStackint empty(Stack S) {	return (S -> top == -1);} //end emptyvoid push(Stack S, int n) {	if (S -> top == MaxStack - 1) {		printf("\nStack Overflow\n");		exit(1);	}	++(S -> top);	S -> ST[S -> top]= n;} //end pushint pop(Stack S) {	if (empty(S)) return RogueValue;	int hold = S -> ST[S -> top];	--(S -> top);	return hold;} //end pop/*Enter some integers, ending with 02 6 9 12 3 0Numbers in reverse order3 12 9 6 2*/

7 也可以用链表来实现

#include <stdio.h>#include <stdlib.h>#define RogueValue -9999typedef struct node {	int num;//节点数据	struct node *next; //节点指针} Node, *NodePtr;typedef struct stackType {	NodePtr top;//栈top指针} StackType, *Stack;Stack initStack();int empty(Stack);void push(Stack, int);int pop(Stack);int main() {	int n;	Stack S = initStack();	printf("Enter some integers, ending with 0\n");	scanf("%d", &n);	while (n != 0) {		push(S, n);		scanf("%d", &n);	}	printf("Numbers in reverse order\n");	while (!empty(S))		printf("%d ", pop(S));	printf("\n");	system("pause");} //end mainStack initStack() {	Stack sp = (Stack) malloc(sizeof(StackType));	sp -> top = NULL;	return sp;}int empty(Stack S) {	return (S -> top == NULL);}void push(Stack S, int n) {	NodePtr np = (NodePtr) malloc(sizeof(Node));	np -> num = n;	np -> next = S -> top;//此时S -> top==NULL	S -> top = np;//新建节点指针做为栈的top指针}int pop(Stack S) {	if (empty(S)) return RogueValue;	int hold = S -> top -> num;	NodePtr temp = S -> top;//暂存，因为top指针要移动	S -> top = S -> top -> next;//栈top指针下（后）移	free(temp);	return hold;}/*Enter some integers, ending with 04 6 8 12 3 0Numbers in reverse order3 12 8 6 4*/

不管是用数组还是链表作为数据容器，关键在于控制top（下标或指针）的移动（增减），以便在最顶点的top加入元素或将top元素弹出并返回。top（下标或指针）的移动（增减）实质上对应内存单元的偏移。

基本数据类型对应一种类型的数据及对这种类型数据的一组操作（表现为操作符）。

函数也同样如此，对应一组数据及对这些数据的操作。

栈是一种操作受限的抽象数据类型，对于数组，并来是可以随机访问和任意增、删的一种复合数据类型，为了模拟实际需要，需要让其操作受限，定义有限的函数限制其仅在顶部增、删并访问。

－End－