博客

C语言用指针支持栈

  • Post category:C

C语言用指针支持栈是一种利用指针实现栈数据结构的方法，实现简单、易于理解，在C语言中广泛应用。本攻略将详细介绍如何使用指针实现栈数据结构，并提供两个示例说明。

什么是栈

栈（Stack）是一种先进后出（LIFO）的数据结构，常用于函数调用、表达式求值等场景。栈包含两个基本操作：压栈（push）和弹栈（pop），以及获取栈顶元素（top）等操作。

用指针实现栈

用指针实现栈，可以采用链表数据结构来表示栈。链表中每个节点包含两个元素：一个是数据元素，一个是指向下一个节点的指针。

定义一个Node节点结构体，用于存储节点数据和指针：

struct Node {
    int data;
    struct Node* next;
};

定义一个栈数据结构，包含指向栈顶节点的指针：

struct Stack {
    struct Node* top;
};

初始化栈：

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

判断栈是否为空：

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

压栈操作：

void push(Stack* stack, int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = value;
    node->next = stack->top;
    stack->top = node;
}

弹栈操作：

int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("cannot pop an empty stack");
        return -1;
    }

    Node* node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);

    return data;
}

获取栈顶元素：

int top(const Stack* stack) {
    if (isEmpty(stack)) {
        printf("the stack is empty");
        return -1;
    }

    return stack->top->data;
}

示例说明

示例一：括号匹配问题

给定一个只包含{、[、(、)、]、}六个字符的字符串，判断其中的括号是否匹配。

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

struct Node {
    char data;
    struct Node* next;
};

struct Stack {
    struct Node* top;
};

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

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

void push(Stack* stack, char value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = value;
    node->next = stack->top;
    stack->top = node;
}

char pop(Stack* stack) {
    if (isEmpty(stack)) {
        return '\0';
    }

    Node* node = stack->top;
    char data = node->data;
    stack->top = node->next;
    free(node);

    return data;
}

char top(const Stack* stack) {
    if (isEmpty(stack)) {
        return '\0';
    }

    return stack->top->data;
}

bool match(char left, char right) {
    return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}');
}

bool isBalanced(const char* str) {
    Stack stack;
    initStack(&stack);

    for (int i = 0; i < strlen(str); i++) {
        char c = str[i];
        if (c == '(' || c == '[' || c == '{') {
            push(&stack, c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (isEmpty(&stack) || !match(top(&stack), c)) {
                return false;
            }
            pop(&stack);
        }
    }

    return isEmpty(&stack);
}

int main() {
    char* str = "{(1 + 2) * [3 - 4]}/5";
    bool result = isBalanced(str);
    printf("%s\n", result ? "Balanced" : "Not Balanced");
    return 0;
}

示例二：二叉树的遍历

前序遍历、中序遍历和后序遍历是二叉树遍历的三种方式，其中前序遍历和后序遍历可以直接用栈来实现。

首先定义二叉树节点结构体：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

前序遍历：

int* preorderTraversal(TreeNode* root, int* returnSize) {
    int* result = (int*)malloc(sizeof(int) * 1000);
    *returnSize = 0;

    Stack stack;
    initStack(&stack);

    if (root != NULL) {
        push(&stack, root);
    }

    while (!isEmpty(&stack)) {
        TreeNode* node = pop(&stack);

        result[(*returnSize)++] = node->val;

        if (node->right != NULL) {
            push(&stack, node->right);
        }

        if (node->left != NULL) {
            push(&stack, node->left);
        }
    }

    return result;
}

后序遍历：

int* postorderTraversal(TreeNode* root, int* returnSize) {
    int* result = (int*)malloc(sizeof(int) * 1000);
    *returnSize = 0;

    Stack stack;
    initStack(&stack);

    if (root != NULL) {
        push(&stack, root);
    }

    while (!isEmpty(&stack)) {
        TreeNode* node = top(&stack);

        if (node->left != NULL && node->left->val != INT_MIN) {
            push(&stack, node->left);
            node->left->val = INT_MIN;
        } else if (node->right != NULL && node->right->val != INT_MIN) {
            push(&stack, node->right);
            node->right->val = INT_MIN;
        } else {
            pop(&stack);
            result[(*returnSize)++] = node->val;
        }
    }

    return result;
}

以上是我使用指针在C语言中实现栈数据结构的方法和两个示例说明，希望对你有所帮助。

Tags: