数据结构 - 栈的实现和应用

1、采用书上第 46 页定义的栈的顺序存储表示，编程实现栈的下列基本操作。
（1）初始化顺序栈 （2）创建顺序栈 （3）判断栈空 （4）输出顺序栈
（5）取栈顶元素 （6）入栈 （7）出栈
2、采用栈的顺序存储表示，编程实现表达式中圆括号“( )”和方括号“[ ]”匹配的检验。

4.1

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#define TRUE    1
#define FALSE   0
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2
typedef int Status;
typedef int SElemType;
#define STACK_INIT_SIZE 100 
#define STACKINCREMENT  10 
typedef struct  {
    SElemType *base; 
    SElemType *top; 
    int     stacksize; 
} SqStack;
 
Status InitStack(SqStack &S) {
    S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base)           
        exit(OVERFLOW);           
    S.top = S.base;               
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

Status StackEmpty(SqStack S) {
    if(S.top == S.base)
        return TRUE;     
    else
        return FALSE; 
}

Status GetTop(SqStack S, SElemType &e) {
    if(S.top == S.base)
        return ERROR;
    e = *(S.top - 1);
    return OK;
}

Status Push(SqStack &S, SElemType e) {
    if(S.top-S.base >= S.stacksize) {
        S.base=(SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if(!S.base)
            exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}

Status Pop(SqStack &S, SElemType &e) {
    if(S.top == S.base)
        return ERROR;
    e = *--S.top;
    return OK;
}

Status Stackoutput(SqStack &S){
	SElemType *p;
	if(S.top == S.base) return ERROR;
	p = S.top;
	while(p!=S.base-1){
		printf("%d-",*p--);
	}
	printf("\n");
	return OK;
}

Status StackTraverse(SqStack S) {
	SElemType *p;
	if(S.top == S.base) return ERROR;
	p = S.base;
	while(p!=S.top){
		printf("%d-",*p++);
	}
	printf("\n");
	return OK;
}

int main() {
    int i,n,k,h,a,b;
    SqStack S;
    printf("创建一个空栈!\n");
	InitStack(S);
	printf("判断栈是否为空!\n");
	printf("StackEmpty(S) = %d\n",StackEmpty(S));
	printf("创建栈的元素个数: \n");
	scanf("%d",&n);
	printf("输入%d个入栈元素的值: \n",n);
	while(n--) {
		scanf("%d",&k);
		Push(S,k);
	} 
	printf("逆序输出顺序栈元素值: \n");
	StackTraverse(S);
	Pop(S,a);
	printf("输出第1个出栈元素值: %d\n",a);
	Pop(S,a);
	printf("输出第2个出栈元素值: %d\n",a);
	printf("输出两次出栈后顺序栈元素值: ");
	StackTraverse(S);
	GetTop(S,b);
	printf("输出栈顶元素值: %d\n",b); 
}

4.2

#include<bits/stdc++.h>
#define TLE ios::sync_with_stdio(0),cin.tie(0)
#define long long ll
using namespace std;
typedef char st;
struct SqStack{
	st *base;
	st *top;
	int stacksize;
};
void InitStack(SqStack &S) {
    S.base = (st*)malloc(105* sizeof(st));
    if(!S.base) exit (0);           
    S.top = S.base;               
    S.stacksize = 105;
}
bool Correct(st s[]){
	int l = strlen(s);
	SqStack S; InitStack(S);
	for(int i = 0; i < l; i++){
		if(s[i] == '(' || s[i] == '[') {
			*++S.top = s[i];
		}
		else if(s[i] == ')' && *S.top == '(' && S.top!=S.base) {
			free(S.top);
			S.top--;
		}
		else if(s[i] == ']' && *S.top == '[' && S.top!=S.base) {
			free(S.top);
			S.top--;
		}
	}
	if(S.top == S.base) {
		free(S.base);
		return 1;
	}
	else {
		free(S.base);
		return 0;
	}
}
int main(){
	st s[105];
	printf("请输入带括号的表达式: \n");
	scanf("%s",s);
	if(Correct(s)) printf("括号匹配正确!\n");
	else printf("括号匹配不正确!\n"); 
	
}

本文地址：https://blog.csdn.net/weixin_45919985/article/details/110286325