数据结构-栈的顺序实现(顺序栈)

#include <stdio.h>

#include <malloc.h>

#define OK 0

#define ERROR 1

typedef int EType;

typedef struct{
  EType *data;
  int capacity;
  EType *top;
}SqStack;

int initSqStack(SqStack *pS,int size){
   pS->data = (EType*)malloc(size*sizeof(EType));
   if(!pS->data) return ERROR;
   pS->capacity = size;
   pS->top = pS->data;
   return OK;
}

int pushSqStack(SqStack *pS,EType e){
  if(pS->top-pS->data==pS->capacity)
    return ERROR;
  *(pS->top) = e;
  pS->top++;
  return OK;
}

int popSqStack(SqStack *pS){
  if(pS->top==pS->data)
    return ERROR;
  pS->top--;
  return OK;
}
int topSqStack(SqStack *pS,EType *e){
  if(pS->top==pS->data)
    return ERROR;
  *e = *(pS->top-1);
  return OK;
}

int isEmpty(SqStack S){
  if(S.top==S.data) return 1;
  return 0;
}

int main(){
  SqStack S;
  initSqStack(&S,50);
  
  EType e = 10; pushSqStack(&S,e);
  e = 20; pushSqStack(&S,e);
  e = 30; pushSqStack(&S,e);
  e = 40; pushSqStack(&S,e);
  while(!isEmpty(S)){
    topSqStack(&S,&e);
    printf("%d\n",e);
    popSqStack(&S);
  }
  return 0;
}

//#include "SqStack.h"
#include <malloc.h>
const int STACK_INIT_SIZE  = 100;
const int STACKINCREMENT = 20;
Status InitStack(SqStack &S)
{
  //分配空间
  S.base = (SElemType*) malloc(STACK_INIT_SIZE * sizeof(SElemType));
  if(!S.base)   return OVERFLOW;
  S.top       = S.base;           //设置指针
  S.stacksize = STACK_INIT_SIZE;  //设置大小
  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) return 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;       //出栈
    --S.top;
    return OK;
}

SElemType Top(SqStack &S){
    SElemType e;
    if(S.top == S.base) return e; //返回一个无效的数据
    return *(S.top-1);
}

//#include "SqStack.h"
#include <cstdio>
/*
准备一个栈，用于存放扫描遇到的左括号
从左向后扫描每一个字符{
  如果遇到的是左括号，则入栈
  如果遇到的是右括号，则
      把栈顶字符和当前字符比较
      若匹配，则弹出栈顶字符，继续向前扫描
      若不匹配，程序返回不匹配标志
  }
当所有字符都扫描完毕，栈应当为空
*/
bool isLeftBracket(const char ch){
    if(ch=='('||ch=='['||ch=='{') return true;
    return false;
}
bool isRightBracket(const char ch){
    if(ch==')'||ch==']'||ch=='}') return true;
    return false;
}
bool isBracketMatch(const char lc,const char rc){
    if(lc=='('&&rc==')'||lc=='['&&rc==']'||lc=='{'&&rc=='}') return true;
    return false;
}
bool IsBracketsMatch(const char *str){
    SqStack S; 
    InitStack(S);//试试不初始化会怎么样？
    const char *p = str;
    while(*p!='\0'){
        if(isLeftBracket(*p)) Push(S,*p);
        else if(isRightBracket(*p)){
            char ch = Top(S);
            if(!isBracketMatch(ch,*p)) return false;
            Pop(S);
        }
        p++; //继续
    }
    if(IsEmpty(S)) return true;
    return false;
}

int main(){
    char *s = "{}[([][])]"; // "[(])，(()]"
    if(IsBracketsMatch(s))printf("Brackets is matched!\n");
    else printf("Brackets is not matched!\n");

    return 0;
}