二. 栈, 队数据结构

Stack

第一种定义(推荐, 可以实现动态分配Stack SIZE)

typedef struct {
  ElemType *base;    //用指针指明stack base;
  int top;    //标记出stack top;
  int stacksize;    //当前已经分配的存储空间, 以元素为单位; 类似于MAXSIZE概念
}SqStack;

• 从第一种定义看出, 求当前stack length可以直接(top-base)/sizeof(ElemType) (不用+1, 因为top指向了下一位);

第二种定义(定死Stack的SIZE)

typedef struct {
  ElemType stack[MAXSIZE];    //直接定义一个数组, 定死了内存
  int top;    //标记出stack top;
} SqStack;

• 从第二种定义, 我们可以看出stack length可以直接top得出(top指向的是空的下一位, 但是stack数组从stack[0]开始, 因为stack-length = top-1-0+1 = top);

/*构造空栈*/
//要顾及到各个struct中的各个参数如base, top, stacksize;
Status InitStack(SqStack *S) {
    S->base = (ElemType *)malloc(SIZE*sizeof(ElemType));
    S->stacksize = SIZE;
    S->top = 0; 
    return 0;
}

/*GetTop*/
//先检查是否为空栈, 不是才可以输出base[top-1];
ElemType GetTop(SqStack *S) {
    if (S->top==0) {printf("GetTop UNDERFLOW\n"); return ERROR;}
    else {return S->base[S->top-1];}
}

/*Pop*/
//先检查是否为空栈, 不是才可以用top--来缩减栈的高度;
Status Pop(SqStack *S) {
    if (S->top==0) {printf("Pop UNDERFLOW\n"); return ERROR;}
    else {S->top--; return 0;}
}

/**/
//先检查是否栈满了, 满了就realloc内存, 然后才可以push e到top原来位置, 然后让top上浮一位;
Status Push (SqStack *S, ElemType e) {
    if (S->top >= SIZE) {
        S->base = (ElemType *)realloc(S->base,(SIZE+INCREMENT)*sizeof(ElemType));
        S->stacksize += INCREMENT;
        if (!S->base) {printf("Push OVERFLOW\n"); exit(OVERFLOW);}
    }
    S->base[S->top] = e;
    S->top++;
    return 0;
}

Queue

typedef struct {
    ElemType *base;  //最好不要写死容量, 以适应不同大小的输入
    int front, rear;
    int length;    //应对队列头减少而尾部到顶的情形, 必须计数num来实现不浪费空间; stack没有这个问题, length直接top值就是了; 
    int queuesize; 
}SqQueue;

/*GetFront*/
//先检查是否length==0, 然后再取base[front]
ElemType GetFront(SqQueue *Q) {
    if (Q->length==0) {
        printf("GetFront UNDERFLOW\n"); return ERROR;
    } else {
        return Q->base[Q->front];
    }
}

//先检查Q是否是空的, 非空才把front往后移动一个位置;
Status DeQueue(SqQueue *Q) {
    if (Q->length==0) {
        printf("DeQueue UNDERFLOW\n"); return ERROR;
    } else {
        Q->front++;
    }
}

//先检查Q是否是满的, 非满的再添加, 别忘了rear, length都要++
Status EnQueue(SqQueue *Q, ElemType e) {
    if (Q->length==SIZE) {
        //动态分配内存
        Q->base = (ElemType *)realloc(Q->base,(SIZE+INCREMENT)*sizeof(ElemType));
        Q->queuesize += INCREMENT;
        if (!Q->base) {printf("EnQueue OVERFLOW\n"); exit(OVERFLOW);}
    }
    Q->base[Q->rear] = e;
    Q->rear++;
    Q->length++;
    printf("rear: %d\n",Q->rear);
    return 0;
}

后记: queue的数据结构定义和stack基本一个套路, 都是采用顺序线性表的定义方式(*elem, length, listsize→stack/queue(数组名就是指针), top/front,rear, length, size (top本身包含了计算length的方法))

DFS和栈, BFS和队列

栈和队列是简单, 使用的数据结构, 运用范围很广.
图算法中最基本的DFS和BFS算法的实现分别依靠栈和队列.
相关算法代码可以参考我的图算法文章.