資料結構-連結清單實作隊列和棧

隊列

• 函數:

1. 創造隊列
2. 增加隊員(尾進)…注意空加隊員和非空加隊員
3. 隊列是否空
4. 出隊(頭出)…注意一個隊員時的出隊
5. 列印隊列
6. 得到隊頭資料
7. 清空隊列
8. 銷毀隊列

• 出隊的人再入隊實作循環,保持人數不變

#include <stdio.h>
#include <stdlib.h>
typedef struct node{

    int data;
    struct node *next;

}NODE;
typedef struct queue{

    NODE *head;
    NODE *rear;

}QUEUE;

QUEUE* createQueue (){

    QUEUE *queue = (QUEUE *)malloc(sizeof(QUEUE));
    if (queue == NULL){
        exit(0);
    }

    queue->head = NULL;
    queue->rear = NULL;


    return queue;
}
int isEmptyQueue(QUEUE *queue){

    if (queue->head == NULL && queue->rear == NULL){
        return 1;
    }
    return 0;
}

void addQueue(QUEUE *queue, int data){

    NODE *pnew= (NODE *)malloc(sizeof(NODE));
    if (pnew == NULL){
        exit(0);
    }
    pnew->data = data;
    pnew->next = NULL;

    if(isEmptyQueue(queue)){

        queue->head = pnew;
        queue->rear = pnew;
    }
    else {
        queue->rear->next = pnew;
        queue->rear = pnew;
    }
}

void delQueue(QUEUE *queue){
    NODE *p;
    if(!isEmptyQueue(queue)){
        if (queue->head == queue->rear){
            queue->rear = NULL;
        }
        p = queue->head;
        queue->head = p->next;
        free(p);
    }

}
void displayQueue(QUEUE *queue){

    if(!isEmptyQueue(queue)){

        NODE *p = queue->head;
        while(p != NULL){

            printf("%d ", p->data);
            p = p->next;
        }
    }

}
int getHeadQueue(QUEUE *queue){

    if (!isEmptyQueue(queue)){
        return queue->head->data;
    }
    return -9999;
}
void clrQueue(QUEUE *queue){

    while (!isEmptyQueue(queue)){
        delQueue(queue);
    }

}
void destryQueue(QUEUE **queue){

    clrQueue(*queue);
    free(*queue);
    *queue = NULL;
}

int main(){

    QUEUE *queue = createQueue();

    int i;

    for (i = 0; i < 10; i++){
        addQueue(queue, i);
    }
    printf("隊列:");
    displayQueue(queue);
    printf("隊頭:%d\n", getHeadQueue(queue));

    printf("出隊\n");
    delQueue(queue);
    displayQueue(queue);
    printf("隊頭:%d\n", getHeadQueue(queue));

    printf("清空隊列\n");
    clrQueue(queue);

    if (isEmptyQueue(queue)){
        printf("clear\n");
    }

    destryQueue(&queue);
    return 0;
}

           

棧

• 函數

1. 建立棧
2. 增加盤子(壓棧)
3. 是否空棧
4. 拿出盤子(彈出)
5. 列出盤子
6. 得到頂盤
7. 清空棧
8. 銷毀棧

#include <stdio.h>
#include <stdlib.h>
typedef struct node{

    int data;
    struct node *next;

}NODE;

typedef struct stack{

    NODE *top;

}STACK;

STACK *createStack(){

    STACK *stack = (STACK *)malloc(sizeof(STACK));
    if (stack == NULL){
        exit(0);
    }

    stack->top = NULL;

    return stack;

}
int isEmptyStack(STACK *stack){

    if (stack->top == NULL){
        return 1;
    }
    return 0;

}
void pushStack(STACK *stack, int data){

    NODE *pnew= (NODE *)malloc(sizeof(NODE));
    if (pnew == NULL){
        exit(0);
    }
    pnew->data = data;

    pnew->next = stack->top;
    stack->top = pnew;

}
void popStack(STACK *stack){

    NODE *p;
    if(!isEmptyStack(stack)){
        p = stack->top;
        stack->top = p->next;
        free(p);
    }
}
void displayStack(STACK *stack){

    if(!isEmptyStack(stack)){

        NODE *p = stack->top;
        while(p != NULL){

            printf("%d ", p->data);
            p = p->next;
        }
    }

}
int getTopStack(STACK *stack){

    if (!isEmptyStack(stack)){
        return stack->top->data;
    }
    return -9999;
}
void clrStack(STACK *stack){

    while (!isEmptyStack(stack)){
        popStack(stack);
    }
}
void destroyStack(STACK **stack){

    clrStack(*stack);
    free(*stack);
    *stack = NULL;
}

int main(){

    STACK *stack = createStack();

    int i;

    for (i = 0; i < 10; i++){
        pushStack(stack, i);
    }
    printf("棧:");
    displayStack(stack);
    printf("棧頂:%d\n", getTopStack(stack));

    printf("pop:\n");
    popStack(stack);
    
    displayStack(stack);
    printf("棧頂:%d\n", getTopStack(stack));

    printf("清空棧\n");
    clrStack(stack);

    if (isEmptyStack(stack)){
        printf("clear\n");
    }

    destroyStack(&stack);

    return 0;
}