数据结构（二）——栈及实现、括号匹配

一、栈的概念与特点

  一种特殊的线性表，它的插入和删除运算均在同一端进行。这一端被称为栈顶，另一端为栈底，插入称为进栈，删除称为出栈。有后进先出的性质。栈顶top相当于顺序表中的size，即元素个数。关于顺序表可以参考数据结构（一）——顺序表及实现 。

 

 

 [注]没有a[n]这个元素。n是元素的数量

二、栈的操作及实现

1、结构体定义

2、初始化

3、判断是否为空

4、取得栈顶值

5、入栈操作

6、出栈操作

7、打印栈的内容

1、结构体定义

#define LENGTH 100
#include<stdio.h>
#include<stdlib.h>

typedef char datatype;

typedef struct sequence_stack{
    datatype data[LENGTH];
    int top;
}sequence_stack;

2、初始化

#include"stack.h"
void init_sequence_stack(sequence_stack *st){
    st->top = 0;
}

3、判断是否为空

#include"stack.h"
int is_empty_sequence_stack(sequence_stack *st){
    return (st->top? 0:1);
}

4、取得栈顶值

#include"stack.h"

datatype get_top(sequence_stack *st){
    if(st->top == 0){
        printf("the stack is empty!\n");
        exit(1);
    }else{
        return st->data[st->top-1];
    }
}

5、入栈操作

#include"stack.h"

void push(sequence_stack *st,datatype x){
    if(st->top == LENGTH){
        printf("the stack is full!\n");
        exit(1);
    }else{
        st->data[st->top] = x;
        st->top++;
    }
}

6、出栈操作

#include"stack.h"

datatype pop(sequence_stack *st){
    if(st->top==0){
        printf("the stack is empty!\n");
        exit(1);
    }else{
        st->top--;
        return st->data[st->top];
    }
}

7、打印栈的内容

#include"stack.h"

void display_sequcence_stack(sequence_stack *st){
    if(st->top == 0){
        printf("the stack is empty!\n");
        exit(1);
    }else{
        int i;
        for(i = 0;i<st->top;i++){
            printf("%c ",st->data[i]);
        }
    }
}

 

三、栈的应用举例

括号匹配：检验表达式中的括号是否匹配

#include<stdio.h>
#include"stack.h"

void compare(sequence_stack *,datatype);

int main(){
    datatype data='\0';
    printf("Please input the express: ");
    sequence_stack Mystack;
    sequence_stack *stack=&Mystack;
    init_sequence_stack(stack);
    while((data=getchar()) != '\n'){
        switch(data){
        case '{':
        case '[':
        case '(':
                push(stack,data);
                break;
        case '}':
                compare(stack,'{');
                break;
        case ']':
                compare(stack,'[');
                break;
        case ')':
                compare(stack,'(');
                break;
        defult : break;
        }
    }
    if(is_empty_sequence_stack(stack)){
        printf("The bracket compare!\n");
    }else {
        printf("The bracket doesn't compare!\n");
    }
    return 0;
}
void compare(sequence_stack *stack,datatype data){
    if(get_top(stack) != data){
        printf("The bracket doesn't compare!\n");
        exit(0);
    }else
        pop(stack);
}

 调试运行：

[fsy@localhost stack]$ gcc `ls stack*` bracket_match.c -o bracket_match -g
[fsy@localhost stack]$ ./bracket_match
Please input the express: abc{1[2(3)]4}aaa
The bracket compare!
[fsy@localhost stack]$ ./bracket_match
Please input the express: {s(s{}s]s}
The bracket doesn't compare!
[fsy@localhost stack]$ ./bracket_match
Please input the express: { [ ( ] ) }
The bracket doesn't compare!
[fsy@localhost stack]$