栈是插入和删除操作限制在一端（即栈顶）的表，是先进后出模型。
入栈：新元素的插入，成为新的栈顶元素；
出栈：栈顶元素的删除，栈顶指向相邻元素。
数制转换
括号匹配的检验
表达式求值
迷宫求解
行编辑程序
二叉树的遍历
1. fata.h
#include <stdio.h>
#include <stdlib.h>
#define Error( Str ) FatalError( Str )
#define FatalError( Str ) fprintf( stderr, "%s\n", Str ),system("puase"),getchar(),exit( 1 )
2. stacklist.h
#ifndef _Stack_h typedef int ElementType; struct Node; typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty(Stack S); Stack CreateStack(void); void DisposeStack(Stack S); void MakeEmpty(Stack S); void Push(ElementType X, Stack S); ElementType Top(Stack S); void Pop(Stack S); #endif
3. stack.h
#include "stack.h"
#include "fatal.h"
#include <stdio.h>
struct Node
{
ElementType Element;
PtrToNode Next;
};
int IsEmpty(Stack S)
{
return S->Next == NULL;
}
void Push(ElementType X, Stack S)
{
PtrToNode TmpCell;
TmpCell = malloc(sizeof(struct Node));
if (TmpCell == NULL)
{
Error("out of space!!!");
}
else
{
TmpCell->Element = X;
TmpCell->Next = S->Next;
S->Next = TmpCell;
}
}
void Pop(Stack S)
{
PtrToNode FirstCell;
if (IsEmpty(S))
{
Error("Empty Stack\n");
}
else
{
FirstCell = S->Next;
S->Next = S->Next->Next;
free(FirstCell);
}
}
void MakeEmpty(Stack S)
{
if (S == NULL)
{
Error("Use CreatStack first\n");
}
else
while (!IsEmpty(S))
{
Pop(S);
}
}
Stack CreateStack(void)
{
Stack S;
S = malloc(sizeof(struct Node));
if (S == NULL)
{
FatalError("out of Space");
}
S->Next = NULL;
MakeEmpty(S);
return S;
}
ElementType Top(Stack S)
{
if (!IsEmpty(S))
{
return S->Next->Element;
}
Error("Empty Stack\n");
return 0;
}
void DisposeStack(Stack S)
{
MakeEmpty(S);//only head
free(S);//free head
}
4. teststack.h
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
//#include <Windows.h>
#include <string.h>
#include "stack.h"
#include "fatal.h"
main()
{
Stack S;
int i;
S = CreateStack();
for (i = 0; i < 10; i++)
Push(i, S);
while (!IsEmpty(S))
{
printf("%d\n", Top(S));
Pop(S);
}
DisposeStack(S);
system("pause");
return 0;
}
1. stackarr.h
#include "fatal.h" #include <stdio.h> #define ElementType int #ifndef _Stackarr_H struct StackRecord; typedef struct StackRecord *Stack; int IsEmpty(Stack S); int IsFull(Stack S); Stack CreateStack(int MaxElement); void DisposeStack(Stack S); void MakeEmpty(Stack S); void Push(ElementType X, Stack S); ElementType Top(Stack S); void Pop(Stack S); ElementType TopAndPop(Stack S); #endif
2. stackarr.c
#include "stackarr.h"
#include "fatal.h"
#include <stdio.h>
#define MinStackSize (10)
#define EmptyToS (-1)
struct StackRecord
{
int Capacity;
int TopOfStack;
ElementType *Array;
};
Stack CreateStack(int MaxElement)
{
Stack S;
if (MaxElement <MinStackSize)
{
Error("Stack Size is too small.");
}
S = malloc(sizeof(struct StackRecord));
if (S == NULL)
{
FatalError("out of space!!!");
}
S->Array = malloc(sizeof(ElementType)*MaxElement);
if (S->Array == NULL)
{
FatalError("out of space!!!");
}
S->Capacity = MaxElement;
MakeEmpty(S);
return S;
}
void DisposeStack(Stack S)
{
if (S!=NULL)
{
free(S->Array);
free(S);
}
}
int IsEmpty(Stack S)
{
return S->TopOfStack == EmptyToS;
}
int IsFull(Stack S)
{
return S->TopOfStack == S->Capacity - 1;
}
void MakeEmpty(Stack S)
{
S->TopOfStack = EmptyToS;
}
void Push(ElementType X, Stack S)
{
if (IsFull(S))
{
Error("Full Stack\n");
}
else
S->Array[++S->TopOfStack] = X;
}
ElementType Top(Stack S)
{
if (!IsEmpty(S))
return S->Array[S->TopOfStack];
Error("Empty Stack\n");
return 0;
}
void Pop(Stack S)
{
if (IsEmpty(S))
{
Error("Empty stack\n");
}
else
S->TopOfStack--;
}
ElementType TopAndPop(Stack S)
{
if (!IsEmpty(S))
{
return S->Array[S->TopOfStack--];
}
Error("Empty stack\n");
return 0;
}
3. teststarkarr.c
#include <stdio.h>
#include "stackarr.h"
#include "fatal.h"
void main()
{
Stack S;
int i;
S = CreateStack(11);
for (i = 0; i <= 10; i++)
Push(i, S);
while (!IsEmpty(S))
{
printf("%d\n", Top(S));
Pop(S);
}
DisposeStack(S);
system("pause");
}
原文：http://www.cnblogs.com/my-cat/p/5970859.html