C语言中判断栈满的方法详解

C语言中判断栈满的方法详解

在C语言中，判断栈是否满的核心观点包括：利用栈的容量和当前栈顶指针进行比较、设置栈容量的上限、编写对应的栈操作函数。其中，利用栈的容量和当前栈顶指针进行比较是最常用的方法。通过定义一个固定大小的数组来实现栈，并使用一个指针来跟踪当前栈顶的位置，如果栈顶指针达到了预定义的最大容量，就可以判断栈已满。

一、栈的基本概念

栈是一种线性数据结构，具有后进先出（LIFO，Last In First Out）的特性。栈的基本操作包括压栈（push）、弹栈（pop）和查看栈顶元素（peek）。由于栈的特殊性质，它在实现递归算法、表达式求值、函数调用等方面具有广泛应用。

二、栈的实现方式

在C语言中，栈通常通过数组和链表两种方式实现。以下将分别介绍这两种实现方式，并讨论如何判断栈是否满。

1. 数组实现栈

通过数组实现栈是一种常见且简单的方式。我们需要定义一个固定大小的数组和一个栈顶指针来跟踪当前栈顶的位置。

#include <stdio.h>
#include <stdbool.h>  
#define MAX_SIZE 100  
typedef struct {  
    int data[MAX_SIZE];  
    int top;  
} Stack;  
// 初始化栈  
void initStack(Stack *s) {  
    s->top = -1;  
}  
// 判断栈是否满  
bool isFull(Stack *s) {  
    return s->top == MAX_SIZE - 1;  
}  
// 压栈操作  
bool push(Stack *s, int value) {  
    if (isFull(s)) {  
        printf("Stack is full!\n");  
        return false;  
    }  
    s->data[++(s->top)] = value;  
    return true;  
}  
// 弹栈操作  
bool pop(Stack *s, int *value) {  
    if (s->top == -1) {  
        printf("Stack is empty!\n");  
        return false;  
    }  
    *value = s->data[(s->top)--];  
    return true;  
}  

在上述代码中，通过定义一个固定大小的数组 data 和一个栈顶指针 top 来实现栈。isFull 函数用于判断栈是否满，如果 top 等于数组的最大索引（MAX_SIZE - 1），则栈已满。

2. 链表实现栈

链表实现栈的方式更加灵活，因为它不需要预定义栈的大小，可以根据需要动态分配内存。

#include <stdio.h>
#include <stdlib.h>  
#include <stdbool.h>  
typedef struct Node {  
    int data;  
    struct Node *next;  
} Node;  
typedef struct {  
    Node *top;  
    int size;  
    int max_size;  
} Stack;  
// 初始化栈  
void initStack(Stack *s, int max_size) {  
    s->top = NULL;  
    s->size = 0;  
    s->max_size = max_size;  
}  
// 判断栈是否满  
bool isFull(Stack *s) {  
    return s->size == s->max_size;  
}  
// 压栈操作  
bool push(Stack *s, int value) {  
    if (isFull(s)) {  
        printf("Stack is full!\n");  
        return false;  
    }  
    Node *newNode = (Node *)malloc(sizeof(Node));  
    if (!newNode) {  
        printf("Memory allocation failed!\n");  
        return false;  
    }  
    newNode->data = value;  
    newNode->next = s->top;  
    s->top = newNode;  
    s->size++;  
    return true;  
}  
// 弹栈操作  
bool pop(Stack *s, int *value) {  
    if (s->top == NULL) {  
        printf("Stack is empty!\n");  
        return false;  
    }  
    Node *temp = s->top;  
    *value = temp->data;  
    s->top = s->top->next;  
    free(temp);  
    s->size--;  
    return true;  
}  

在链表实现方式中，通过链表节点动态分配内存来实现栈。isFull 函数根据当前栈的大小 size 和预定义的最大大小 max_size 来判断栈是否满。

三、栈操作函数的实现

在实现栈的过程中，除了判断栈是否满，还需要实现其他基本操作函数，如压栈、弹栈和查看栈顶元素。以下将详细介绍这些操作函数的实现。

1. 初始化栈

初始化栈是第一步操作，它通常包括设置栈顶指针和其他必要的初始化步骤。

void initStack(Stack *s) {
    s->top = -1; // 数组实现方式  
    // 或者  
    s->top = NULL; // 链表实现方式  
    s->size = 0;  
}  

2. 压栈操作

压栈操作用于将元素添加到栈顶。在数组实现方式中，需要检查栈是否满；在链表实现方式中，需要分配新节点并更新栈顶指针。

bool push(Stack *s, int value) {
    if (isFull(s)) {  
        printf("Stack is full!\n");  
        return false;  
    }  
    // 数组实现方式  
    s->data[++(s->top)] = value;  
    return true;  
    // 链表实现方式  
    Node *newNode = (Node *)malloc(sizeof(Node));  
    if (!newNode) {  
        printf("Memory allocation failed!\n");  
        return false;  
    }  
    newNode->data = value;  
    newNode->next = s->top;  
    s->top = newNode;  
    s->size++;  
    return true;  
}  

3. 弹栈操作

弹栈操作用于移除并返回栈顶元素。在数组实现方式中，直接操作栈顶指针；在链表实现方式中，释放栈顶节点并更新栈顶指针。

bool pop(Stack *s, int *value) {
    if (s->top == -1) { // 数组实现方式  
        printf("Stack is empty!\n");  
        return false;  
    }  
    *value = s->data[(s->top)--];  
    return true;  
    // 链表实现方式  
    if (s->top == NULL) {  
        printf("Stack is empty!\n");  
        return false;  
    }  
    Node *temp = s->top;  
    *value = temp->data;  
    s->top = s->top->next;  
    free(temp);  
    s->size--;  
    return true;  
}  

4. 查看栈顶元素

查看栈顶元素操作用于返回栈顶元素但不移除它。在数组实现方式中，直接返回栈顶指针指向的元素；在链表实现方式中，返回栈顶节点的数据。

int peek(Stack *s) {
    if (s->top == -1) { // 数组实现方式  
        printf("Stack is empty!\n");  
        return -1; // 或者其他错误标志  
    }  
    return s->data[s->top];  
    // 链表实现方式  
    if (s->top == NULL) {  
        printf("Stack is empty!\n");  
        return -1; // 或者其他错误标志  
    }  
    return s->top->data;  
}  

四、栈满的实际应用场景

在实际应用中，判断栈是否满有很多实际的应用场景。例如，在表达式求值中，栈用于保存操作数和操作符；在递归算法中，栈用于保存函数调用的上下文信息。当栈满时，需要处理相应的异常情况，确保程序的稳定性和可靠性。

1. 表达式求值

在计算机科学中，表达式求值是一个经典问题。通过使用栈，可以方便地实现中缀表达式转后缀表达式，并计算后缀表达式的值。

#include <stdio.h>
#include <stdlib.h>  
#include <ctype.h>  
#define MAX_EXPR_SIZE 100  
typedef struct {  
    char data[MAX_EXPR_SIZE];  
    int top;  
} CharStack;  
void initCharStack(CharStack *s) {  
    s->top = -1;  
}  
bool isCharStackFull(CharStack *s) {  
    return s->top == MAX_EXPR_SIZE - 1;  
}  
bool pushChar(CharStack *s, char value) {  
    if (isCharStackFull(s)) {  
        printf("Char Stack is full!\n");  
        return false;  
    }  
    s->data[++(s->top)] = value;  
    return true;  
}  
bool popChar(CharStack *s, char *value) {  
    if (s->top == -1) {  
        printf("Char Stack is empty!\n");  
        return false;  
    }  
    *value = s->data[(s->top)--];  
    return true;  
}  
char peekChar(CharStack *s) {  
    if (s->top == -1) {  
        printf("Char Stack is empty!\n");  
        return '\0'; // 或者其他错误标志  
    }  
    return s->data[s->top];  
}