【地铁上的面试题】--基础部分--数据结构与算法--栈和队列

一、栈的基本概念和特点

1.1 栈的定义与特点

栈是一种基于后进先出（Last-In-First-Out，LIFO）原则的抽象数据类型（ADT）。它可以理解为一种特殊的线性数据结构，其中元素按照一定的顺序进行插入和删除操作。 栈的定义包括以下几个要点：

1. 元素：栈由一系列元素组成，可以是任意类型的数据。
2. 顶部（Top）：栈的顶部是最后一个插入的元素，也是唯一可以访问和删除的元素。
3. 压入（Push）：将元素添加到栈的顶部，也称为入栈。
4. 弹出（Pop）：从栈的顶部移除元素，也称为出栈。
5. 空栈（Empty Stack）：不包含任何元素的栈。
6. 栈空判断（IsEmpty）：检查栈是否为空。

栈的特点是，只能在栈的顶部进行插入和删除操作。最后插入的元素将首先被删除，这与我们日常生活中的物理堆栈类似，例如书堆或者餐盘堆放等。

1.2 栈的实现方式

栈可以通过多种方式实现，常见的有以下三种方式：

1. 数组实现栈： 使用数组作为底层数据结构，通过维护一个指针（通常称为栈顶指针）来指示栈顶元素的位置。当元素入栈时，栈顶指针向上移动；当元素出栈时，栈顶指针向下移动。数组实现的栈具有简单、高效的特点，可以直接通过索引访问元素。然而，数组实现的栈大小固定，无法动态调整，可能存在空间浪费的问题。
2. 链表实现栈： 使用链表作为底层数据结构，通过维护指向栈顶节点的指针来表示栈的状态。每个节点包含一个元素和一个指向下一个节点的指针。入栈操作相当于在链表头部插入一个新节点，出栈操作相当于删除链表头部节点。链表实现的栈可以动态调整大小，但由于链表需要额外的指针空间，相比数组实现的栈，其空间开销更大。
3. 动态数组实现栈： 动态数组是在数组实现的基础上进行扩展的一种方式。通过动态调整数组的大小来满足栈的需求，当栈的容量不足时，可以重新分配更大的数组，并将元素复制到新数组中。这种方式结合了数组实现的高效随机访问和链表实现的动态大小特点。但动态数组实现的栈在扩容过程中可能涉及元素的复制，导致一定的时间开销。

选择栈的实现方式取决于具体的需求和场景。如果需要高效的随机访问和固定大小的栈，可以选择数组实现；如果需要动态大小的栈且对空间效率要求不是特别高，可以选择链表实现；如果需要兼顾随机访问和动态大小的栈，可以考虑动态数组实现。

1.3 栈的应用场景

栈在计算机科学和软件开发中有广泛的应用场景。以下是一些常见的栈的应用场景：

1. 函数调用： 栈常用于函数调用的过程中，每次函数调用时，会将当前函数的状态（局部变量、返回地址等）压入栈中，以便在函数返回时能够正确恢复上一级函数的状态。
2. 表达式求值： 栈可以用于解析和求解数学表达式，例如中缀表达式转换为后缀表达式，或者计算后缀表达式的值。通过栈的先进后出的特性，可以有效地处理运算符的优先级和括号的匹配。
3. 括号匹配： 栈常用于检查括号是否匹配的问题。通过遍历字符串中的括号字符，将左括号入栈，遇到右括号时弹出栈顶元素并检查是否匹配，以判断括号是否正确闭合。
4. 浏览器历史记录： 浏览器的历史记录可以使用栈来实现。每次打开一个新的网页时，将该网页的 URL 入栈；当点击返回按钮时，将栈顶的 URL 弹出，实现网页的后退功能。
5. 撤销操作： 许多应用程序中都提供了撤销操作，栈可以用于保存操作的历史记录。每次执行一个操作时，将操作的信息入栈，当需要撤销时，可以从栈中弹出最近的操作并执行相应的逆操作。
6. 递归算法： 递归算法常常使用栈来实现函数调用的过程。当递归函数调用自身时，将当前状态入栈，直到达到递归终止条件，然后通过弹出栈顶元素恢复上一层函数的执行。

栈在许多算法和数据结构中都扮演着重要的角色，它们提供了一种简单且高效的数据结构，用于解决许多实际问题。熟悉栈的应用场景和使用方法有助于程序员在开发过程中更好地利用栈的特性。

二、栈的操作和复杂度分析

2.1 入栈操作

1. 入栈操作的实现 以下是使用 C 语言实现入栈操作的示例代码：

代码语言：javascript复制

#include <stdio.h>

#define MAX_SIZE 100

// 定义栈结构
typedef struct {
    int data[MAX_SIZE];  // 存储数据的数组
    int top;             // 栈顶指针
} Stack;

// 初始化栈
void initStack(Stack* stack) {
    stack->top = -1;  // 将栈顶指针置为初始值
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

// 入栈操作
void push(Stack* stack, int value) {
    if (isFull(stack)) {
        printf("Error: Stack is full.n");
        return;
    }
    stack->top  ;                  // 栈顶指针加1
    stack->data[stack->top] = value;  // 将元素存入栈顶位置
}

// 测试入栈操作
int main() {
    Stack stack;
    initStack(&stack);  // 初始化栈

    // 入栈操作
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    // 输出栈中元素
    printf("Stack elements: ");
    while (!isEmpty(&stack)) {
        printf("%d ", stack.data[stack.top]);
        stack.top--;  // 栈顶指针减1，模拟出栈操作
    }
    printf("n");

    return 0;
}

上述代码中，我们通过定义一个结构体 Stack 来表示栈，其中包括一个存储数据的数组 data 和一个栈顶指针 top。initStack 函数用于初始化栈，isEmpty 函数用于判断栈是否为空，isFull 函数用于判断栈是否已满，push 函数用于进行入栈操作。在 main 函数中，我们先初始化栈，然后调用 push 函数多次进行入栈操作，并通过循环遍历栈中的元素输出结果。

1. 入栈操作的时间复杂度 入栈操作的时间复杂度是 O(1)，即常数时间复杂度。因为在入栈操作中，无论栈中已有多少元素，我们只需要执行检查栈是否已满（常数时间复杂度）、更新栈顶指针（常数时间复杂度）、存储新元素到栈顶位置（常数时间复杂度）。由于这些操作的执行次数与栈的大小无关，因此入栈操作的时间复杂度是恒定的，无论栈中存储的元素数量有多少，入栈操作都能在常数时间内完成，这使得栈成为一种高效的数据结构。无需遍历整个栈或移动其他元素，入栈操作只需要常数时间，使得栈适用于许多实时应用和算法中。
2. 入栈操作的空间复杂度 入栈操作的空间复杂度为 O(1)，即常数空间复杂度。因为我们只需要额外存储新元素到栈中，不会随着栈中元素的增加而增加额外的空间。无论栈的大小如何，入栈操作只需要分配一个额外的存储位置来存储新元素。因此，入栈操作的空间复杂度是恒定的，不会随着栈的大小而增加。无论栈中存储的元素数量有多少，入栈操作只需要常数额外空间。

Tip：除了存储栈元素本身的空间外，栈的实现可能还需要一些额外的空间来存储栈的相关信息，例如栈顶指针。但这些额外的空间也是固定的，与栈的大小无关，因此不会影响入栈操作的空间复杂度。

2.2 出栈操作

1. 出栈操作的实现 以下是使用 C 语言实现出栈操作的示例代码：

代码语言：javascript复制

#include <stdio.h>
#define MAX_SIZE 100

// 定义栈结构
typedef struct {
    int data[MAX_SIZE];  // 存储数据的数组
    int top;             // 栈顶指针
} Stack;

// 初始化栈
void initStack(Stack* stack) {
    stack->top = -1;  // 将栈顶指针置为初始值
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

// 出栈操作
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Error: Stack is empty.n");
        return -1;  // 返回一个错误值
    }
    int value = stack->data[stack->top];  // 获取栈顶元素
    stack->top--;                        // 栈顶指针减1，模拟出栈操作
    return value;
}

// 测试出栈操作
int main() {
    Stack stack;
    initStack(&stack);  // 初始化栈

    // 入栈操作
    stack.data[  stack.top] = 10;
    stack.data[  stack.top] = 20;
    stack.data[  stack.top] = 30;

    // 出栈操作
    while (!isEmpty(&stack)) {
        int value = pop(&stack);
        printf("Popped value: %dn", value);
    }

    return 0;
}

上述代码中，我们使用结构体 Stack 表示栈，其中包含一个存储数据的数组 data 和一个栈顶指针 top。initStack 函数用于初始化栈，isEmpty 函数用于判断栈是否为空，pop 函数用于进行出栈操作。在 main 函数中，我们先初始化栈，然后使用 stack.data[ stack.top] 将元素入栈，通过调用 pop 函数进行出栈操作，并输出出栈的元素。

Tip：出栈操作的实现相对简单，只需要更新栈顶指针并返回栈顶元素即可。当栈不为空时，我们可以通过访问栈顶指针所指向的元素获取栈顶元素的值，并将栈顶指针减1，模拟出栈操作。

1. 出栈操作的时间复杂度 出栈操作的时间复杂度是 O(1)，即常数时间复杂度。在出栈操作中，无论栈中已有多少元素，我们只需要执行检查栈是否为空（常数时间复杂度）、获取栈顶元素的值（常数时间复杂度）、更新栈顶指针（常数时间复杂度），由于这些操作的执行次数与栈的大小无关，因此出栈操作的时间复杂度是恒定的。无论栈中存储的元素数量有多少，出栈操作都能在常数时间内完成，无需遍历整个栈或移动其他元素，出栈操作只需要常数时间。
2. 出栈操作的空间复杂度 出栈操作的空间复杂度为 O(1)，即常数空间复杂度。在出栈操作中，我们不需要额外分配或释放额外的空间。出栈操作只涉及到更新栈顶指针和返回栈顶元素的值，不会引入新的空间消耗。因此，出栈操作的空间复杂度是恒定的，不会随着栈的大小而增加。无论栈中存储的元素数量有多少，出栈操作只需要常数额外空间。

2.3 栈的其他操作

1. 栈的大小获取 栈的大小可以通过栈的容量或当前栈中元素的数量来获取。如果使用静态数组实现栈，那么栈的大小通常在创建栈时就确定了，可以通过数组的大小来获取。例如，在 C 语言中，可以使用如下方式获取静态数组实现的栈的大小：

代码语言：javascript复制

#define MAX_SIZE 100  // 栈的最大容量
int stackSize = MAX_SIZE;  // 栈的大小为最大容量

如果使用动态数组或链表实现栈，那么栈的大小可以通过统计栈中当前元素的数量来获取。通常，栈会维护一个变量来记录栈中元素的数量。例如，在 C 语言中，可以使用如下方式获取动态数组或链表实现的栈的大小：

代码语言：javascript复制

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

int stackSize = stack.top   1;  // 栈的大小为栈顶指针加1

上述代码中，我们通过 stack.top 获取栈顶指针，然后加1得到栈的大小。

Tip：栈的大小可能会受到实际内存或资源的限制，例如静态数组实现的栈受到数组的大小限制，动态数组实现的栈受到可用内存的限制，链表实现的栈受到系统内存的限制。因此，在使用栈时要注意避免栈溢出或内存溢出的情况。

1. 栈是否为空判断 栈是否为空可以通过检查栈顶指针来判断。在大多数栈的实现中，栈顶指针的初始值通常被设置为一个特殊的值，表示栈为空。常见的做法是将栈顶指针初始化为 -1，表示栈为空。通过检查栈顶指针的值，我们可以确定栈是否为空。如果栈顶指针为 -1，则表示栈为空；否则，栈中至少有一个元素。 以下是一个示例的 C 语言代码，用于判断栈是否为空：

代码语言：javascript复制

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

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

在上述代码中，isEmpty 函数用于判断栈是否为空。如果栈顶指针 stack->top 的值为 -1，则返回 1 表示栈为空；否则，返回 0 表示栈不为空。

Tip：栈是否为空的判断应该在进行栈操作之前，以确保在空栈上执行出栈操作或访问栈顶元素时不会发生错误。

1. 栈顶元素获取 要获取栈顶元素，我们只需要访问栈顶指针所指向的位置的元素即可。在栈的常规实现中，栈顶指针指向栈顶元素的位置。通过访问该位置的元素，我们可以获取栈顶元素的值。 以下是一个示例的 C 语言代码，用于获取栈顶元素：

代码语言：javascript复制

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

// 获取栈顶元素
int top(Stack* stack) {
    if (stack->top == -1) {
        printf("Error: Stack is empty.n");
        return -1;  // 返回一个错误值
    }
    return stack->data[stack->top];
}

在上述代码中，top 函数用于获取栈顶元素。如果栈顶指针 stack->top 的值为 -1，则表示栈为空，无法获取栈顶元素，会输出错误信息并返回一个错误值（这里返回 -1）；否则，返回栈顶指针所指向位置的元素的值。

三、队列的基本概念和特点

3.1 队列的定义和特点

队列是一种常见的数据结构，它一种线性数据结构，可以通过一端（称为队尾）添加元素，通过另一端（称为队头）删除元素（先进先出FIFO原则）。新元素被添加到队尾，而元素的删除操作总是从队头进行。它的特点如下：

1. 先进先出（FIFO）：队列中先加入的元素先被处理，后加入的元素后被处理，保持元素的顺序性
2. 有限容量：队列的容量可以是有限的，即只能容纳一定数量的元素。

3.2 队列的实现方式

队列可以通过不同的实现方式来实现，常见的实现方式有以下两种：

1. 使用数组：
   • 使用数组作为底层数据结构来存储队列元素。
   • 使用两个指针，一个指向队头，一个指向队尾，来标记队列中元素的位置。
   • 入队操作时，将新元素添加到队尾，同时更新队尾指针。
   • 出队操作时，从队头删除元素，同时更新队头指针。
   • 这种实现方式简单直观，但在队列长度变化较大时可能会浪费空间。
2. 使用链表：
   • 使用链表作为底层数据结构来存储队列元素。
   • 每个链表节点包含一个元素和指向下一个节点的指针。
   • 使用两个指针，一个指向队头节点，一个指向队尾节点，来标记队列中元素的位置。
   • 入队操作时，创建一个新的节点，并将其添加到链表末尾（队尾），同时更新队尾指针。
   • 出队操作时，删除链表头节点（队头），同时更新队头指针。
   • 这种实现方式可以动态调整队列长度，不会浪费空间，但需要额外的指针存储节点间的连接关系。

Tip：无论是使用数组还是链表实现队列，都需要注意处理边界情况，如空队列或满队列的判断。此外，还可以使用循环队列等高级实现方式来优化队列的性能和空间利用率。

3.3 队列的应用场景

队列在计算机科学和软件开发中有许多应用场景，下面是一些常见的队列应用场景：

1. 系统任务调度：操作系统中的任务调度器可以使用队列来管理待执行的任务。任务被添加到队列中，并按照队列的先进先出顺序执行。
2. 缓冲区管理：在计算机网络和数据通信中，队列常用于管理缓冲区。数据包到达时先进入队列，然后按照顺序从队列中取出进行处理。
3. 消息传递系统：队列常被用于实现消息传递系统，其中消息发送者将消息放入队列，而消息接收者从队列中获取消息进行处理。
4. 并发编程：在多线程或多进程编程中，队列可以作为线程或进程之间的通信机制，用于传递数据或任务。
5. 打印任务管理：打印队列是一种常见的队列应用场景。多个打印任务按照先后顺序排队等待执行。
6. 网络请求管理：在服务器端开发中，队列可用于管理网络请求。每个请求被添加到队列中，服务器按照队列顺序逐个处理请求。
7. 数据结构算法：队列是一些经典算法的基础数据结构，如广度优先搜索（BFS）、迷宫求解、循环队列等。

四、队列的操作和复杂度分析

4.1 入队操作

1. 入队操作的实现 入队操作用于将元素添加到队列中，以下是一个示例的 C 语言代码实现：

代码语言：javascript复制

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];  // 存储数据的数组
    int front;           // 队头指针
    int rear;            // 队尾指针
} Queue;

// 入队操作
void enqueue(Queue* queue, int element) {
    if (queue->rear == MAX_SIZE - 1) {
        printf("Error: Queue is full.n");
        return;
    }
    queue->rear  ;
    queue->data[queue->rear] = element;
}

在上述代码中，enqueue 函数用于将元素添加到队列中。首先，我们检查队列是否已满，即队尾指针 queue->rear 是否达到了数组的最大索引（MAX_SIZE - 1）。如果队列已满，则输出错误信息并返回；否则，将新元素添加到队尾指针所指向的位置，并更新队尾指针。

1. 入队操作的时间复杂度 入队操作的时间复杂度是 O(1)。无论队列的大小如何，入队操作只涉及对队尾指针的更新以及对数组中指定位置的赋值操作。因此，入队操作的时间复杂度是常数级别的，与队列中元素的数量无关。无论队列中有多少个元素，入队操作所需的时间都是相同的，即 O(1)。
2. 入队操作的空间复杂度 入队操作的空间复杂度是 O(1)。在入队操作中，只需要额外存储一个元素，并没有随着队列大小的增长而增加额外的空间开销。无论队列中有多少个元素，入队操作所需的额外空间都是固定的，即 O(1)。因此，入队操作的空间复杂度是常数级别的。

4.2 出队操作

1. 出队操作的实现 出队操作用于从队列中删除并返回队头元素，以下是一个示例的 C 语言代码实现：

代码语言：javascript复制

int dequeue(Queue* queue) {
    if (queue->front > queue->rear) {
        printf("Error: Queue is empty.n");
        return -1;  // 返回一个表示错误的值
    }
    int element = queue->data[queue->front];
    queue->front  ;
    return element;
}

在上述代码中，dequeue 函数用于执行出队操作。首先，我们检查队列是否为空，即队头指针 queue->front 是否超过了队尾指针 queue->rear。如果队列为空，则输出错误信息并返回一个表示错误的值（在此示例中为 -1）；否则，将队头指针所指向的元素作为出队元素保存，然后将队头指针向后移动一位，并返回出队元素。

1. 出队操作的时间复杂度 出队操作的时间复杂度是 O(1)。无论队列中有多少个元素，出队操作只涉及对队头指针的更新以及对数组中指定位置的访问操作。因此，出队操作的时间复杂度是常数级别的，与队列中元素的数量无关。无论队列中有多少个元素，出队操作所需的时间都是相同的，即 O(1)。
2. 出队操作的空间复杂度 出队操作的空间复杂度是 O(1)。在出队操作中，并没有引入额外的空间开销。出队操作只涉及对队头指针的更新，不会随着队列大小的增长而增加额外的空间占用。因此，出队操作的空间复杂度是常数级别的，即 O(1)。无论队列中有多少个元素，出队操作所需的额外空间都是固定的。

4.3 队列的其他操作

1. 队列的大小获取 要获取队列的大小，可以定义一个函数来返回队列中元素的数量。以下是一个示例的 C 语言代码实现：

代码语言：javascript复制

int getSize(Queue* queue) {
    return queue->rear - queue->front   1;
}

在上述代码中，getSize 函数用于获取队列的大小。通过计算队尾指针 queue->rear 和队头指针 queue->front 之间的差值，再加上 1，即可得到队列中元素的数量。返回该数量即可。

Tip：上述代码假定队列的合法性已经在其他地方进行了检查，即队头指针不会超过队尾指针，否则可能会导致错误的结果。

1. 队列是否为空判断 要判断队列是否为空，可以定义一个函数来检查队列的状态并返回相应的结果。以下是一个示例的 C 语言代码实现：

代码语言：javascript复制

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

在上述代码中，isEmpty 函数用于判断队列是否为空。如果队头指针 queue->front 大于队尾指针 queue->rear，则说明队列中没有元素，返回一个非零值表示队列为空；否则，返回零表示队列不为空。

1. 队首元素获取 要获取队列的队首元素，可以定义一个函数来返回队列中队头指针所指向的元素值。以下是一个示例的 C 语言代码实现：

代码语言：javascript复制

int getFront(Queue* queue) {
    if (isEmpty(queue)) {
        printf("Error: Queue is empty.n");
        return -1;  // 返回一个表示错误的值
    }
    return queue->data[queue->front];
}

在上述代码中，getFront 函数用于获取队列的队首元素。首先，我们通过调用 isEmpty 函数检查队列是否为空，如果队列为空，则输出错误信息并返回一个表示错误的值（在此示例中为 -1）；否则，直接返回队头指针 queue->front 所指向的元素值。

五、栈和队列的经典面试题

题目 1: 括号匹配

给定一个字符串，包含若干个括号（包括圆括号、方括号和花括号），判断括号的匹配是否正确。例如，“{[()()]}” 是一个正确的匹配，而 “{[(])}” 是一个错误的匹配。

讲解：这道题可以使用栈来解决。遍历字符串的每个字符，如果遇到左括号，则将其入栈；如果遇到右括号，则判断栈顶元素是否与该右括号匹配，如果匹配则将栈顶元素出栈，否则返回错误。最后，如果栈为空，则表示括号匹配正确。

C 语言代码示例：

代码语言：javascript复制

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

#define MAX_SIZE 100

bool isMatching(char left, char right) {
    if ((left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}')) {
        return true;
    }
    return false;
}

bool isValidParentheses(char* s) {
    int len = strlen(s);
    char stack[MAX_SIZE];
    int top = -1;

    for (int i = 0; i < len; i  ) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            stack[  top] = s[i];
        } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
            if (top == -1 || !isMatching(stack[top], s[i])) {
                return false;
            }
            top--;
        }
    }

    return top == -1;
}

int main() {
    char s[MAX_SIZE];
    printf("请输入括号字符串: ");
    scanf("%s", s);
    bool isValid = isValidParentheses(s);
    if (isValid) {
        printf("括号匹配正确n");
    } else {
        printf("括号匹配错误n");
    }
    return 0;
}

题目 2: 求解栈中的最小元素

设计一个支持 push、pop、top 操作，并能在常数时间内返回栈中的最小元素的栈。

讲解：这道题可以使用两个栈来实现，一个栈用于存储原始数据，另一个栈用于存储当前栈中的最小元素。每次 push 操作时，如果新元素小于等于当前最小元素栈的栈顶元素，则将新元素同时入栈到两个栈中；pop 操作时，同时将两个栈的栈顶元素出栈。

C 语言代码示例：

代码语言：javascript复制

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];  // 存储原始数据的栈
    int minStack[MAX_SIZE];  // 存储最小元素的栈
    int top;  // 栈顶指针
} MinStack;

void push(MinStack* stack,

 int val) {
    stack->data[  stack->top] = val;
    if (stack->top == 0 || val <= stack->minStack[stack->top - 1]) {
        stack->minStack[stack->top] = val;
    } else {
        stack->minStack[stack->top] = stack->minStack[stack->top - 1];
    }
}

void pop(MinStack* stack) {
    if (stack->top >= 0) {
        stack->top--;
    }
}

int top(MinStack* stack) {
    if (stack->top >= 0) {
        return stack->data[stack->top];
    }
    return INT_MIN;
}

int getMin(MinStack* stack) {
    if (stack->top >= 0) {
        return stack->minStack[stack->top];
    }
    return INT_MIN;
}

int main() {
    MinStack stack;
    stack.top = -1;

    push(&stack, 5);
    push(&stack, 3);
    push(&stack, 7);
    push(&stack, 2);
    printf("当前栈中的最小元素为: %dn", getMin(&stack));
    pop(&stack);
    pop(&stack);
    printf("当前栈中的最小元素为: %dn", getMin(&stack));
    return 0;
}

题目 3: 用队列实现栈

使用队列实现一个栈的下列操作：push、pop、top 和 empty。

讲解：这道题可以使用两个队列来实现一个栈。当进行 push 操作时，将元素入队到一个非空队列中；当进行 pop 操作时，将非空队列中的元素依次出队并入队到另一个空队列中，直到非空队列中只剩下一个元素，将该元素出队即为栈的顶部元素；而 top 操作则直接返回非空队列的队尾元素；empty 操作则判断两个队列是否都为空。

C 语言代码示例：

代码语言：javascript复制

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

typedef struct {
    int* queue1;
    int* queue2;
    int top;
    int size;
} MyStack;

MyStack* createStack(int size) {
    MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
    stack->queue1 = (int*)malloc(size * sizeof(int));
    stack->queue2 = (int*)malloc(size * sizeof(int));
    stack->top = -1;
    stack->size = size;
    return stack;
}

void push(MyStack* stack, int val) {
    if (stack->top < stack->size - 1) {
        stack->queue1[  stack->top] = val;
    }
}

void swapQueues(MyStack* stack) {
    int* temp = stack->queue1;
    stack->queue1 = stack->queue2;
    stack->queue2 = temp;
}

void adjustQueue(MyStack* stack) {
    while (stack->top > 0) {
        stack->queue2[  stack->top] = stack->queue1[stack->top - 1];
    }
}

void pop(MyStack* stack) {
    if (stack->top >= 0) {
        adjustQueue(stack);
        swapQueues(stack);
        stack->top--;
    }
}



int top(MyStack* stack) {
    if (stack->top >= 0) {
        return stack->queue1[stack->top];
    }
    return -1;
}

bool isEmpty(MyStack* stack) {
    return stack->top == -1;
}

int main() {
    MyStack* stack = createStack(100);
    push(stack, 5);
    push(stack, 3);
    push(stack, 7);
    push(stack, 2);

    printf("栈顶元素为: %dn", top(stack));

    pop(stack);

    printf("栈顶元素为: %dn", top(stack));

    while (!isEmpty(stack)) {
        pop(stack);
    }

    printf("栈是否为空: %dn", isEmpty(stack));

    return 0;
}

以上是三道经典的栈和队列面试题，通过这些题目的讲解和代码实现，可以加深对栈和队列的理解，并且熟悉它们的常见应用。

六、总结

栈和队列是常见的数据结构，在编程和算法中起着重要的作用。它们具有不同的特点和应用场景。下面是栈和队列的总结：

栈（Stack）是一种后进先出（LIFO）的数据结构，类似于现实生活中的一摞盘子。栈的特点包括：

• 只允许在栈顶进行插入和删除操作，即入栈（push）和出栈（pop）操作。
• 栈顶是最后一个插入的元素，栈底是最先插入的元素。
• 栈的插入和删除操作都是常数时间复杂度（O(1)）。
• 栈的大小是有限的，当栈满时无法再插入新元素，称为栈溢出。

栈的应用场景包括：

• 表达式求值：使用栈可以方便地进行中缀表达式转换为后缀表达式，并计算表达式的值。
• 函数调用：函数调用时，每次进入一个新函数，需要保存上一个函数的状态，可以使用栈来实现函数的嵌套调用。
• 括号匹配：栈可以用于检查括号是否匹配的问题，例如判断一个字符串中的括号是否完全匹配。

队列（Queue）是一种先进先出（FIFO）的数据结构，类似于现实生活中排队的概念。队列的特点包括：

• 元素在队列尾部进行插入（入队，enqueue）操作，而在队列头部进行删除（出队，dequeue）操作。
• 队列头部是第一个插入的元素，队列尾部是最后一个插入的元素。
• 队列的插入和删除操作都是常数时间复杂度（O(1)）。
• 队列的大小是有限的，当队列满时无法再插入新元素，称为队列溢出。

队列的应用场景包括：

• 广度优先搜索（BFS）：在图或树的遍历中，使用队列来按层次进行节点的遍历。
• 缓冲区管理：当有大量的任务需要处理时，可以使用队列作为任务的缓冲区，按顺序进行处理。
• 消息传递：多线程或多进程环境下，使用队列可以实现线程或进程之间的安全通信。

根据需求选择合适的数据结构：

• 如果需要后进先出的特性，可以选择使用栈。
• 如果需要先进先出的特性，可以选择使用队列。
• 如果需要在两端进行插入和删除操作，可以选择使用双端队列。
• 如果需要按优先级进行插入和删除操作，可以选择使用优先队列。

队列 基础 数据结构与算法 数组 指针

0 人点赞