数据结构与算法（四）栈的链式存储

• 接口

#ifndef __STACK_LIST_H__ 
#define __STACK_LIST_H__ 
#include <stdlib.h> 
#include <stdio.h> 
#include <stdbool.h> 
typedef int ElementType; 
typedef struct SNode 
{ 
   ElementType Data; 
   struct SNode*Next; 
}SNode; 
typedef SNode* Stack; 


Stack CreateStack();// 
bool IsEmpty(Stack S);// 
void Push(Stack S, ElementType item);// 
ElementType Pop(Stack S);// 
void Display(Stack S); 
#endif

• 函数实现

#include "StackList.h" 
Stack CreateStack() 
{ 
   Stack temp = (Stack)malloc(sizeof(struct SNode)); 
   temp->Next = NULL; 
   return temp; 
} 
bool IsEmpty(Stack S) 
{ 
   return (S->Next == NULL); 
} 
void Push(Stack S, ElementType item) 
{ 
   Stack temp = (Stack)malloc(sizeof(struct SNode)); 
   temp->Data = item; 
   temp->Next = S->Next; 
   S->Next = temp; 
} 
ElementType Pop(Stack S) 
{ 
   Stack firstCell; 
   ElementType topItem; 
   if (IsEmpty(S)) { 
       return 0; 
   } 
   firstCell = S->Next; 
   S->Next = firstCell->Next; 
   topItem = firstCell->Data; 
   free(firstCell); 
   return topItem; 
} 
void Display(Stack S) 
{ 
   while (!IsEmpty(S)) { 
       printf("%d ", Pop(S)); 
   } 
   printf("\n"); 
}

• 测试函数

int main(int argc, char**argv) 
{ 
   Stack myStack = CreateStack(); 
   for (int i = 0; i < 10; i++) { 
       Push(myStack, i); 
   } 
   Display(myStack); 
   return 0; 
}

• 测试结果