栈

介绍

栈是一种特殊的表，规定它只能从栈顶插入数据(Push)，也仅仅只能从栈顶取出数据(Pop)，也就是先进后出(FILO)。它在程序设计中非常重要，例如函数的调用使用的就是栈结构。

栈也同样有两种实现，一种是数组实现，另一种是链表实现。

一般来说，大部分情况下使用数组实现。我们只将很少的数据放入栈中。

数组实现

数组实现的好处是时间复杂度底，仅仅操作一个数组，但是我们在最开始定义栈的时候，必须指定一个固定大小，这导致它失去的灵活性。为了防止栈溢出，我们总是定义一个稍微大一点的数组，但是它也造成的空间的浪费。

定义

/*
    栈的数组实现
    相比于链表实现，数组实现更为常用。
    虽然它有缺点，就是数组的大小是固定的，也就意味着栈的大小是固定的，
    所以每次创建栈的时候都要预留一些空间，这样会造成空间的浪费，但是相比于时间开销，这还是划算的。
*/
#define ElementType int
#include <stdio.h>
#include<stdlib.h>
typedef struct StackRecord *PtrToStack;
typedef PtrToStack Stack;

// 栈为空时，栈顶元素的数组下标，这里定义为-1
#define EmptyTOS (-1)
// 规定最小的栈的大小
#define MinStack (5)

int IsEmpty(Stack s);
int IsFull(Stack);
Stack CreateStack(int MaxElements);
void MakeEmpty(Stack);
void DisposeStack(Stack);
ElementType Top(Stack);
void Push(ElementType, Stack);
int Pop(Stack);

struct StackRecord {
    // 栈顶的数组下标，栈为空是，它为-1
    int TopOfStack;
    // 栈的大小，也就是数组的大小
    int Capacity;
    ElementType *Array;
};

函数实现

int
IsEmpty(Stack s) {
    return s->TopOfStack == EmptyTOS;
}

int
IsFull(Stack s) {
    return s->TopOfStack == (s->Capacity-1);
}

Stack
CreateStack(int max) {
    if (max < MinStack) {
        fprintf(stderr, "Stack size is too small.");
        exit(1);
    }
    Stack stack = malloc(sizeof(struct StackRecord));
    stack->Array = malloc(sizeof(ElementType) * max);
    stack->Capacity = max;
    MakeEmpty(stack);
}

void
MakeEmpty(Stack s) {
    s->TopOfStack = EmptyTOS;
}

ElementType
Top(Stack s) {
    if(!IsEmpty(s))
        return s->Array[s->TopOfStack];
    else {
        fprintf(stderr, "Stack is Empty!");
    }
    return 0;
}

void
Push(ElementType X, Stack s) {
    if(!IsFull(s)) {
        s->Array[++s->TopOfStack] = X;
    }
    else {
        fprintf(stderr, "Stack is Full!");
    }
}
// 成功则返回1，否则返回0
int
Pop(Stack s) {
    if (!IsEmpty(s)) {
        s->TopOfStack--;
        return 1;
    } else {
        fprintf(stderr, "Stack is empty!");
        return 0;
    }
}

void
DisposeStack(Stack s) {
    if ( s != NULL ) {
        free(s->Array);
        free(s);
    }
}

链表实现

栈的链表实现与表的链表实现在很大程度上是相同的，它只不过规定了插入和取出的位置只能是栈顶。

/* 栈的链表实现 */
#include<stdio.h>
#include<stdlib.h>
#define ElementType int
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;

Stack CreateStack( void );
int IsEmpty(Stack);
ElementType Top(Stack);
void MakeEmpty(Stack);
void Pop(Stack);
void Push(ElementType, Stack);
ElementType TopAndPop(Stack);


struct Node {
    ElementType Element;
    PtrToNode Next;
};

Stack
CreateStack( void ) {
    Stack stack = (Stack)malloc(sizeof(struct Node));
    if (stack == NULL) {
        fprintf(stderr, "Out Of Space.");
    } else {
        stack->Next = NULL;
        // 这一句貌似是多余的
        MakeEmpty(stack);
        return stack;
    }
}

void
MakeEmpty(Stack s) {
    if (s == NULL)
        fprintf(stderr, "Must use CreateStack first!");
    else
        while ( !IsEmpty(s) )
            Pop(s);
}

int
IsEmpty(Stack s) {
    return s->Next == NULL;
}

ElementType
Top(Stack s) {
    while (!IsEmpty(s)) {
        return s->Next->Element;
    }
    fprintf(stderr, "Stack is Empty.");
    return 0;
}

void
Pop(Stack s) {
    if (!IsEmpty(s)) {
        PtrToNode Cell = s->Next;
        s->Next = s->Next->Next;
        free(Cell);
    } else {
        fprintf(stderr, "Empty Stack!");
    }
}

void
Push(ElementType X, Stack s) {
    PtrToNode TemCell = (PtrToNode)malloc(sizeof(struct Node));
    if (TemCell == NULL) {
        fprintf(stderr, "Out Of Space!");
    } else {
        TemCell->Element = X;
        TemCell->Next = s->Next;
        s->Next = TemCell;
    }
}

ElementType
TopAndPop(Stack s) {
    ElementType X = Top(s);
    Pop(s);
    return X;
}

最后修改于 2021-07-12