數(shù)組和鏈表是兩種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)

數(shù)組和鏈表是兩種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，也是構(gòu)成很多復(fù)雜數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。本程序利用數(shù)組和鏈表實(shí)現(xiàn)堆棧。#ifndef_STACK_H#define_STACK_H#ifndefBOOL#defineBOOLint#endiftypedefcharItem;struct_Stack;typedefstruct_StackStack;typedefStack*pStack;pStackStack_Init(intnMax);voidStack_Destroy(pStackpSt);voidStack_Push(pStackpSt,Itemelem);ItemStack_Pop(pStackpSt);intStack_Size(pStackpSt);BOOLStack_IsEmpty(pStackpSt);BOOLStack_IsFull(pStackpSt);#endif#include<stdio.h>#include<stdlib.h>#include〃STACK.h〃staticError(char*msg)(printf(〃Error:%s\n〃，msg);}struct_Stack(Item*elem;inttop;intnMax;};pStackStack_Init(intnMax)(pStackpSt二malloc(sizeof(*pSt));pSt->elem=malloc(nMax*sizeof(*pSt->elem));pSt->top=-1;pSt->nMax=nMax-1;returnpSt;}voidStack_Destroy(pStackpSt)(free(pSt->elem);pSt->elem=NULL;free(pSt);pSt=NULL;}voidStack_Push(pStackpSt,Itemelem)(if(Stack_IsFull(pSt))(Error("StackIsFull");exit(-1);}pSt->elem[++pSt->top]=elem;}ItemStack_Pop(pStackpSt)(if(Stack_IsEmpty(pSt))(Error("StackIsEmpty");exit(-1);}returnpSt->elem[pSt->top--];}intStack_Size(pStackpStk)(returnpStk->top+1;}BOOLStack_IsEmpty(pStackpSt)(returnpSt->top==-1;}BOOLStack_IsFull(pStackpSt)(returnpSt->top==pSt->nMax;}typedefstruct_StackElem(Itemelem;struct_StackElem*next;}StackElem;typedefStackElem*link;typedefstruct_Stack(linkhead;intnMax;}Stack;pStackStack_Init(intnMax)(pStackpStk二malloc(sizeof(*pStk));pStk->head=NULL;pStk->nMax=nMax;returnpStk;}voidStack_Destroy(pStackpStk)(while(!Stack_IsEmpty(pStk))(Stack_Pop(pStk);}free(pStk);}voidStack_Push(pStackpStk,Itemelem)(linkln;if(Stack_IsFull(pStk))(Error("StackIsFull");exit(-1);}ln=malloc(sizeof(*ln));ln->elem=elem;ln->next=pStk->head;pStk->head=ln;}ItemStack_Pop(pStackpStk)(linkIn;Itemelem;if(Stack_IsEmpty(pStk))(Error("StackIsEmpty");exit(-1);}ln=pStk->head;elem=ln->elem;pStk->head=pStk->head->next;free(ln);returnelem;}intStack_Size(pStackpStk)(intcnt;linkln;for(cnt=0,ln=pStk->head;ln!=NULL;ln=ln->next,cnt++);returncnt;}BOOLStack_IsEmpty(pStackpStk)(returnpStk->head==NULL;}BOOLStack_IsFull(pStackpStk)(returnStack_Size(pStk)==pStk->nMax;}#include<stdio.h>#include<string.h>#include〃STACK.h〃intmain()(pStackpStk=Stack_Init(20);chari='z';while(!Stack_IsFull(pStk))(Stack_Push(pStk,i--);}printf(〃Stack