在學習資料結構時，最重要的一個課題就是堆疊、駐列等結構。以下簡介以陣列實作堆疊的案例:
先簡介一些必要變數與函數:
#define N 100 //堆疊最大容量;
int stack[N]; //宣告stack;
int sp; //堆疊的指標;
StackOverflow()當堆疊已經滿的時候告知使用者"Stack Over flow"，也就是不能再push資料;
StackUnderflow()當堆疊已經空的時候高知使用者"Stack Under flow"，也就是不能再pop資料;
void StackOverflow(){
printf("\nStack Over flow");
}
void StackUnderflow(){
printf("\nStack Under flow");
}
CreateStack()當需要堆疊stack時，讓其指標初始位置定在-1，因為C語言的陣列是從0開始編排;
void CreateStack(){
sp=-1;
}
IsStackEmpty()判斷堆疊stack是否已空;
IsStackFull()判斷堆疊stack是否已滿;
bool IsStackEmpty(){
return (sp==-1);
}
bool IsStackFull(){
return (sp==(N-1));
}
AddStack(int item)將一筆資料item丟入堆疊stack中，過程須判斷stack還有沒有空間;
void AddStack(int item){ //void AddStack(ItemType item){
if(IsStackFull())StackOverflow();
else stack[++sp]=item;
}
DeleteStack()將堆疊stack最上面的一筆資料移除，但實際上只是將stack的指標sp往下移動，在過程中要先判斷stack是否已空，而不能在移動sp;
int DeleteStack(){ //ItemType DeleteStack(){
if(IsStackEmpty()) StackUnderflow();
else return stack[sp--];
}
StackTop()將堆疊stack最上面的值複製出來;
int StackTop(){ //ItemType StackTop(){
if(IsStackEmpty()) StackUnderflow();
else return stack[sp];
}
以下是一個簡單的堆疊範例:
#include
#include
/***************************************
#ifndef _STDBOOL_H
#define _STDBOOL_H
#define bool _Bool
#define true 1
#define false 0
#define __bool_true_false_are_defined 1
#endif
***************************************/
#define N 100 //const int N=100;
int stack[N]; //ItemType stack[N];
int sp;
void StackOverflow(){
printf("\nStack Over flow");
}
void StackUnderflow(){
printf("\nStack Under flow");
}
void CreateStack(){
sp=-1;
}
bool IsStackEmpty(){
return (sp==-1);
}
bool IsStackFull(){
return (sp==(N-1));
}
void AddStack(int item){ //void AddStack(ItemType item){
if(IsStackFull())StackOverflow();
else stack[++sp]=item;
}
int DeleteStack(){ //ItemType DeleteStack(){
if(IsStackEmpty()) StackUnderflow();
else return stack[sp--];
}
int StackTop(){ //ItemType StackTop(){
if(IsStackEmpty()) StackUnderflow();
else return stack[sp];
}
void Status(){
int i;
printf("sp:%d\n", sp);
printf("stack:\n");
for(i=0; i<=sp; i++){
printf("%d\t", i);
}
printf("\n");
for(i=0; i<=sp; i++){
printf("%d\t", stack[i]);
}
}
int main(){
int input, copy;
char ch;
CreateStack();
Status();
do{
printf("\nInput:");
scanf("%d", &input);
AddStack(input);
Status();
printf("\nDo you want to input a number?(y/n):");
ch=_getche();
}while(ch=='y');
do{
printf("\nDo you want to delete a number?(y/n):");
ch=_getche();
if(ch=='y')
DeleteStack();
printf("\n");
Status();
}while(ch=='y');
copy=StackTop();
printf("\ncopy:%d", copy);
getch();
return 0;
}
以下是程式結果:
sp:-1
stack:
Input:33
sp:0
stack:
0
33
Do you want to input a number?(y/n):y
Input:44
sp:1
stack:
0 1
33 44
Do you want to input a number?(y/n):y
Input:55
sp:2
stack:
0 1 2
33 44 55
Do you want to input a number?(y/n):n
Do you want to delete a number?(y/n):y
sp:1
stack:
0 1
33 44
Do you want to delete a number?(y/n):n
sp:1
stack:
0 1
33 44
copy:44
