行编辑.cpp

栈和队列的基本操作及应用

#include <stdlib.h>        
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配量

typedef struct SqStack
{
 char *base; //在栈构造之前和销毁之后，bass的值为NULL
 char *top; //栈顶指针
 int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack;

void InitStack(SqStack &S) //构造一个空栈
{
 S.base=(char*)malloc(STACK_INIT_SIZE *sizeof(char));
 if (!S.base)
  exit(1);
 S.top=S.base;
 S.stacksize=STACK_INIT_SIZE;
}

void push(SqStack &S,char e) //插入元素e为新的栈顶元素
{
 if(S.top-S.base>=S.stacksize) //栈满，追加存储空间
 {
  S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
  if (!S.base)
   exit(1);
  S.top=S.base+S.stacksize;
  S.stacksize+=STACKINCREMENT;
 }
 *S.top++=e;
}

char pop(SqStack &S,char &e) //若栈不空，则删除s的栈顶元素，用e返回其值
{

 if (S.top==S.base)
      return false;
 e=*--S.top;
 return e;
}

void ClearStack(SqStack &S) //把s置为空栈
{
 S.top=S.base;
}

void DestroyStack(SqStack &S)
{
 free(S.base);
 S.top=S.base;
}

bool StackEmpty(SqStack &S) //判断栈是否空？空则返回true，否则返回false
{
 if (S.top==S.base)
  return true;
 return false;
}
void main()
{
 char ch,e;
 SqStack S,D;
 InitStack(S); //构造一个空栈S
 InitStack(D); //构造一个空栈D
 ch=getchar(); //从终端接收第一个字符
 while (ch!=EOF) //EOF为全文结束符
 {
  while(ch!=EOF&&ch!='\n')
  {
   switch(ch)
   {
   case'#':pop(S,e);break;
   case'@':ClearStack(S);break;
   default:push(S,ch);break; //有效字符进栈
   }
   ch=getchar();
  }
  while (!StackEmpty(S)) //把有效字符压入D栈
  {
   e=pop(S,e);
   push (D,e);
   
  }
  while (!StackEmpty(D)) //输出有效字符
  {
   e=pop(D,e);
   printf("%c",e);
  }
  ClearStack(S);
  if(ch!=EOF)
   ch=getchar();
 }
 DestroyStack(S);
}