堆栈

——主要参考了中国大学MOOC数据结构课程的内容
类型名称: 堆栈（Stack）
数据对象集：一个有0个或多个元素的有穷线性表。
操作集：长度为MaxSize的堆栈S∈Stack，堆栈元素item∈ElementType

1. Stack CreateStack( int MaxSize )： 生成空堆栈，其最大长度为MaxSize；
2. int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满；
3. void Push( Stack S, ElementType item )：将元素item压入堆栈；
4. int IsEmpty ( Stack S )：判断堆栈S是否为空；
5. ElementType Pop( Stack S )：删除并返回栈顶元素；

用数组加一个指示变量的写法如下：

#include<stdio.h>
#define MAX 100

typedef struct SNode *Stack;

struct SNode {
    int top;
    int array[MAX];
};

Stack CreateStack() {
    Stack stack = (Stack)malloc(sizeof(struct SNode));
    stack->top = -1;
    return stack;
}

int Push(Stack stack,int data) {
    if(stack->top<MAX-1) {
        stack->array[++stack->top] = data;
    } else {
        printf("栈满了\n");
    }
}

int Pop(Stack stack) {
    if(stack->top>=0) {
        return stack->array[stack->top--];  
    } else {
        printf("栈空了\n");
        return -1;
    }
}

int main() {
    Stack stack = CreateStack();
    int i;
    for(i=0; i<10; i++) {
        Push(stack,i);
    }
    for(i=0; i<10; i++) {
        printf("%d ",Pop(stack));
    }
    free(stack);
    return 0;
}

值得注意的是，Pop的写法，这种写法我一开始没有想到，但是还是很容易想到。在学了面向对象后，想访问top，老是想直接用top，而不是stack->top，这一点让我更加理解面向对象的好处。用单向链表实现的代码如下所示：

#include<stdio.h>

typedef struct SNode *Stack;
struct SNode {
    int data;
    struct SNode *next;
} ;

Stack createStack(int data){
    Stack stack = (Stack)malloc(sizeof(struct SNode));
    stack->data = data;
    stack->next = NULL;
}

void Push(Stack stack,int data){
    Stack newStack = createStack(data);
    Stack temp = stack->next;
    stack->next = newStack;
    newStack->next = temp;
}

int Pop(Stack stack){
    if((stack)->next!=NULL){
        Stack deleteStack = stack->next;
        stack->next = deleteStack->next;
        int data = deleteStack->data;
        free(deleteStack);
        return data;
    }else{
        printf("栈空了\n");
        return -1;
    }
}

int main(){
    Stack stack = createStack(-1);
    int i;
    for(i=0; i<10; i++) {
        Push(stack,i);
    }
    for(i=0; i<11; i++) {
        printf("%d ",Pop(stack));
    }
    free(stack);    
    return 0;
}

这里面有一个技巧值得注意，就是在编写堆栈的时候，设置一个头结点可以使得代码简单一点，也更好理解其中的思想。