C語言棧和隊列如何實現

C語言棧和隊列如何實現

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

棧的實現

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

棧的結構定義

首先，我們需要定義一個棧的結構體，包含棧的容量、棧頂指針和存儲數據的數組。

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

初始化棧

在操作棧之前，需要初始化棧，將棧頂指針設置為-1，表示棧為空。

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

壓棧操作

壓棧操作將元素添加到棧頂。首先需要檢查棧是否已滿，如果棧未滿，則將元素添加到棧頂，并更新棧頂指針。

void push(Stack *s, int value) {
    if (s->top >= MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    s->data[++(s->top)] = value;
}

彈棧操作

彈棧操作從棧頂移除元素。首先需要檢查棧是否為空，如果棧不為空，則返回棧頂元素，并更新棧頂指針。

int pop(Stack *s) {
    if (s->top < 0) {
        printf("Stack Underflow\n");
        return -1;
    }
    return s->data[(s->top)--];
}

查看棧頂元素

查看棧頂元素操作返回棧頂元素，但不移除它。

int peek(Stack *s) {
    if (s->top < 0) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->data[s->top];
}

隊列的實現

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

隊列的結構定義

首先，我們需要定義一個隊列的結構體，包含隊列的容量、隊頭指針、隊尾指針和存儲數據的數組。

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

初始化隊列

在操作隊列之前，需要初始化隊列，將隊頭指針和隊尾指針都設置為0。

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

入隊操作

入隊操作將元素添加到隊尾。首先需要檢查隊列是否已滿，如果隊列未滿，則將元素添加到隊尾，并更新隊尾指針。

void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        printf("Queue is full\n");
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

出隊操作

出隊操作從隊頭移除元素。首先需要檢查隊列是否為空，如果隊列不為空，則返回隊頭元素，并更新隊頭指針。

int dequeue(Queue *q) {
    if (q->front == q->rear) {
        printf("Queue is empty\n");
        return -1;
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return value;
}

查看隊頭元素

查看隊頭元素操作返回隊頭元素，但不移除它。

int peekQueue(Queue *q) {
    if (q->front == q->rear) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->data[q->front];
}

總結

本文介紹了如何在C語言中實現棧和隊列這兩種基本的數據結構。棧和隊列在算法和程序設計中有著廣泛的應用，理解它們的實現原理對于編寫高效的程序至關重要。通過本文的示例代碼，讀者可以掌握棧和隊列的基本操作，并能夠在實際編程中靈活運用。