王道408用数组，链表以及双向链表实现栈、队列

我在电脑上敲了一遍，又在纸上模拟了一遍

下面记录在电脑上敲的:

一、用数组实现栈

#include #include <string.h>#define MaxSize 50typedef struct{    int data[MaxSize];    int top;}stack;void InitStack(stack & S){    S.top = -1;    S.data[0] = 5;    memset(S.data,0,sizeof(S.data));    // printf("%x\n%x\n\n\n",S.data,&S.data);          // 这俩地址指向了同一个位置a}bool IsEmpty(stack S){    if(S.top == -1)        return 1;    return 0;}bool IsFull(stack S){    if(S.top == MaxSize-1)        return 1;    return 0;}bool Push(stack &S,int x){    if(IsFull(S))        return 0;    S.data[++S.top] =  x;    return 1;}bool Pop(stack &S,int &x){    if(IsEmpty(S))        return 0;    x = S.data[S.top--];    return 1;}int main(){    stack sk;    InitStack(sk);    Push(sk,1);    Push(sk,2);    Push(sk,3);    Push(sk,4);    Push(sk,5);    int ans;    for(int i=0;i<=7;i++){        if(Pop(sk,ans)){            printf("%d\n",ans);        }        else{            puts("Empty Stack!!!");        }    }    return 0;}

二、用单链表实现栈

#include #include #include typedef struct SNode{    int data;    struct SNode *next;} SNode,*Listack;void InitStack(Listack &S){  // 定义头节点    S = (Listack )malloc(sizeof(SNode));    S->next = NULL;    return ;}bool IsStackEmpty(Listack S){    if(S->next == NULL){        return 1;    }    return 0;}bool StackPush(Listack &S,int x){    SNode * p = (SNode *)malloc(sizeof(SNode));    p->data = x;    p->next = S->next;    S->next = p;    return 1;}bool StackPop(Listack &S,int &x){    if(IsStackEmpty(S)){        return 0;    }    SNode * p = S->next;    x = p->data;    S->next = p->next;    free(p);    return 1;}int main(){    SNode * sn;    InitStack(sn);    StackPush(sn,1);    StackPush(sn,2);    StackPush(sn,3);    StackPush(sn,4);    StackPush(sn,5);    int ans;    for(int i = 0;i<=7;i++){        if(StackPop(sn,ans)){            printf("%d\n",ans);        }        else{            printf("EmptyStack!!!\n");        }    }    return 0;}

三、用双链表实现栈

#include #include typedef struct _DbNode{    int data;    struct _DbNode * next;    struct _DbNode * last;}DbNode,*PDNode;typedef struct _LiDbNode{           // 定义这个结构体只是为了管理收尾两个节点，中间的节点还是全部由DbNode构成的    DbNode * head;    DbNode * rear;}LiDbNode,*PDbStack;void InitDbNode(PDbStack &S){    DbNode * p = (DbNode *)malloc(sizeof(DbNode));    S = (LiDbNode *)malloc(sizeof(LiDbNode));    p->last = p->next = NULL;    S->head = S->rear = p;}bool DbStackPush(PDbStack  &S,int x){    DbNode * p = (DbNode *)malloc(sizeof(DbNode));    p->data = x;    p->next = NULL;    p->last = S->rear;    S->rear->next = p;    S->rear = p;    return 1;}bool IsDbStackEmpty(PDbStack S){    if(S->head == S->rear){        return 1;    }    return 0;}bool DbStackPop(PDbStack &S,int &x){    if(IsDbStackEmpty(S)){       return 0;    }        DbNode * p = S->rear;           // 注意这里 S->rear指向的就是尾节点，而在后续用单链表实现Queue的时候，S-front指向的是头节点，也就是说S->front->next才是指向的节点，这是一个小坑，注意!!    p->last->next = NULL;    S->rear = p->last;    x = p->data;    free(p);        return 1;}int main(){    PDbStack sn;    InitDbNode(sn);    DbStackPush(sn,1);    DbStackPush(sn,2);    DbStackPush(sn,3);    DbStackPush(sn,4);    DbStackPush(sn,5);    int ans;    for(int i = 0;i<=7;i++){        if(DbStackPop(sn,ans)){            printf("%d\n",ans);        }        else{            printf("EmptyStack!!!\n");        }    }    return 0;}

四、用数组实现队列

#include #include <string.h>#define MaxSize 50typedef struct{    int data[MaxSize];    int head,rear;}queue;void InitQueue(queue &q){    memset(q.data,0,sizeof(q.data));    q.head = q.rear = 0;}bool IsEmpty(queue q){    if(q.rear == q.head)        return 1;    return 0;}bool IsFull(queue q){    if((q.rear + 1) % MaxSize == q.head)        return 1;    return 0;}bool EnPush(queue &q,int x){    if(IsFull(q)) return 0;    q.data[q.rear] = x;             // 这里为了区分队列是否满/空，我们牺牲了一个存储单元，使rear永远指向最后一个数据的下一位置，这也是不用++q.rear的原因,小坑...    q.rear = (q.rear+1) % MaxSize;    return 1;}bool DePop(queue &q,int &x){    if(IsEmpty(q)) return 0;    x = q.data[q.head];             // head 一直指向最开始的数据单元    q.head = (q.head + 1) % MaxSize;    return 1;}int main(){    queue qe;    InitQueue(qe);    for(int i = 0;i<=70;i++){        if(!EnPush(qe,i))            printf("%d -- ",i);            puts("Full Queue!!!");    }        int ans;    for(int i=0;i<=70;i++){        if(DePop(qe,ans)){            printf("%d\n",ans);        }        else{            printf("%d -- ",i);            puts("Empty Queue!!!");        }    }    return 0;}

五、用单链表实现队列

#include #include typedef struct _QNode{    int data;    struct _QNode * next;    }QNode,*pQNode;typedef struct _LinkQueue{    QNode* rear;    QNode* front;}LinkQueue,*pLinkQueue;void InitQueue(pLinkQueue &Q){  // 初始化队列，创建头节点，使队头指向头节点，队尾指向头节点//    Q = (LinkQueue *)malloc(sizeof(LinkQueue));    QNode *q = (QNode *)malloc(sizeof(QNode));    q->next = NULL;    Q->rear = Q->front = q;}bool IsEmpty(pLinkQueue Q){    if(Q->front == Q->rear) return 1;    return 0;}bool EnPush(pLinkQueue &Q,int x){    QNode *q = (QNode *)malloc(sizeof(QNode));    q->next = NULL;    q->data = x;    Q->rear->next = q;    Q->rear = q;    return 1;}bool DePop(pLinkQueue &Q,int &x){    if(IsEmpty(Q)) return 0;    QNode *q = Q->front->next;              //要注意这里和前面用双向链表实现栈的时候不太一样，当时S->rear指的是最后一个节点，而这里的S->front指的是头节点，而不是第一个节点，我们需要用S->front->next来获得第一个节点，切记切记!!!    x = q->data;    Q->front->next = q->next;    if(Q->rear == q)                //当原队列中只有一个节点时，删除后，让尾指针重新指向头结点!!//        Q->rear = Q->front;            free(q);    return 1; }int main(){             pLinkQueue qe;    InitQueue(qe);    EnPush(qe,1);    EnPush(qe,2);    EnPush(qe,3);    EnPush(qe,4);    EnPush(qe,5);    int ans;    for(int i=0;i<=7;i++){        if(DePop(qe,ans)){            printf("%d\n",ans);        }        else{            puts("Empty Queue!!!");        }    }    return 0;    }