데이터 구조: 스 택 (링크 로 구현)

/*
 * this file is an implementation of stack with linked list
 * file name: stack.c
 * author: John Woods
 * date: 2015/5/9
 * statement: anyone can use this file for any purpose
 */

#include <stdio.h>
#include <stdlib.h>

#define BOOL int
#define TRUE 1
#define FALSE 0

typedef struct SNode {
    int value;
    struct SNode * next;
}* SNode;

typedef struct Stack {
    int depth;
    SNode top;
}* Stack;

/* operation declaration */
void stackInit(Stack * p_myStack);
void pop(Stack myStack);
void push(Stack myStack);
void stackClear(Stack myStack);
void stackDestroy(Stack * p_myStack);
BOOL isExist(Stack myStack);

/* menu */
void menu();

/* entrance: main function */
int main(void) {
    Stack myStack = NULL;
    int choice;
    char c;
    while(TRUE) {
        menu();
        while(!scanf("%d", &choice)) while('
' != (c=getchar()) && EOF != c);
        switch(choice) {
            case 1:
                stackInit(&myStack);
                break;
            case 2:
                stackClear(myStack);
                break;
            case 3:
                push(myStack);
                break;
            case 4:
                pop(myStack);
                break;
            case 5:
                stackDestroy(&myStack);
                break;
            default:
                exit(EXIT_SUCCESS);
                break;
        }
    }
    return 0;
}

/* menu implementation */
void menu() {
    printf("
\t****************MENU****************
");
    printf("\t*  1.initial stack  2.clear stack  *
");
    printf("\t*  3.push element   4.pop element  *
");
    printf("\t*  5.destroy stack  6.exit         *
");
    printf("\t****************MENU****************
");
    printf("Your choice:");
}

/* operation implementation */
void stackInit(Stack * p_myStack) {
    if(isExist(*p_myStack)) {
        printf("This stack is already exist, cannot initial it!
");
        return;
    }
    if(NULL == (*p_myStack = (Stack)malloc(sizeof(struct Stack)))) {
        printf("Out of memory!
");
        return;
    }
    (*p_myStack)->top = NULL;
    (*p_myStack)->depth = 0;
    printf("Initial successfully!
");
}

void pop(Stack myStack) {
    SNode pNode = NULL;
    int out;
    char c;
    if(!isExist(myStack)) {
        printf("This stack is not exist! Please initial it first!
");
        return;
    }
    if(0 == myStack->depth) {
        printf("This stack is empty! Cannot pop the top value!
");
        return;
    }
    while(TRUE) {
        out = myStack->top->value;
        pNode = myStack->top;
        myStack->top = myStack->top->next;
        myStack->depth--;
        free(pNode);
        pNode = NULL;
        printf("The value has been popped is %d
", out);
        
        if(0 == myStack->depth) {
            printf("This stack is empty now, cannot continue popping!
 ");
            break;
        }

        while('
' != (c=getchar()) && EOF != c);
        printf("Go on?(y/n):");
        if('y' != (c=getchar()) && 'Y' != c) break;
    }
}

void push(Stack myStack) {
    SNode pNode = NULL;
    int value;
    char c;
    if(!isExist(myStack)) {
        printf("This stack is not exist! Please initial it first!
");
        return;
    }
    while(TRUE) {
        if(!(pNode = (SNode)malloc(sizeof(struct SNode)))) {
            printf("Out of memory!
");
            return;
        }
        printf("Please input the value:");
        while(!scanf("%d", &value)) while('
' != (c=getchar()) && EOF != c);
        pNode->value = value;
        pNode->next = myStack->top;
        myStack->top = pNode;
        myStack->depth++;
        pNode = NULL;
        printf("Push successfully!
");
    
        while('
' != (c=getchar()) && EOF != c);
        printf("Go on?(y/n):");
        if('y' != (c=getchar()) && 'Y' != c) break;
    }
}

void stackClear(Stack myStack) {
    if(!isExist(myStack)) {
        printf("This stack is not exist! Please initial it first!
");
        return;
    }
    SNode pNode = NULL;
    while(myStack->top) {
        pNode = myStack->top;
        myStack->top = myStack->top->next;
        free(pNode);
    }
    myStack->top = NULL;
    myStack->depth = 0;
    printf("Clear successfully!
");
}

void stackDestroy(Stack * p_myStack) {
    if(!isExist(*p_myStack)) {
        printf("This stack is not exist! Please initial it first!
");
        return;
    }
    stackClear(*p_myStack);
    free(*p_myStack);
    *p_myStack = NULL;
    printf("Destroy successfully!
");
}

BOOL isExist(Stack myStack) {
    if(NULL == myStack) return FALSE;
    else return TRUE;
}

/* typedef */
typedef struct SName{
    int data;
} * SName;
/*         */
SName temp = (SName)malloc(sizeof(struct SName));
/*    temp        ，             ，          ， stack.c stackInit() stackDestroy()         */