本文主要是介绍数据结构（二）之栈ADT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
栈是只能在一个位置进行插入和删除元素的表，这个位置称为栈顶。由于栈是一个表，因此任何实现表的方法都能实现栈。一种是使用指针，一种是使用数组，其中数组可能是更流行的解决方案，因为指针实现时malloc和free的调用开销是昂贵的，而数组避免了指针的使用，但数组唯一潜在危害是要提前声明一个数组的大小。本文将从分别介绍指针和数组的实现。
1. 先介绍指针实现。具体实现过程跟单链表很像，只不过插入和删除是在栈顶操作。实现栈时可以声明一个表头，方便插入和删除。
#include <stdio.h>
#include <stdlib.h>typedef int ElementType;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;Stack createStack();
void disposeStack(Stack S);
void push(ElementType X, Stack S);
ElementType pop(Stack S);struct Node
{ElementType Element;PtrToNode Next;
};Stack createStack()
{Stack S;S = (Stack)malloc(sizeof(struct Node));if(S == NULL)return NULL;S->Next = NULL;return S;
}void disposeStack(Stack S)
{PtrToNode p;PtrToNode tmp;p = S->Next;free(S);while(p != NULL){tmp = p;p = p->Next;free(tmp);}return;
}void push(ElementType X, Stack S)
{PtrToNode p;p = (PtrToNode)malloc(sizeof(struct Node));if(p == NULL)return;p->Element = X;p->Next = S->Next;S->Next = p;return;
}ElementType pop(Stack S)
{PtrToNode tmp;if(S == NULL || S->Next == NULL)return 0;tmp = S->Next;S->Next = tmp->Next;ElementType X = tmp->Element;free(tmp);return X;
}测试代码：
void printStack(Stack S)
{PtrToNode P;P = S->Next;while(P != NULL){printf("%d", P->Element);P = P->Next;}printf("\n");return;
}int main()
{Stack S;S = createStack();if(S == NULL)return 0;for(int i=0; i<10; ++i){push(i, S);}printStack(S);printf("%d\n", pop(S));printStack(S);push(9, S);printStack(S);disposeStack(S);system("pause");return 0;
}2. 数组实现。定义每个栈有一个变量TopOfStack来表示栈顶位置，对于空栈它是-1。压栈时TopOfStack加1，弹出时TopOfStack减1。一个影响栈的执行效率的问题是错误检测。对空栈的pop和对满栈的push都将超出数组的界限并引起程序崩溃，这在写代码时要特别注意：
#include <stdio.h>
#include <stdlib.h>typedef int ElementType;
typedef struct StackRecord *Stack;Stack createStack(int maxElements);
void disposeStack(Stack S);
void push(ElementType X, Stack S);
ElementType pop(Stack S);#define EmptyTOS (-1)struct StackRecord
{int Capacity;int TopOfStack;ElementType *Array;
};Stack createStack(int maxElements)
{Stack S;S = (Stack)malloc(sizeof(StackRecord));if(S == NULL)return NULL;S->Array = (ElementType *)malloc(maxElements*sizeof(ElementType));if(S->Array == NULL)return NULL;S->Capacity = maxElements; S->TopOfStack = EmptyTOS;return S;
}void disposeStack(Stack S)
{if(S != NULL){free(S->Array);free(S);}return;
}void push(ElementType X, Stack S)
{if(S->TopOfStack+1 >= S->Capacity)return;S->Array[++S->TopOfStack] = X;return;
}ElementType pop(Stack S)
{if(S->TopOfStack == EmptyTOS)return 0;return S->Array[S->TopOfStack--];
}void printStack(Stack S)
{for(int i = S->TopOfStack; i >= 0; --i){printf("%d", S->Array[i]);}printf("\n");return;
}int main()
{Stack S;S = createStack(10);if(S == NULL)return 0;for(int i=0; i<10; ++i){push(i, S);}printStack(S);printf("%d\n", pop(S));printStack(S);push(9, S);push(9, S);printStack(S);disposeStack(S);system("pause");return 0;
}栈有很多应用，在此总结了一下：
（1）平衡符号
（2）后缀表达式。称为后缀式或逆波兰记法
（3）中缀到后缀的转换
（4）函数调用。特别是在递归时用
更详细的介绍可以查阅《数据结构与算法分析（C语言描述）》。
这篇关于数据结构（二）之栈ADT的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
