【数据结构与算法C】利用两个栈S1S2模拟一个队列，用栈的基本操作实线EnQueue,DeQueue,QueueEmpty
入队列
Created with Raphaël 2.1.2开始S2为空出S1入S2入S1yesno
出队列
Created with Raphaël 2.1.2开始S2不为空出S2结束出S1入S2S2不为空出S2yesnoyes
/* * main.c * * Created on: Apr 19, 2015 * Author: xubin * 利用两个栈S1S2模拟一个队列，用栈的基本操作实线EnQueue,DeQueue,QueueEmpty */#include#include #define STACKINITSIZE 100#define STACKINCREMENT 10#define TRUE 1#define FALSE 0typedef int bool;//顺序栈typedef struct{ char *base; char *top; int stacksize;}SqStack;//函数声明int StackLength(SqStack S);//若栈S为空，则返回TRUE，否则返回FALSEbool StackEmpty(SqStack S);// 销毁栈S，S不在存在bool DestroyStack(SqStack *S);//构造一个空栈bool InitStack(SqStack *S){ S->base = (char *)malloc(STACKINITSIZE * sizeof(SqStack)); if(S->base == NULL){ return FALSE; } S->top = S->base; S->stacksize = STACKINITSIZE; return TRUE;}// 若栈不为空，则用e返回栈顶元素，并返回true，否则返回falsebool GetTop(SqStack S,char *e){ if(S.top == S.base){ return FALSE; } *e = *(S.top - 1); return TRUE;}//插入元素e为新的栈顶元素bool Push(SqStack *S,char e){ if(S->top - S->base >=S->stacksize){ //栈满，追加存储空间 S->base = (char *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof(SqStack)); if(S->base == NULL){ return FALSE; } S->top = S->base + S->stacksize; } *S->top ++ = e; return TRUE;}// 若栈不为空，则删除S的栈顶元素，用e返回其值，并返回TRUE，否则返回FALSEbool Pop(SqStack *S,char *e){ if(S->top == S->base){ return FALSE; } *e = * -- S->top; // 传递指针指向的内容而不是传递指针 //e= --S->top; // 错误的传递方法 return TRUE;}//**********************************************************************//**********************************************************************// 用栈的基本操作模拟队列// 利用两个栈S1S2模拟一个队列，用栈的基本操作实线EnQueue,DeQueue,QueueEmpty//bool EnQueue(SqStack *S1,SqStack *S2,char e){ char temp; //如果S2为空，出S1入S2 if(StackEmpty(*S2) == TRUE){ while(StackEmpty(*S1) == FALSE){ Pop(S1,&temp); Push(S2,temp); } } Push(S1,e); return TRUE;}bool DeQueue(SqStack *S1,SqStack *S2,char *e){ char temp; // 判断是否为空 if(StackEmpty(*S2) == TRUE && StackEmpty(*S1) == TRUE){ return FALSE; } if(StackEmpty(*S2) == FALSE){ Pop(S2,e); } else{ while(StackEmpty(*S1) == FALSE){ Pop(S1,&temp); Push(S2,temp); } Pop(S2,e); } return TRUE;}bool QueueEmpty(SqStack S1,SqStack S2){ if(StackEmpty(S1) == TRUE && StackEmpty(S2) == TRUE){ return TRUE; }else return FALSE;}//*********************************************************************//*********************************************************************int main(){ SqStack S1,S2; char ch; char temp; printf("顺序栈的基本操作\n"); if(InitStack(&S1) == 1 && InitStack(&S2) == 1){ printf("栈初始化成功\n"); } else{ printf("初始化失败\n"); return 1; } printf("现在输入一串字符串，压入队列:"); ch = getchar(); while(ch != '\n' && EnQueue(&S1,&S2,ch)){ ch = getchar(); } while(QueueEmpty(S1,S2) == FALSE){ DeQueue(&S1,&S2,&temp); printf("%c\t",temp); } return 0;}//返回栈S的元素的个数，即栈的长度int StackLength(SqStack S){ //int num = 0; return (S.top - S.base);}// 销毁栈S，S不在存在bool DestroyStack(SqStack *S){ if(S->base == NULL) return FALSE; free(S->base); return TRUE;}//若栈S为空，则返回TRUE，否则返回FALSEbool StackEmpty(SqStack S){ if(S.top == S.base){ return TRUE; } else{ return FALSE; }}
版权声明：本文为博主原创文章，未经博主允许不得转载。