以陣列實作堆疊

在學習資料結構時，最重要的一個課題就是堆疊、駐列等結構。以下簡介以陣列實作堆疊的案例:

先簡介一些必要變數與函數:

#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