C語言棧與隊列如何定義

C語言棧與隊列如何定義

在C語言中，棧（Stack）和隊列（Queue）是兩種常見的數據結構，它們分別遵循不同的操作規則。棧遵循“后進先出”（LIFO）的原則，而隊列遵循“先進先出”（FIFO）的原則。本文將介紹如何在C語言中定義和實現棧與隊列。

1. 棧的定義與實現

棧是一種線性數據結構，只允許在一端進行插入和刪除操作，這一端稱為棧頂（Top）。棧的基本操作包括入棧（Push）和出棧（Pop）。

1.1 棧的結構定義

在C語言中，棧通常使用數組或鏈表來實現。以下是使用數組實現棧的結構定義：

#define MAX_SIZE 100  // 定義棧的最大容量

typedef struct {
    int data[MAX_SIZE];  // 存儲棧元素的數組
    int top;             // 棧頂指針
} Stack;

1.2 棧的初始化

在使用棧之前，需要對其進行初始化，即將棧頂指針top設置為-1，表示棧為空。

void initStack(Stack *s) {
    s->top = -1;
}

1.3 入棧操作

入棧操作將元素添加到棧頂，并更新棧頂指針。

void push(Stack *s, int value) {
    if (s->top >= MAX_SIZE - 1) {
        printf("棧已滿，無法入棧\n");
        return;
    }
    s->data[++(s->top)] = value;
}

1.4 出棧操作

出棧操作將棧頂元素移除，并返回該元素的值。

int pop(Stack *s) {
    if (s->top == -1) {
        printf("棧為空，無法出棧\n");
        return -1;  // 返回一個錯誤值
    }
    return s->data[(s->top)--];
}

1.5 判斷棧是否為空

可以通過檢查棧頂指針top是否為-1來判斷棧是否為空。

int isEmpty(Stack *s) {
    return s->top == -1;
}

2. 隊列的定義與實現

隊列是一種線性數據結構，允許在一端（隊尾）進行插入操作，在另一端（隊頭）進行刪除操作。隊列的基本操作包括入隊（Enqueue）和出隊（Dequeue）。

2.1 隊列的結構定義

在C語言中，隊列通常使用數組或鏈表來實現。以下是使用數組實現隊列的結構定義：

#define MAX_SIZE 100  // 定義隊列的最大容量

typedef struct {
    int data[MAX_SIZE];  // 存儲隊列元素的數組
    int front;          // 隊頭指針
    int rear;           // 隊尾指針
} Queue;

2.2 隊列的初始化

在使用隊列之前，需要對其進行初始化，即將隊頭指針front和隊尾指針rear都設置為0，表示隊列為空。

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

2.3 入隊操作

入隊操作將元素添加到隊尾，并更新隊尾指針。

void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        printf("隊列已滿，無法入隊\n");
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

2.4 出隊操作

出隊操作將隊頭元素移除，并返回該元素的值。

int dequeue(Queue *q) {
    if (q->front == q->rear) {
        printf("隊列為空，無法出隊\n");
        return -1;  // 返回一個錯誤值
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return value;
}

2.5 判斷隊列是否為空

可以通過檢查隊頭指針front和隊尾指針rear是否相等來判斷隊列是否為空。

int isEmpty(Queue *q) {
    return q->front == q->rear;
}

3. 總結

本文介紹了如何在C語言中定義和實現棧與隊列。棧和隊列是兩種基本的數據結構，它們在算法和程序設計中有著廣泛的應用。通過數組實現棧和隊列是一種簡單直觀的方式，但在實際應用中，也可以使用鏈表等更靈活的數據結構來實現棧和隊列。

掌握棧和隊列的基本操作對于理解更復雜的數據結構和算法至關重要。希望本文能幫助你更好地理解和使用棧與隊列。