C语言对栈的实现基本操作

下面我将详细讲解“C语言对栈的实现基本操作”的完整攻略。

栈的基本概念

栈是一种数据结构，是一种只允许在一端进行插入删除操作的线性表，这一端称为栈顶，另一端称为栈底。遵循后进先出（LIFO）的原则，即最后插入的元素最先弹出。

栈的操作

栈的基本操作包括初始化、入栈、出栈、获取栈顶元素以及判断栈是否为空。下面分别进行详细介绍：

初始化栈

初始化栈即为给栈分配空间，初始化栈顶和栈底指针。C 语言中用结构体定义一个栈，初始化时使用 malloc 分配结构体大小的内存，并将栈顶指针和栈底指针置为空。

#include <stdlib.h>

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int top; // 栈顶指针
} Stack;

void init(Stack *s) {
    s=(Stack*)malloc(sizeof(Stack));
    s->top=-1;
}

入栈

入栈即在栈顶插入一个元素。当栈未满时，插入元素，并将栈顶指针指向该元素；若栈已满，则输出提示信息。

void push(Stack *s, int value) {
    if(s->top==MAXSIZE-1) {
        printf("Stack overflow.");
        return;
    }
    s->data[++s->top]=value;
}

出栈

出栈即弹出栈顶元素。当栈非空时，弹出栈顶元素并将栈顶指针下移一个位置；若栈为空，则输出提示信息。

int pop(Stack *s) {
    if(s->top==-1) {
        printf("Stack underflow.");
        return -1;
    }
    return s->data[s->top--];
}

获取栈顶元素

获取栈顶元素即查看栈顶元素的值。当栈非空时，返回栈顶元素的值；若栈为空，则输出提示信息。

int top(Stack *s) {
    if(s->top==-1) {
        printf("Stack underflow.");
        return -1;
    }
    return s->data[s->top];
}

判断栈是否为空

判断栈是否为空即查看栈顶指针是否为 -1。当栈为空时，返回 1；否则返回 0。

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

示例说明

示例一

假设当前栈中元素为 {1, 2, 3, 4}，现需将栈中全部元素出栈并输出。则代码如下：

#include <stdio.h>

int main() {
    Stack s;
    init(&s);
    int num;
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    push(&s, 4);
    while(!isEmpty(&s)) {
        num=pop(&s);
        printf("%d ",num);
    }
    return 0;
}

结果输出为：

4 3 2 1

示例二

现在需要判断一个字符串中的括号是否匹配。例如，字符串 "((()))" 是合法的，而字符串 "(()" 是不合法的。则代码如下：

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

int main() {
    Stack s;
    init(&s);
    char str[50];
    int i,flag=1;
    printf("请输入要判断的字符串：");
    scanf("%s",str);
    for(i=0;i<strlen(str);i++) {
        if(str[i]=='(') {
            push(&s,i);
        }
        if(str[i]==')'&&!isEmpty(&s)) {
            pop(&s);
        }
        else if(str[i]==')'&&isEmpty(&s)) {
            flag=0;
            break;
        }
    }
    if(!isEmpty(&s)) {
        flag=0;
    }
    if(flag) {
        printf("该字符串是合法的.");
    }
    else {
        printf("该字符串是不合法的.");
    }
    return 0;
}

运行结果为：

请输入要判断的字符串：((()))
该字符串是合法的.

请输入要判断的字符串：(())
该字符串是不合法的.