栈有时又叫做LIFO（后进先出表）。
栈的链表实现
#include<stdio.h>
#include<stdlib.h>
struct Node;
typedef struct Node *PrtToNode;
typedef PrtToNode Stack;
struct Node{
int Element;
PrtToNode Next;
};
void MakeEmpty(Stack S);
void Pop(Stack S);
//测试栈是否空栈的例程--链表实现
int IsEmpty(Stack S){
return S->Next==NULL;
}
//创建一个空栈的例程--链表实现
Stack CreateStack(){
Stack S;
S=malloc(sizeof(struct Node));
if(S==NULL)
printf("Out of space!!!");
S->Next=NULL;
MakeEmpty(S);
return S;
}
void MakeEmpty(Stack S){
if(S==NULL)
printf("Must use CreateStack first");
else
while (!IsEmpty(S)) {
Pop(S);
}
}
//Push进栈的例程--链表实现
void Push(int X,Stack S){
PrtToNode TmpCell;
TmpCell=malloc(sizeof(struct Node));
if(TmpCell==NULL)
printf("Out of space!!!");
else{
TmpCell->Element=X;
TmpCell->Next=S->Next;
S->Next=TmpCell;
}
}
//返回栈顶元素的例程--链表实现
int Top(Stack S){
if(!IsEmpty(S))
return S->Next->Element;
printf("Empty stack");
return 0;
}
//从栈弹出元素的例程--链表实现
void Pop(Stack S){
PrtToNode FirstCell;
if(IsEmpty(S))
printf("Empty Stack");
else{
FirstCell=S->Next;
S->Next=S->Next->Next;
free(FirstCell);
}
}
int main(){
return 0;
}
栈的数组实现
这种策略的惟一潜在危害是我们需要声明一个数组的大小。
#include<stdio.h>
#include<stdlib.h>
struct StackRecord;
typedef struct StackRecord *Stack;
#define EmptyTOS -1
#define MinStackSize 5
struct StackRecord{
int Capacity;
int TopOfStack;
int *Array;
};
void MakeEmpty(Stack S);
//栈的创建--数组实现
Stack CreateStack(int MaxElements){
Stack S;
if(MaxElementsArray=malloc(sizeof(int)*MaxElements);
if(S->Array==NULL)
printf("Out of space!!!");
S->Capacity=MaxElements;
MakeEmpty(S);
return S;
}
//释放栈的例程--数组实现
void DisposeStack(Stack S){
if(S!=NULL){
free(S->Array);
free(S);
}
}
//检测一个栈是否空栈的例程--数组实现
int IsEmpty(Stack S){
return S->TopOfStack == EmptyTOS;
}
//创建一个空栈的例程--数组实现
void MakeEmpty(Stack S){
S->TopOfStack=EmptyTOS;
}
//检测一个栈是否栈满的例程--数组实现
int IsFull(Stack S){
return S->TopOfStack==S->Capacity-1;
}
//进栈的例程--数组实现
void Push(int X,Stack S){
if(IsFull(S))
printf("Full stack");
else
S->Array[++S->TopOfStack]=X;
}
//将栈顶返回的例程--数组实现
int Top(Stack S){
if(!IsEmpty(S))
return S->Array[S->TopOfStack];
printf("Empty stack");
return 0;
}
//从栈弹出元素的例程--数组实现
void Pop(Stack S){
if(!IsEmpty(S))
printf("Empty stack");
else
S->TopOfStack--;
}
//给出栈顶元素并从栈弹出的例程--数组实现
int TopAndPop(Stack S){
if(!IsEmpty(S))
return S->Array[S->TopOfStack--];
printf("Empty stack");
return 0;
}
int main(){
return 0;
}
