行业资讯

C语言栈与队列怎么相互实现

发布时间：2022-04-12 10:38:06 作者：iii
来源：亿速云 阅读：146

C语言栈与队列怎么相互实现

1. 引言

在计算机科学中，栈（Stack）和队列（Queue）是两种非常重要的数据结构。它们分别遵循不同的操作规则：栈遵循“后进先出”（LIFO）的原则，而队列遵循“先进先出”（FIFO）的原则。尽管它们在操作规则上有所不同，但栈和队列之间可以通过相互实现来展示它们之间的紧密联系。

本文将详细介绍如何在C语言中通过栈来实现队列，以及如何通过队列来实现栈。我们将从基本概念入手，逐步深入到具体的实现细节，并通过代码示例来帮助读者更好地理解这些概念。

2. 栈与队列的基本概念

2.1 栈（Stack）

栈是一种线性数据结构，它遵循“后进先出”（LIFO）的原则。栈的基本操作包括：

栈通常用于实现递归算法、表达式求值、括号匹配等场景。

2.2 队列（Queue）

队列是一种线性数据结构，它遵循“先进先出”（FIFO）的原则。队列的基本操作包括：

队列通常用于实现任务调度、缓冲区管理、广度优先搜索等场景。

3. 用栈实现队列

3.1 思路分析

要用栈实现队列，我们需要模拟队列的“先进先出”特性。由于栈是“后进先出”的，我们需要使用两个栈来模拟队列的行为。具体思路如下：

  1. 入队操作：将所有元素压入第一个栈（Stack1）。
  2. 出队操作：如果第二个栈（Stack2）为空，则将Stack1中的所有元素依次弹出并压入Stack2，然后从Stack2中弹出栈顶元素。如果Stack2不为空，则直接从Stack2中弹出栈顶元素。

通过这种方式，我们可以确保先进入Stack1的元素会先进入Stack2，从而实现队列的“先进先出”特性。

3.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--];
}

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

typedef struct {
    Stack s1;
    Stack s2;
} Queue;

void initQueue(Queue *q) {
    initStack(&q->s1);
    initStack(&q->s2);
}

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

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

int front(Queue *q) {
    if (isEmpty(&q->s2)) {
        while (!isEmpty(&q->s1)) {
            push(&q->s2, pop(&q->s1));
        }
    }
    return peek(&q->s2);
}

int isEmptyQueue(Queue *q) {
    return isEmpty(&q->s1) && isEmpty(&q->s2);
}

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

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

    printf("Front element: %d\n", front(&q)); // Output: 1
    printf("Dequeue: %d\n", dequeue(&q));    // Output: 1
    printf("Dequeue: %d\n", dequeue(&q));    // Output: 2
    printf("Dequeue: %d\n", dequeue(&q));    // Output: 3

    return 0;
}

3.3 代码解析

3.4 复杂度分析

4. 用队列实现栈

4.1 思路分析

要用队列实现栈，我们需要模拟栈的“后进先出”特性。由于队列是“先进先出”的，我们需要使用两个队列来模拟栈的行为。具体思路如下：

  1. 入栈操作：将元素加入非空队列（Queue1或Queue2）。
  2. 出栈操作：将非空队列中的元素依次出队并加入另一个空队列，直到只剩下一个元素，然后将该元素出队。

通过这种方式，我们可以确保最后进入队列的元素会最先出队，从而实现栈的“后进先出”特性。

4.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;
}

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

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, *emptyQueue;
    if (!isEmpty(&s->q1)) {
        nonEmptyQueue = &s->q1;
        emptyQueue = &s->q2;
    } else {
        nonEmptyQueue = &s->q2;
        emptyQueue = &s->q1;
    }

    while (nonEmptyQueue->front != nonEmptyQueue->rear) {
        enqueue(emptyQueue, dequeue(nonEmptyQueue));
    }

    return dequeue(nonEmptyQueue);
}

int peek(Stack *s) {
    Queue *nonEmptyQueue, *emptyQueue;
    if (!isEmpty(&s->q1)) {
        nonEmptyQueue = &s->q1;
        emptyQueue = &s->q2;
    } else {
        nonEmptyQueue = &s->q2;
        emptyQueue = &s->q1;
    }

    while (nonEmptyQueue->front != nonEmptyQueue->rear) {
        enqueue(emptyQueue, dequeue(nonEmptyQueue));
    }

    int value = dequeue(nonEmptyQueue);
    enqueue(emptyQueue, value);
    return value;
}

int isEmptyStack(Stack *s) {
    return isEmpty(&s->q1) && isEmpty(&s->q2);
}

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

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

    printf("Top element: %d\n", peek(&s)); // Output: 3
    printf("Pop: %d\n", pop(&s));         // Output: 3
    printf("Pop: %d\n", pop(&s));         // Output: 2
    printf("Pop: %d\n", pop(&s));         // Output: 1

    return 0;
}

4.3 代码解析

4.4 复杂度分析

5. 总结

通过本文的介绍，我们了解了如何在C语言中通过栈来实现队列，以及如何通过队列来实现栈。尽管栈和队列在操作规则上有所不同，但通过巧妙地使用两个栈或两个队列，我们可以模拟出另一种数据结构的行为。

在实际应用中，栈和队列的选择取决于具体的需求。栈适用于需要“后进先出”操作的场景，而队列适用于需要“先进先出”操作的场景。通过相互实现，我们可以更好地理解这两种数据结构的特性和应用场景。

希望本文的内容能够帮助读者更好地理解栈和队列的概念，并在实际编程中灵活运用这些数据结构。

推荐阅读：
  1. c++中栈与队列的实现
  2. 如何使用JavaScript实现栈与队列

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

c语言

上一篇：Python如何实现酷炫进度条

下一篇：python数据处理实例分析

相关阅读

您好，登录后才能下订单哦！

密码登录
登录注册
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
产品服务
地区划分
帮助支持
关于我们
行业资讯-文章归档 问答-问答归档
广州亿速云计算有限公司

7*24小时在线电话：400-100-2938

7*24小时在线QQ：800811969

Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有
粤ICP备17096448号-1 粤公网安备 44010402001142号