devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构|C语言版】栈和队列

作者：Cpp五条 | 2024-05-13 11:48:15

赞

踩

【数据结构|C语言版】栈和队列

在这里插入图片描述
在这里插入图片描述

#include<GUIQU.h>
int main {
上期回顾: 【数据结构|C语言版】算法效率和复杂度分析
个人主页：C_GUIQU
归属专栏：【数据结构（C语言版）学习】
return 一键三连;
}
在这里插入图片描述

前言

各位小伙伴大家好！上次小编给大家讲解了数据结构中的重要基础：算法效率和复杂度分析，接下来我们讲解一下栈和队列！

【知识框架】
在这里插入图片描述

1. 栈

1.1 栈的概念和性质

栈（Stack）是一种基本的数据结构，它遵循后进先出（Last In, First Out, LIFO）的原则。这意味着最后一个被添加到栈中的元素将会是第一个被移除的元素。这个特性使得栈在解决特定类型的问题时非常有用，比如内存管理、函数调用、表达式求值等场景。

【基本概念】

  1. 栈顶（Top）与栈底（Bottom）：

    • 栈顶是进行元素插入（称为“压栈”）和删除（称为“弹栈”）操作的位置。
    • 栈底则是栈的另一端，通常不进行直接操作。

  2. 操作：

    • push 或 add：向栈顶添加一个元素。
    • pop 或 remove：从栈顶移除一个元素，并可选择返回该元素。
    • peek 或 top：查看但不移除栈顶的元素。
    • is_empty：检查栈是否为空。
    • size：返回栈中元素的数量。

  3. 实现方式：

    • 栈可以用数组或链表来实现。数组实现较为简单，但可能需要预先分配较大的空间或动态调整数组大小；链表实现则更灵活，插入和删除操作的时间复杂度都为O(1)。

【性质】

  1. 线性结构：栈是一种线性数据结构，尽管元素之间的逻辑关系不是顺序的，但它们在内存中可以是连续存储的。

  2. 受限访问：只能访问栈顶的元素，不能直接访问中间或底部的元素，这与队列（遵循先进先出，FIFO原则）或数组等其他线性结构不同。

  3. 动态大小：栈的大小会随着元素的压栈和弹栈而动态变化。

  4. 应用场景：

    • 函数调用堆栈：每当调用一个函数时，相关信息（如局部变量、返回地址）会被压入一个特殊的栈中，当函数返回时，这些信息会被逐一弹出。
    • 表达式求值与解析：如计算数学表达式或处理编程语言的语法结构时，栈可以用来保存运算符和操作数，便于按照正确的顺序进行计算。
    • 回溯算法：在解决迷宫、括号匹配等问题时，栈可以用来存储路径或状态，以便在遇到死胡同时回退到上一步。

【实例说明】

假设我们要计算一个简单的后缀表达式（如 3 4 + 5 *），使用栈的操作流程如下：

  1. 遇到数字 3 和 4，直接压栈。
  2. 遇到操作符 +，弹出 4 和 3，计算 3 + 4 = 7，并将结果 7 压入栈。
  3. 遇到数字 5，压栈。
  4. 遇到操作符 *，弹出 5 和 7，计算 7 * 5 = 35，将结果压入栈。
  5. 最终栈中只剩一个元素 35，即为表达式的计算结果。

通过这个过程，我们可以看到栈如何有效地帮助我们管理和处理数据，尤其是在有明确顺序约束的场景下。

1.2 顺序栈

顺序栈是栈的一种具体实现方式，它基于数组来存储栈中的元素。在顺序栈中，数组的末端（通常是数组的一个固定索引位置，初始时设为-1）用来模拟栈顶，随着元素的压栈（入栈）和弹栈（出栈），这个末端索引会相应地增减。

【特性】

  • 空间预先分配：顺序栈需要预先分配一段连续的内存空间，用于存放栈中的元素。这意味着栈的最大容量在初始化时就被确定，如果超出这个容量，可能会导致溢出错误。
  • 操作效率：对于压栈和弹栈操作，顺序栈的时间复杂度均为O(1)，因为只需要对数组的末端索引进行简单的修改即可，不需要移动数组中的元素。
  • 空间利用率：如果栈的实际元素数量远小于预分配的空间，那么部分空间会被闲置，从而降低了空间利用率。

在C语言中实现顺序栈，主要涉及到以下几个步骤：定义栈的结构体、初始化栈、进行基本的栈操作（如压栈、弹栈、查看栈顶元素和判断栈是否为空）。

下面是一个简单的C语言顺序栈实现示例：

【定义顺序栈结构体】

首先，定义一个结构体来描述顺序栈，包括一个整型数组用于存储元素，以及一个整型变量top来标记栈顶位置。

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

#define MAX_SIZE 100 // 定义栈的最大容量

typedef struct {
    int data[MAX_SIZE]; // 存储元素的数组
    int top;           // 栈顶指针
} Stack;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

【初始化栈】
接着，编写一个函数来初始化栈，包括将栈顶指针top设置为-1，表示栈为空。

void initStack(Stack* s) {
    s->top = -1; // 初始化栈顶指针
}

  • 1
  • 2
  • 3

【判断栈是否为空】

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

  • 1
  • 2
  • 3

【压栈操作】

压栈操作需要检查栈是否已满，如果未满，则将元素添加到栈顶并更新top。

bool push(Stack* s, int item) {
    if (s->top >= MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return false;
    }
    s->data[++(s->top)] = item; // 先加后用，将元素放入栈顶并更新top
    return true;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

【弹栈操作】

弹栈操作需要检查栈是否为空，如果不为空，则移除栈顶元素并更新top。

bool pop(Stack* s, int* item) {
    if (isEmpty(s)) {
        printf("Stack Underflow\n");
        return false;
    }
    *item = s->data[s->top--]; // 获取并返回栈顶元素，然后减小top
    return true;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

【查看栈顶元素】

int peek(Stack* s) {
    if (!isEmpty(s)) {
        return s->data[s->top];
    }
    printf("Stack is empty.\n");
    return -1; // 或者其他错误代码
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

【示例使用】

int main() {
    Stack s;
    initStack(&s);
    
    push(&s, 10);
    push(&s, 20);
    printf("Top element is: %d\n", peek(&s));
    pop(&s, NULL); // 弹出栈顶元素，这里不关心弹出的值
    printf("After pop, top element is: %d\n", peek(&s));
    
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

这段代码展示了如何定义、初始化、操作一个顺序栈，并包含了一个简单的使用示例。请注意，实际应用中可能需要根据具体需求调整栈的最大容量MAX_SIZE以及其他细节。

1.3 链栈

在C语言中实现链栈（链式存储的栈），我们首先需要定义链表节点的结构体，然后实现链栈的基本操作，包括初始化、压栈、弹栈、查看栈顶元素以及判断栈是否为空。

【定义链表节点结构体】
链栈通常使用单链表实现，其中每个节点包含数据域和指向下一个节点的指针。

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

// 定义链表节点结构体
typedef struct Node {
    int data;            // 数据域
    struct Node* next;   // 指向下一个节点的指针
} Node;

// 定义链栈结构体
typedef struct {
    Node* top;          // 指向栈顶的指针
} Stack;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

【初始化链栈】

初始化链栈主要是将栈顶指针设为NULL，表示栈为空。

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

  • 1
  • 2
  • 3

【判断栈是否为空】

检查栈顶指针是否为NULL。

bool isEmpty(Stack* s) {
    return s->top == NULL;
}

  • 1
  • 2
  • 3

【压栈操作】

在链栈的顶部添加新元素，即在链表头部插入节点。

void push(Stack* s, int item) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = item;       // 赋值
    newNode->next = s->top;     // 新节点的next指向原栈顶
    s->top = newNode;           // 更新栈顶指针
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

【弹栈操作】

删除链栈顶部元素，即删除链表头部节点。

int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack Underflow\n");
        exit(1);
    }
    Node* temp = s->top;      // 临时保存栈顶节点
    int item = temp->data;    // 保存要返回的数据
    s->top = temp->next;      // 更新栈顶指针
    free(temp);              // 释放原栈顶节点的内存
    return item;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

【查看栈顶元素】

返回栈顶元素，但不改变栈的状态。

int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty.\n");
        return -1; // 或其他错误代码
    }
    return s->top->data;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

【示例使用】

int main() {
    Stack s;
    initStack(&s);
    
    push(&s, 10);
    push(&s, 20);
    printf("Top element is: %d\n", peek(&s));
    printf("Popped element: %d\n", pop(&s));
    printf("After pop, top element is: %d\n", peek(&s));
    
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

这段代码展示了如何定义一个链栈结构体，以及如何执行链栈的基本操作。请注意，在实际使用中应考虑错误处理和资源管理，例如确保内存正确分配和释放。

1.4 共享栈

在C语言中实现共享栈，指的是让两个栈共用同一块内存区域，以提高空间利用率。这种设计尤其适用于栈的大小难以估计，且可能出现一个栈空闲而另一个栈空间不足的情况。共享栈的关键在于通过两个栈顶指针分别跟踪两个栈的顶部，确保它们不会互相干扰。

【定义共享栈结构体】
首先，定义一个共享栈的结构体，包括一个静态数组用于存储数据，以及两个整型变量top1和top2分别作为两个栈的栈顶指针。

#include <stdio.h>
#include <assert.h>

#define MAX_SIZE 100 // 共享栈的最大容量

typedef struct {
    int data[MAX_SIZE]; // 共享的存储空间
    int top1;          // 栈1的栈顶指针
    int top2;          // 栈2的栈顶指针
} SharedStack;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

【初始化共享栈】
初始化共享栈时，将两个栈顶指针都设置为边界值，以表明栈为空。

void initSharedStack(SharedStack* s) {
    assert(s != NULL);
    s->top1 = -1; // 栈1为空时，top1为-1
    s->top2 = MAX_SIZE; // 栈2为空时，top2为MAX_SIZE
}

  • 1
  • 2
  • 3
  • 4
  • 5

【判断栈是否为空】
分别定义函数来判断栈1和栈2是否为空。

bool isStack1Empty(const SharedStack* s) {
    return s->top1 == -1;
}

bool isStack2Empty(const SharedStack* s) {
    return s->top2 == MAX_SIZE;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

【压栈操作】
实现压栈操作时，需要注意栈满的条件是两个栈顶指针相邻（即top1 + 1 == top2或top2 - 1 == top1，具体取决于实现方式）。

bool pushToStack1(SharedStack* s, int item) {
    if ((s->top1 + 1) == s->top2) { // 检查栈满
        printf("Stack1 Overflow\n");
        return false;
    }
    s->data[++(s->top1)] = item;
    return true;
}

bool pushToStack2(SharedStack* s, int item) {
    if (s->top2 == (s->top1 + 1)) { // 检查栈满
        printf("Stack2 Overflow\n");
        return false;
    }
    s->data[--(s->top2)] = item;
    return true;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

【弹栈操作】
弹栈操作相对简单，只需更新相应的栈顶指针并返回数据。

int popFromStack1(SharedStack* s) {
    if (isStack1Empty(s)) {
        printf("Stack1 Underflow\n");
        return -1; // 或其他错误代码
    }
    return s->data[s->top1--];
}

int popFromStack2(SharedStack* s) {
    if (isStack2Empty(s)) {
        printf("Stack2 Underflow\n");
        return -1; // 或其他错误代码
    }
    return s->data[s->top2++];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

【示例使用】

int main() {
    SharedStack sharedStack;
    initSharedStack(&sharedStack);
    
    pushToStack1(&sharedStack, 1);
    pushToStack2(&sharedStack, 2);
    printf("Popped from Stack1: %d\n", popFromStack1(&sharedStack));
    printf("Popped from Stack2: %d\n", popFromStack2(&sharedStack));
    
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

这段代码展示了如何定义和操作一个共享栈，包括初始化、压栈、弹栈以及检查栈是否为空等基本功能。请注意，实际应用中应根据具体情况调整栈的容量及错误处理逻辑。

2. 队列

2.1 队列的概念和性质

队列（Queue）是一种基础且广泛使用的数据结构，它的特点是遵循先进先出（First In, First Out, FIFO）的原则。这意味着最早进入队列的元素也将是最先离开队列的元素。队列的这种特性类似于现实生活中的排队场景，比如人们在超市收银台前排队结账，先到的人先完成结账离开。

【队列的基本概念】

  1. 结构: 队列由两部分组成——队头（front）和队尾（rear）。队头是队列中允许删除元素的一端，而队尾是允许添加元素的一端。

  2. 操作:

    • 入队（Enqueue）: 在队列的队尾添加一个元素。
    • 出队（Dequeue）: 从队列的队头移除一个元素。
    • 查看队头元素: 不移除的情况下查看队列最前面的元素。
    • 判断队列是否为空: 检查队列中是否有元素。

  3. 实现方式:

    • 顺序队列: 使用数组实现，需要处理队列满时的扩容问题或队列空时的缩容问题。
    • 循环队列: 也是基于数组实现，但通过取模运算使得数组的存储空间可以循环使用，解决了顺序队列假溢出的问题。
    • 链式队列: 使用链表实现，每个节点包含元素和指向下一个节点的指针，更加灵活，不存在固定大小的限制。

【队列的性质】

  1. 线性结构: 队列属于线性数据结构，元素之间存在一对一的前后关系。
  2. 受限访问: 只能在队头进行删除操作，在队尾进行插入操作，不能随机访问队列中的元素。
  3. 动态大小: 队列的长度可以根据需要动态变化，可以增长也可以缩小。
  4. 应用场景广泛: 队列常用于需要处理一系列任务，且这些任务必须按照到达的顺序被处理的场景，如打印任务调度、CPU进程调度、消息队列、事件处理等。

总之，队列作为一种数据结构，其核心在于提供了按先进先出规则管理数据的能力，这一特性使其成为解决特定类型问题的高效工具。

2.2 循环队列

循环队列是队列的一种特殊实现方式，它使用数组来存储队列中的元素，并利用环状的特性使得数组空间可以得到更有效的利用。在循环队列中，当队列尾部达到数组的末端时，不是停止插入，而是绕回到数组的起始位置继续插入。同样，队列头部在出队时，也会在达到数组末端后回到起始位置。这样，即使队列中还有空余空间，数组也不会发生假溢出。

【关键特点】

  1. 数组使用：循环队列仍然使用数组来存储元素，但通过维护两个指针（头指针和尾指针）来追踪队列的开始和结束位置，这两个指针都是在数组的索引范围内循环移动。

  2. 头指针（front）与尾指针（rear）：

    • 头指针指向队列的第一个元素的位置（即下一个要出队的元素）。
    • 尾指针指向队列的最后一个元素之后的位置（即下一个要入队的位置）。

  3. 判满条件：由于头尾指针都可能回到数组的起始位置，因此判断循环队列是否已满不能简单地比较头尾指针是否相等，常用的判满条件是(rear + 1) % max_size == front，其中max_size是数组的大小。

  4. 判空条件：头尾指针相等，即front == rear时，队列为空。

  5. 解决假溢出：通过循环利用数组空间，避免了普通队列中因数组两端相遇而导致无法继续入队的假溢出问题。

【操作】

  • 入队（enqueue）：在尾指针指向的位置插入新元素，并将尾指针向前移动一位（循环回到数组开头）。如果队列已满，则需要处理满队情况。

  • 出队（dequeue）：从头指针指向的位置移除元素，并将头指针向前移动一位（同样循环移动）。如果队列为空，则需要处理空队情况。

  • 查看队首元素：直接读取头指针指向的数组元素即可。

【实现注意事项】

  • 区分空和满的标志：因为头尾指针相等既可能是空队也可能是满队，通常会牺牲一个数组单元或者使用额外的布尔变量来区分这两种情况。

  • 数组大小的选择：考虑到循环的特性，数组的实际有效大小应该比实际需要的队列大小少一个单位，以避免混淆空队和满队的情况。

循环队列的实现提高了空间的利用率，特别适合于那些需要高效插入和删除操作且数据量动态变化的场景，如缓存管理、任务调度等。

2.3 链式队列

链式队列是队列的一种实现方式，它使用链表（通常为单链表或双链表）作为底层数据结构来存储队列中的元素，而非数组。链式队列的主要特点是动态空间分配，能够灵活地适应元素数量的变化，避免了循环队列中固定大小可能导致的潜在空间浪费或溢出问题。

【基本概念】

  1. 节点结构：链式队列中的每个元素存储在一个节点中，每个节点包含两部分：一个是存储数据的数据域（通常为一个变量或结构），另一个是指向下一个节点的指针域。

  2. 队列的表示：链式队列通过两个指针来表示队列的状态，分别是队头指针和队尾指针。

    • 队头指针（front）指向队列的第一个元素（即队首节点）。
    • 队尾指针（rear）指向队列的最后一个元素（即队尾节点）。注意，当队列为空时，队头指针和队尾指针都为NULL。

  3. 操作：

    • 入队（Enqueue）：在队列的末尾添加一个新元素，即在队尾节点之后创建一个新的节点，并更新队尾指针指向新节点。
    • 出队（Dequeue）：从队列的前端移除一个元素，即删除队头节点，并更新队头指针指向原队头节点的下一个节点。
    • 查看队首元素：直接访问队头节点的数据域获取队首元素，无需改变队列状态。
    • 判断队列是否为空：检查队头指针是否为NULL，如果是，则队列为空。

【优点】

  • 动态性：链式队列的空间是动态分配的，可以根据需要自动扩展，不会出现数组固定大小的局限性。
  • 灵活性：插入和删除操作简单，只需要改变指针的指向，不需要移动元素。
  • 避免溢出：理论上只要内存足够，链式队列就不会满。

【缺点】

  • 额外开销：每个节点除了存储数据外，还需要额外的空间来存储指针，相比数组实现有额外的内存消耗。
  • 访问速度：链式结构相比数组访问元素的速度较慢，因为需要遍历链表。

【应用场景】

链式队列因其动态性和灵活性，适用于不确定数据量大小或需要频繁插入删除操作的场景，如某些类型的事件处理系统、任务调度、广度优先搜索（BFS）的实现等。

2.4 双端队列

双端队列（Double-Ended Queue，简称 Deque）是一种具有队列和栈特性的线性数据结构。与传统的队列（只能在一端添加元素，在另一端移除元素）不同，双端队列允许在其两端进行插入和删除操作。这使得双端队列可以同时表现先进先出（FIFO，First In First Out）和后进先出（LIFO，Last In First Out）的特性，具体取决于操作的位置。

【特点】

  1. 双端操作：可以在队列的前端（头部）进行入队（enqueue）和出队（dequeue）操作，同时也可以在队列的后端（尾部）进行同样的操作。

  2. 动态调整大小：大多数双端队列实现支持动态调整其大小，以适应元素数量的变化。

  3. 多样化的操作集合：除了基本的入队和出队操作，双端队列还提供了在两端读取元素的功能，如获取队头元素和队尾元素，以及在两端进行插入操作。

  4. 变种：存在输入受限的双端队列和输出受限的双端队列，前者允许在一端进行插入和删除，在另一端仅允许插入；后者则是一端允许插入和删除，另一端仅允许删除。

  5. 栈和队列的融合：如果限制操作方式，双端队列可以模拟栈或队列的行为。例如，仅在一端进行插入和删除操作时，双端队列就变成了栈；而如果两端都遵循FIFO原则，则表现为队列。

【常见操作】

  • addFront(item)：在队列前端添加一个元素。
  • addRear(item)：在队列后端添加一个元素。
  • removeFront()：从队列前端移除一个元素。
  • removeRear()：从队列后端移除一个元素。
  • getFront()：获取队列前端的元素（不移除）。
  • getRear()：获取队列后端的元素（不移除）。
  • isEmpty()：检查双端队列是否为空。
  • size()：返回双端队列中的元素数量。

【实现方式】
双端队列可以通过数组（需要处理循环和动态扩容的问题）或者链表（单链表或双链表）来实现。在C++标准模板库(STL)中，std::deque就是一个实现了双端队列的容器，它采用了分块的线性结构进行存储，允许高效地在两端进行插入和删除操作。

3. 例题精选

3.1 有效的括号

在这里插入图片描述

3.2 用队列实现栈

在这里插入图片描述

2.4 用栈实现队列

在这里插入图片描述

3.4 设计循环队列

在这里插入图片描述

3.5 参考答案

【有效的括号】

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    int stk[n + 1], top = 0;
    for (int i = 0; i < n; i++) {
        char ch = pairs(s[i]);
        if (ch) {
            if (top == 0 || stk[top - 1] != ch) {
                return false;
            }
            top--;
        } else {
            stk[top++] = s[i];
        }
    }
    return top == 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

【用队列实现栈】

#define LEN 20
typedef struct queue {
    int *data;
    int head;
    int rear;
    int size;
} Queue;

typedef struct {
    Queue *queue1, *queue2;
} MyStack;

Queue *initQueue(int k) {
    Queue *obj = (Queue *)malloc(sizeof(Queue));
    obj->data = (int *)malloc(k * sizeof(int));
    obj->head = -1;
    obj->rear = -1;
    obj->size = k;
    return obj;
}

void enQueue(Queue *obj, int e) {
    if (obj->head == -1) {
        obj->head = 0;
    }
    obj->rear = (obj->rear + 1) % obj->size;
    obj->data[obj->rear] = e;
}

int deQueue(Queue *obj) {
    int a = obj->data[obj->head];
    if (obj->head == obj->rear) {
        obj->rear = -1;
        obj->head = -1;
        return a;
    }
    obj->head = (obj->head + 1) % obj->size;
    return a;
}

int isEmpty(Queue *obj) {
    return obj->head == -1;
}

MyStack *myStackCreate() {
    MyStack *obj = (MyStack *)malloc(sizeof(MyStack));
    obj->queue1 = initQueue(LEN);
    obj->queue2 = initQueue(LEN);
    return obj;
}

void myStackPush(MyStack *obj, int x) {
    if (isEmpty(obj->queue1)) {
        enQueue(obj->queue2, x);
    } else {
        enQueue(obj->queue1, x);
    }
}

int myStackPop(MyStack *obj) {
    if (isEmpty(obj->queue1)) {
        while (obj->queue2->head != obj->queue2->rear) {
            enQueue(obj->queue1, deQueue(obj->queue2));
        }
        return deQueue(obj->queue2);
    }
    while (obj->queue1->head != obj->queue1->rear) {
        enQueue(obj->queue2, deQueue(obj->queue1));
    }
    return deQueue(obj->queue1);
}

int myStackTop(MyStack *obj) {
    if (isEmpty(obj->queue1)) {
        return obj->queue2->data[obj->queue2->rear];
    }
    return obj->queue1->data[obj->queue1->rear];
}

bool myStackEmpty(MyStack *obj) {
    if (obj->queue1->head == -1 && obj->queue2->head == -1) {
        return true;
    }
    return false;
}

void myStackFree(MyStack *obj) {
    free(obj->queue1->data);
    obj->queue1->data = NULL;
    free(obj->queue1);
    obj->queue1 = NULL;
    free(obj->queue2->data);
    obj->queue2->data = NULL;
    free(obj->queue2);
    obj->queue2 = NULL;
    free(obj);
    obj = NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98

【用栈实现队列】

typedef struct {
    int* stk;
    int stkSize;
    int stkCapacity;
} Stack;

Stack* stackCreate(int cpacity) {
    Stack* ret = malloc(sizeof(Stack));
    ret->stk = malloc(sizeof(int) * cpacity);
    ret->stkSize = 0;
    ret->stkCapacity = cpacity;
    return ret;
}

void stackPush(Stack* obj, int x) {
    obj->stk[obj->stkSize++] = x;
}

void stackPop(Stack* obj) {
    obj->stkSize--;
}

int stackTop(Stack* obj) {
    return obj->stk[obj->stkSize - 1];
}

bool stackEmpty(Stack* obj) {
    return obj->stkSize == 0;
}

void stackFree(Stack* obj) {
    free(obj->stk);
}

typedef struct {
    Stack* inStack;
    Stack* outStack;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue* ret = malloc(sizeof(MyQueue));
    ret->inStack = stackCreate(100);
    ret->outStack = stackCreate(100);
    return ret;
}

void in2out(MyQueue* obj) {
    while (!stackEmpty(obj->inStack)) {
        stackPush(obj->outStack, stackTop(obj->inStack));
        stackPop(obj->inStack);
    }
}

void myQueuePush(MyQueue* obj, int x) {
    stackPush(obj->inStack, x);
}

int myQueuePop(MyQueue* obj) {
    if (stackEmpty(obj->outStack)) {
        in2out(obj);
    }
    int x = stackTop(obj->outStack);
    stackPop(obj->outStack);
    return x;
}

int myQueuePeek(MyQueue* obj) {
    if (stackEmpty(obj->outStack)) {
        in2out(obj);
    }
    return stackTop(obj->outStack);
}

bool myQueueEmpty(MyQueue* obj) {
    return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);
}

void myQueueFree(MyQueue* obj) {
    stackFree(obj->inStack);
    stackFree(obj->outStack);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81

【设计循环队列】

typedef struct {
    int front;
    int rear;
    int capacity;
    int *elements;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    obj->capacity = k + 1;
    obj->rear = obj->front = 0;
    obj->elements = (int *)malloc(sizeof(int) * obj->capacity);
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if ((obj->rear + 1) % obj->capacity == obj->front) {
        return false;
    }
    obj->elements[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->capacity;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (obj->rear == obj->front) {
        return false;
    }
    obj->front = (obj->front + 1) % obj->capacity;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->rear == obj->front) {
        return -1;
    }
    return obj->elements[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (obj->rear == obj->front) {
        return -1;
    }
    return obj->elements[(obj->rear - 1 + obj->capacity) % obj->capacity];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->rear == obj->front;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % obj->capacity == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->elements);
    free(obj);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

结语

以上就是小编对栈和队列的讲解。
如果觉得小编讲的还可以，还请一键三连。互三必回！
持续更新中~！

在这里插入图片描述

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/563500
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号