思路:设置两个栈,栈1起入队的作用、栈2起出队的作用.入队时,所有元素进栈1,栈满时会通过realloc函数追加存储空间
并且保存原来栈1的元素.出队时,先判断栈2是否为空,若为空,则会判断栈1是否为空,栈1为空,则说明队列为空,栈1不为空则将栈1的元素全部出栈并入栈2,栈2满时依然通过realloc追加存储空间,然后栈2元素出栈;若栈2不为空,栈2元素直接出栈extern void *realloc(void *mem_address, unsigned int newsize);
功能:先释放原来mem_address所指内存区域，并按照newsize指定的大小重新分配空间，同时将原有数据从头到尾拷贝到新分配的内存区域，并返回该内存区域的首地址,即重新分配存储#include#include #define STACK_INIT_SIZE 3//定义栈初始空间的容量#define STACKINCREMENT 3//存储空间的分配增量typedef char elementtype;//栈1作入栈用,栈2作出栈用typedef struct sqstack{ elementtype *top;//栈顶指针 elementtype *base;//栈底指针 int stacksize;//当前已分配的空间,以栈元素的个数为单位}sqstack;sqstack *s1 = (sqstack*)malloc(sizeof(sqstack));sqstack *s2 = (sqstack*)malloc(sizeof(sqstack));int inistack(){ s1->base = (elementtype*)malloc(sizeof(elementtype)*STACK_INIT_SIZE);//access violation s2->base = (elementtype*)malloc(sizeof(elementtype)*STACK_INIT_SIZE); if(!s1->base && !s2->base) return 0; s1->top = s1->base;//栈空时,栈顶指针和栈底指针位置相同 s2->top = s2->base; s1->stacksize = s2->stacksize = STACK_INIT_SIZE; return 1;}int enstack(char t,int c){ if(c == 1) { if(s1->top - s1->base == s1->stacksize)//栈1满 { s1->base = (elementtype*)realloc(s1->base,sizeof(elementtype)*(s1->stacksize+STACKINCREMENT));//追加存储空间 if(!s1->base)//空间开辟失败 return 0; s1->stacksize += STACKINCREMENT;//修改栈容量 } *(s1->top)++ = t; return 1; } else{ if(s2->top - s2->base == s2->stacksize)//栈2满 { s2->base = (elementtype*)realloc(s2->base,sizeof(elementtype)*(s2->stacksize+STACKINCREMENT));//追加存储空间 if(!s2->base)//空间开辟失败 return 0; s2->top = s2->base + s2->stacksize;//修改栈顶指针的新值 s2->stacksize += STACKINCREMENT;//修改栈容量 } *(s2->top)++ = t; return 1; }}int popstack(char &t){ if(s2->top == s2->base)//栈2空 { if(s1->top == s1->base)//如果栈1也空,则队列为空 return 0; else{ //栈1的所有元素出栈,入栈2 while(s1->top != s1->base) { enstack(*(--s1->top),2);//入栈2 } } } t = *(--s2->top); return 1;}void QueueMenu(){ printf("\t\t\t~~~两个栈模拟无限长队列~~~\n"); printf("\t\t\t\t1.元素入队\n"); printf("\t\t\t\t2.元素出队\n"); printf("\t\t\t\t3.显示队列\n"); printf("\t\t\t\t4.清空队列\n");}int enqueue(char t){ return enstack(t,1);}int dequeue(char &t){ return popstack(t);}int showqueue(){ if(s2->top == s2->base && s1->top == s1->base) return 0; else{ printf("队列元素为:"); elementtype *s = s2->top; while(s != s2->base) printf("%c ",*(--s)); //此处依然是栈的操作 s = s1->base; while(s1->top != s) printf("%c ",*s++); printf("\n"); return 1; }}int delqueue(){ free(s1->base); free(s2->base); return inistack();}int main(){ int a; inistack(); while(1) { QueueMenu(); printf("请输入你的选择:"); scanf("%d",&a); while(a < 1 || a > 4) { fflush(stdin);//清除缓存 system("pause"); system("cls"); QueueMenu(); printf("请重新输入你的选择:"); scanf("%d",&a); } //inistack(); char t; switch(a) { case 1: fflush(stdin);// printf("请输入要入队的元素:"); scanf("%c",&t); if(enqueue(t)) printf("元素入队成功!\n"); else printf("队满,元素入队失败!\n"); break; case 2: if(dequeue(t)) printf("出队元素为:%c\n",t); else printf("队空!出队失败!\n"); break; case 3: if(!showqueue()) printf("队列为空!\n"); break; default: if(delqueue()) printf("队列清空\n"); else printf("重新创建失败,队列未被清空\n"); } fflush(stdin); system("pause"); system("cls"); } return 0;}