您现在的位置是：首页 >技术交流 >栈和队列：理解与使用网站首页技术交流

栈和队列：理解与使用

创意程序员 2024-06-17 10:19:05
简介栈和队列：理解与使用

目录

栈

顺序栈结构

链式栈结构

中缀表达式和后缀表达式

顺序栈四则运算

链式栈四则运算

队列

顺序队列结构

链式队列结构

总结

栈和队列是计算机科学中常见的数据结构，它们都是一种线性数据结构，可以对元素进行快速的插入、删除和查找操作。栈和队列都可以用于各种不同的应用场景，不过它们的使用方式和特点有所不同。

栈

首先，让我们来了解一下栈的概念。栈是一种具有“后进先出”（Last In First Out，LIFO）特性的数据结构，如图：

 

只有栈顶元素是可以访问的。新加入的元素会直接放在栈顶，而每次需要访问栈元素时，都会从栈顶开始弹出元素。栈常用于实现函数调用、表达式求值、括号匹配等场景。通常使用 push() 方法将一个元素压入栈中，使用 pop() 方法将栈顶元素弹出。

栈结构包括两类：顺序栈结构和链式栈结构。

顺序栈结构

顺序栈结构使用一组地址连续的内存单元依次保存栈中的数据。在程序中，可以定义一个指定大小的结构数组作为栈，定义一个变量top保存栈顶序号，初始为-1表示空栈。顺序栈的定义和常见操作及代码如下：

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

typedef struct {
    char *data;
    int top;
    int maxSize;
} Stack;

// 初始化栈
void initStack(Stack *stack, int maxSize) {
    stack->data = (char *)malloc(sizeof(char) * maxSize);
    stack->top = -1;
    stack->maxSize = maxSize;
}

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

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

// 入栈
void push(Stack *stack, char element) {
    if (isFull(stack)) {
        printf("栈已满，无法入栈！
");
        return;
    }
    stack->data[++stack->top] = element;
}

// 出栈
char pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("栈已空，无法出栈！
");
        return 0;
    }
    return stack->data[stack->top--];
}

// 读取栈顶元素
char peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("栈已空，无法读取栈顶元素！
");
        return 0;
    }
    return stack->data[stack->top];
}

// 清空栈
void clear(Stack *stack) {
    stack->top = -1;
}

// 销毁栈
void destroy(Stack *stack) {
    free(stack->data);
    stack->data = NULL;
    stack->top = -1;
    stack->maxSize = 0;
}

链式栈结构

链式栈结构使用链表保存栈元素值，链表头部为栈顶，链表尾部为栈底。链式栈的定义和常见操作及代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DATA_SIZE 10

// 链式栈结点结构
typedef struct Node {
    char data[DATA_SIZE];
    struct Node *next;
} Node, *LinkedStack;

// 初始化栈
void initStack(LinkedStack *top) {
    *top = NULL;
}

// 判断栈是否为空
int isEmpty(LinkedStack *top) {
    return *top == NULL;
}

// 入栈
void push(LinkedStack *top, char *data) {
    //printf("push: %s ", data);
    Node *node = (Node *)malloc(sizeof(Node));
    strcpy(node->data, data);
    node->next = *top;
    *top = node;
}

// 出栈
void pop(LinkedStack *top, char *data) {
    if (isEmpty(top)) {
        printf("栈已空，无法出栈！
");
        return;
    }
    Node *node = *top;
    *top = node->next;
    strcpy(data, node->data);
    //printf("pop: %s ", data);
    free(node);
}

// 读取栈顶元素
char* peek(LinkedStack *top) {
    if (isEmpty(top)) {
        printf("栈已空，无法读取栈顶元素！
");
        return NULL;
    }
    return (*top)->data;
}

// 清空栈
void clear(LinkedStack *top) {
    while (!isEmpty(top)) {
        Node *node = *top;
        *top = node->next;
        free(node);
    }
}

// 销毁栈
void destroy(LinkedStack *top) {
    clear(top);
}

// 打印栈
void print(LinkedStack *top) {
    if (isEmpty(top)) {
        printf("栈已空，无法打印！
");
        return;
    }
    printf("栈中元素：");
    Node *node = *top;
    while (node != NULL) {
        printf("%s ", node->data);
        node = node->next;
    }
    printf("
");
}

中缀表达式和后缀表达式

前提提到栈可以用于实现表达式求值，在展示这个案例前，我们先了解一下表达式求值的应用过程。我们平时使用的表达式如“2*(5-1)”是中缀表达式，使用括号来明确运算符的优先级和结合性。后缀表达式（也称为逆波兰表达式），是一种将运算符放置在操作数之后的表示方法，将前面的中缀表达式转换为后缀表达式就是“251-*”。将中缀表达式转换为后缀表达式，可以使表达式更容易计算，而不需要考虑括号和运算符优先级。将中缀表达式 "2*(5-1)" 转换为后缀表达式的过程如下：

  1.  从左到右遍历中缀表达式 "2*(5-1)"；
  2. 遇到操作数 2，将其添加到后缀表达式列表中；
  3. 遇到运算符 *，将其入栈；
  4. 遇到左括号 (，将其入栈；
  5. 遇到操作数 5，将其添加到后缀表达式列表中；
  6. 遇到运算符 -，与栈顶运算符 * 比较，栈顶优先级较低，将 - 入栈（如果栈顶运算符优先级高，则弹出并添加到后缀表达式列表中）。
  7. 遇到操作数 1，将其添加到后缀表达式列表中；
  8. 遇到右括号 )，将栈顶的运算符 - * 依次弹出并添加到后缀表达式列表中，直到遇到左括号 ( 时停止，左括号丢弃；
  9. 中缀表达式遍历完成后，如果栈中还有剩余运算符，则将栈中剩余的运算符依次弹出并添加到后缀表达式列表中。

处理后缀表达式求值的过程则相对简单，因为不需要考虑括号和运算符优先级：

  1. 从左到右遍历后缀表达式中的每个元素；
  2. 如果遇到操作数，将其压入栈中；
  3. 如果遇到运算符，从栈中弹出 2 个操作数，根据运算符进行计算，并将结果压入栈中；
  4. 重复步骤 2 和步骤 3，直到遍历完整个后缀表达式。
  5. 最后，栈中将只剩下一个元素，即为最终的计算结果。

顺序栈四则运算

以下为使用顺序栈结构进行四则运算的例子：

#define MAX_SIZE 100

// 判断是否为运算符
int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 判断运算符优先级
int priority(char c) {
    if (c == '+' || c == '-') {
        return 1;
    } else if (c == '*' || c == '/') {
        return 2;
    }
    return 0;
}

// 中缀表达式转后缀表达式
void infixToPostfix(char *infix, char *postfix) {
    Stack stack;
    initStack(&stack, strlen(infix));
    int i = 0, j = 0;
    while (infix[i] != '') {
        // 如果是负数，补0变成0-某数
        if (infix[i] == '-' && (i == 0 || infix[i - 1] == '(')) {
            postfix[j++] = '0';
        }

        if (infix[i] == '(') {
            // 如果是左括号，直接入栈
            push(&stack, infix[i]);
        } else if (infix[i] == ')') {
            // 如果是右括号，弹出栈中的元素放入后缀表达式中，直到遇到左括号
            while (peek(&stack) != '(') {
                postfix[j++] = pop(&stack);
            }
            // 弹出左括号，但不放入后缀表达式中
            pop(&stack);
        } else if (isOperator(infix[i])) {
            // 如果是运算符，弹出栈中优先级大于等于当前运算符的元素放入后缀表达式中
            while (!isEmpty(&stack) && priority(peek(&stack)) >= priority(infix[i])) {
                postfix[j++] = pop(&stack);
            }
            // 当前运算符入栈
            push(&stack, infix[i]);
        } else {
            postfix[j++] = infix[i];
        }
        i++;
    }
    // 将栈中剩余的元素放入后缀表达式中
    while (!isEmpty(&stack)) {
        postfix[j++] = pop(&stack);
    }
    postfix[j] = '';
    destroy(&stack);
}

// 计算后缀表达式
int calculate(char *postfix) {
    Stack stack;
    initStack(&stack, strlen(postfix));
    int i = 0;
    while (postfix[i] != '') {
        if (isOperator(postfix[i])) {
            // 如果是运算符，弹出栈中的两个元素进行运算，将结果入栈
            int a = pop(&stack) - '0';
            int b = pop(&stack) - '0';
            int result;
            switch (postfix[i]) {
                case '+':
                    result = b + a;
                    break;
                case '-':
                    result = b - a;
                    break;
                case '*':
                    result = b * a;
                    break;
                case '/':
                    result = b / a;
                    break;
            }
            push(&stack, result + '0');
        } else {
            push(&stack, postfix[i]);
        }
        i++;
    }
    int result = pop(&stack) - '0';
    destroy(&stack);
    return result;
}

int main() {
    char infix[MAX_SIZE];
    printf("请输入中缀表达式：");
    scanf("%s", infix);
    printf("中缀表达式：%s
", infix);
    char postfix[strlen(infix)];
    infixToPostfix(infix, postfix);
    printf("后缀表达式：%s
", postfix);
    printf("计算结果：%d
", calculate(postfix));
    return 0;
}

链式栈四则运算

以下为使用链式栈结构进行四则运算的例子：

#include <string.h>
#include "LinkedStack.c"
#define MAX_SIZE 100

// 判断是否为运算符
int isOperator(char *str) {
    if (strlen(str) > 1) {
        return 0;
    }
    char c = str[0];
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 判断运算符优先级
int priority(char *str) {
    char c = str[0];
    if (c == '+' || c == '-') {
        return 1;
    } else if (c == '*' || c == '/') {
        return 2;
    }
    return 0;
}

// 拼接字符
void append(char *str, char c) {
    int len = strlen(str);
    str[len] = c;
    str[len + 1] = '';
}

// 字符拷贝
void set(char *str, char c) {
    str[0] = c;
    str[1] = '';
}

// 中缀表达式转后缀表达式
int infixToPostfix(char *infix, char postfix[][DATA_SIZE]) {
    LinkedStack stack;
    initStack(&stack);
    int i = 0, j = 0, isOperand = 0;
    char data[DATA_SIZE], oper[1];
    while (infix[i] != '') {
        set(oper, infix[i]); //当前操作符/操作数
        // 如果是负数
        if (infix[i] == '-' && (i == 0 || infix[i - 1] == '(')) {
            set(postfix[j++], '-');
            isOperand = 1;
        } else {
            if (infix[i] == '(') {
                // 如果是左括号，直接入栈
                isOperand = 0;
                set(data, infix[i]);
                push(&stack, data);
            } else if (infix[i] == ')') {
                // 如果是右括号，弹出栈中的元素放入后缀表达式中，直到遇到左括号
                isOperand = 0;
                while (peek(&stack)[0] != '(') {
                    pop(&stack, data);
                    strcpy(postfix[j++], data);
                }
                // 弹出左括号，但不放入后缀表达式中
                pop(&stack, data);
            } else if (isOperator(oper)) {
                // 如果是运算符，弹出栈中优先级大于等于当前运算符的元素放入后缀表达式中
                isOperand = 0;
                while (!isEmpty(&stack) && priority(peek(&stack)) >= priority(&infix[i])) {
                    pop(&stack, data);
                    strcpy(postfix[j++], data);
                }
                // 当前运算符入栈
                set(data, infix[i]);
                push(&stack, data);
            } else {
                if (isOperand) {
                    // 该数字是前面的一部分，拼接到后缀表达式最后一个数字中
                    append(postfix[j - 1], infix[i]);
                } else {
                    // 该数字是一个新的数字，直接放到后缀表达式中
                    set(postfix[j++], infix[i]);
                    isOperand = 1;
                }
            }
        }
        i++;
    }
    // 将栈中剩余的元素放入后缀表达式中
    while (!isEmpty(&stack)) {
        pop(&stack, data);
        strcpy(postfix[j++], data);
    }
    postfix[j][0] = '';
    destroy(&stack);
    return j;
}

// 计算后缀表达式
int calculate(char postfix[][DATA_SIZE], int size) {
    LinkedStack stack;
    initStack(&stack);
    char data[DATA_SIZE];
    for (int i = 0; i < size; i++) {
        if (isOperator(postfix[i])) {
            // 如果是运算符，弹出栈中的两个元素进行运算，将结果入栈
            pop(&stack, data);
            int a = atoi(data);
            pop(&stack, data);
            int b = atoi(data);
            int result;
            switch (postfix[i][0]) {
                case '+':
                    result = b + a;
                    break;
                case '-':
                    result = b - a;
                    break;
                case '*':
                    result = b * a;
                    break;
                case '/':
                    result = b / a;
                    break;
            }
            itoa(result, data, 10);
            push(&stack, data);
        } else {
            push(&stack, postfix[i]);
        }
    }
    pop(&stack, data);
    destroy(&stack);
    return atoi(data);
}

int main() {
    char infix[MAX_SIZE];
    printf("请输入中缀表达式：");
    scanf("%s", infix);
    printf("中缀表达式：%s
", infix);
    char postfix[strlen(infix)][DATA_SIZE];
    int len = infixToPostfix(infix, postfix); //有负数的情况下，len会比实际的多1

    // 打印后缀表达式
    printf("后缀表达式(%d)：", len);
    for (int i = 0; i < len; i++) {
        printf(" %s", postfix[i]);
    }
    printf("
");

    printf("计算结果：%d
", calculate(postfix, len));
    return 0;
}

大家可以比较上述两个例子，除了所使用的栈结构不同，还有什么差异？

队列

接下来，我们来了解一下队列的概念。队列是一种具有“先进先出”（First In First Out，FIFO）特性的数据结构，如图：

 

新加入的元素会先放在队尾，而每次需要访问队列元素时，都会从队头开始取出元素，因此队列的操作是双向的。队列常用于实现任务调度、缓冲区管理、广度优先搜索等场景。

队列结构也包括两类：顺序队列结构和链式队列结构。

顺序队列结构

顺序队列结构使用一组地址连续的内存单元依次保存队列中的数据。在程序中，可以定义一个指定大小的结构数组作为队列。

链式队列结构

链式队列结构使用链表保存队列元素值，在链表一端只能进行取出/删除操作，称为队头，在链表的另一端只能进行插入操作，称为队尾。链式队列的常见操作及代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DATA_SIZE 10

// 链式队列结点结构
typedef struct Node {
    char data[DATA_SIZE];
    struct Node *next;
} Node;

// 链式队列结构
typedef struct LinkedQueue {
    Node *front;
    Node *rear;
} LinkedQueue;

// 初始化队列
void initQueue(LinkedQueue *queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 判断队列是否为空
int isEmpty(LinkedQueue *queue) {
    return queue->front == NULL;
}

// 入队
void enqueue(LinkedQueue *queue, char *data) {
    printf("enqueue: %s
", data);
    Node *node = (Node *)malloc(sizeof(Node));
    strcpy(node->data, data);
    node->next = NULL;
    if (isEmpty(queue)) {
        queue->front = node;
        queue->rear = node;
    } else {
        queue->rear->next = node;
        queue->rear = node;
    }
}

// 出队
void dequeue(LinkedQueue *queue, char *data) {
    if (isEmpty(queue)) {
        printf("队列已空，无法出队！
");
        return;
    }
    printf("dequeue: %s
", data);
    Node *node = queue->front;
    queue->front = node->next;
    strcpy(data, node->data);
    free(node);
}

// 读取队头元素
char* peek(LinkedQueue *queue) {
    if (isEmpty(queue)) {
        printf("队列已空，无法读取队头元素！
");
        return NULL;
    }
    return queue->front->data;
}

// 清空队列
void clear(LinkedQueue *queue) {
    Node *p, *node = queue->front;
    while (p = node) {
        free(p);
        node = node->next;
    }
    queue->front = NULL;
    queue->rear = NULL;
}

总结

需要注意的是，虽然栈和队列都可以用于各种不同的应用场景，但是在使用时需要注意一些细节问题。栈是一种后进先出（LIFO）的数据结构，数据项按照后进先出的顺序存储和访问。最后进入栈的元素是第一个被访问和移除的元素。队列是一种先进先出（FIFO）的数据结构，数据项按照先进先出的顺序存储和访问。最先进入队列的元素是第一个被访问和移除的元素。

栈和队列是计算机科学中重要的数据结构之一，它们都有着广泛的应用场景。了解栈和队列的概念以及使用方法可以帮助我们更好地理解和使用这些数据结构。

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐