C語言數據結構之棧與隊列怎么相互實現

C語言數據結構之棧與隊列怎么相互實現

在C語言中，棧（Stack）和隊列（Queue）是兩種常見的數據結構，它們分別遵循“后進先出”（LIFO）和“先進先出”（FIFO）的原則。雖然它們在操作方式上有所不同，但通過巧妙的設計，我們可以利用棧來實現隊列，或者利用隊列來實現棧。本文將詳細介紹如何用棧實現隊列，以及如何用隊列實現棧。

1. 用棧實現隊列

1.1 基本思路

隊列的特點是先進先出，而棧的特點是后進先出。為了用棧實現隊列，我們需要使用兩個棧來模擬隊列的行為。具體思路如下：

1. 入隊操作：將元素壓入第一個棧（稱為“輸入?！保?。
2. 出隊操作：如果第二個棧（稱為“輸出?！保榭?，則將輸入棧中的所有元素依次彈出并壓入輸出棧。然后從輸出棧中彈出棧頂元素，即為隊列的隊首元素。

1.2 代碼實現

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

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

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

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

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

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

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

typedef struct {
    Stack input;
    Stack output;
} Queue;

void initQueue(Queue *q) {
    initStack(&q->input);
    initStack(&q->output);
}

void enqueue(Queue *q, int value) {
    push(&q->input, value);
}

int dequeue(Queue *q) {
    if (isEmpty(&q->output)) {
        while (!isEmpty(&q->input)) {
            push(&q->output, pop(&q->input));
        }
    }
    return pop(&q->output);
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);

    printf("%d\n", dequeue(&q)); // 輸出 1
    printf("%d\n", dequeue(&q)); // 輸出 2
    printf("%d\n", dequeue(&q)); // 輸出 3

    return 0;
}

1.3 分析

• 時間復雜度：入隊操作的時間復雜度為O(1)，出隊操作的時間復雜度在最好情況下為O(1)，最壞情況下為O(n)（當輸出棧為空時，需要將輸入棧中的所有元素移動到輸出棧）。
• 空間復雜度：使用了兩個棧，空間復雜度為O(n)。

2. 用隊列實現棧

2.1 基本思路

棧的特點是后進先出，而隊列的特點是先進先出。為了用隊列實現棧，我們需要使用兩個隊列來模擬棧的行為。具體思路如下：

1. 入棧操作：將元素加入非空隊列。
2. 出棧操作：將非空隊列中的元素依次出隊并加入另一個隊列，直到只剩下一個元素，該元素即為棧頂元素，將其出隊。

2.2 代碼實現

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

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

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

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

int isFull(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

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

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

typedef struct {
    Queue q1;
    Queue q2;
} Stack;

void initStack(Stack *s) {
    initQueue(&s->q1);
    initQueue(&s->q2);
}

void push(Stack *s, int value) {
    if (!isEmpty(&s->q1)) {
        enqueue(&s->q1, value);
    } else {
        enqueue(&s->q2, value);
    }
}

int pop(Stack *s) {
    Queue *nonEmptyQueue = isEmpty(&s->q1) ? &s->q2 : &s->q1;
    Queue *emptyQueue = isEmpty(&s->q1) ? &s->q1 : &s->q2;

    while ((nonEmptyQueue->front + 1) % MAX_SIZE != nonEmptyQueue->rear) {
        enqueue(emptyQueue, dequeue(nonEmptyQueue));
    }
    return dequeue(nonEmptyQueue);
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 1);
    push(&s, 2);
    push(&s, 3);

    printf("%d\n", pop(&s)); // 輸出 3
    printf("%d\n", pop(&s)); // 輸出 2
    printf("%d\n", pop(&s)); // 輸出 1

    return 0;
}

2.3 分析

• 時間復雜度：入棧操作的時間復雜度為O(1)，出棧操作的時間復雜度為O(n)（需要將隊列中的元素逐個移動到另一個隊列）。
• 空間復雜度：使用了兩個隊列，空間復雜度為O(n)。

3. 總結

通過上述實現，我們可以看到，棧和隊列雖然是兩種不同的數據結構，但它們之間可以通過相互模擬來實現對方的功能。用棧實現隊列的關鍵在于使用兩個棧來分別處理入隊和出隊操作，而用隊列實現棧的關鍵在于使用兩個隊列來模擬棧的后進先出特性。

在實際應用中，選擇哪種實現方式取決于具體的需求和場景。例如，如果對出隊操作的性能要求較高，可以選擇用棧實現隊列；如果對出棧操作的性能要求較高，可以選擇用隊列實現棧。

希望本文能幫助你更好地理解棧和隊列的相互實現方式，并在實際編程中靈活運用。