剑指offer java实现 【剑指offer】两个队列实现一个栈
*******************************************************************/ #include#include typedefstructNode{intdata;structNode*pNext;}NODE,*PNODE; typedefstructQueue{PNODEfront;//队头指针PNODErear;//队尾指针}QUEUE,*PQUEUE; PQUEUEcreate_queue();boolis_empty(PQUEUE);voiden_queue(PQUEUE,int);boolde_queue(PQUEUE,int*);voiddestroy_queue(PQUEUE);voidtraverse_queue(PQUEUE);intlength(PQUEUE);voidpush(PQUEUE,PQUEUE,int);boolpop(PQUEUE,PQUEUE,int*); intmain(){intpData;//用来保存出队的元素值 //创建队列并进行入队测试PQUEUEpS1=create_queue();PQUEUEpS2=create_queue();push(pS1,pS2,4);push(pS1,pS2,5);printf("thelengthofpS1:%d\n",length(pS1));printf("thelengthofpS2:%d\n",length(pS2));if(pop(pS1,pS2,&pData))printf("%dispopout\n",pData);elseprintf("Stackisempty,cannotpop\n");printf("thelengthofpS1:%d\n",length(pS1));printf("thelengthofpS2:%d\n",length(pS2));push(pS1,pS2,6);printf("thelengthofpS1:%d\n",length(pS1));printf("thelengthofpS2:%d\n",length(pS2));push(pS1,pS2,7);printf("thelengthofpS1:%d\n",length(pS1));printf("thelengthofpS2:%d\n",length(pS2));if(pop(pS1,pS2,&pData))printf("%dispopout\n",pData);elseprintf("Stackisempty,cannotpop\n");printf("thelengthofpS1:%d\n",length(pS1));printf("thelengthofpS2:%d\n",length(pS2));if(pop(pS1,pS2,&pData))printf("%dispopout\n",pData);elseprintf("Stackisempty,cannotpop\n");printf("thelengthofpS1:%d\n",length(pS1));printf("thelengthofpS2:%d\n",length(pS2));if(pop(pS1,pS2,&pData))printf("%dispopout\n",pData);elseprintf("Stackisempty,cannotpop\n");printf("thelengthofpS1:%d\n",length(pS1));printf("thelengthofpS2:%d\n",length(pS2));if(pop(pS1,pS2,&pData))printf("%dispopout\n",pData);elseprintf("Stackisempty,cannotpop\n"); return0;} /*创建一个空队列,队头指针和队尾指针都指向头结点,头结点中不存放数据,只存放指针*/PQUEUEcreate_queue(){PQUEUEpS=(PQUEUE)malloc(sizeof(Queue));pS->front=(PNODE)malloc(sizeof(NODE));if(!pS||!pS->front){printf("pSorfrontmallocfailed!!");exit(-1);}else{pS->rear=pS->front;pS->front->pNext=NULL;}returnpS;} /*判断队列是否为空*/boolis_empty(PQUEUEpS){if(pS->front==pS->rear)returntrue;elsereturnfalse;} /*进队函数,从队尾进队,队头指针保持不变*/voiden_queue(PQUEUEpS,inte){PNODEpNew=(PNODE)malloc(sizeof(NODE));if(!pNew){printf("pNewmallocfailed");exit(-1);}else{pNew->data=e;pNew->pNext=NULL;pS->rear->pNext=pNew;pS->rear=pNew;}return;} /*出队函数,从队头出队,队尾指针保持不变,但当最后一个元素出队时,需要对队尾指针重新赋值,使其指向头结点*/boolde_queue(PQUEUEpS,int*pData){if(is_empty(pS))returnfalse;else{PNODEp=pS->front->pNext;*pData=p->data;pS->front->pNext=p->pNext; //这里是队列头元素出队的特殊情况,一般情况下,删除队头元素时//仅需修改头结点中的指针,但当队列中最后一个元素被删除时,//队列尾指针也丢失了,因此需对队尾指针重新赋值(指向头结点)。if(pS->rear==p)pS->rear=pS->front;free(p);}returntrue;} /*遍历队列,从对头向队尾依次输出队中的元素*/voidtraverse_queue(PQUEUEpS){if(is_empty(pS))printf("thereisnodatainthequeue!\n");else{PNODEpCurrent=pS->front->pNext;printf("Nowdatasintthequeueare:\n");while(pCurrent){printf("%d",pCurrent->data);pCurrent=pCurrent->pNext;}printf("\n");}return;} /*求队列的长度*/intlength(PQUEUEpS){intcount=0;PNODEpCurrent=pS->front->pNext;while(pCurrent){count++;pCurrent=pCurrent->pNext;}returncount;} /*销毁队列,头结点也被销毁,最后也将pS节点销毁,并将其指向为空,避免垂直指针的产生*/voiddestroy_queue(PQUEUEpS){if(is_empty(pS))return;else{while(pS->front){pS->rear=pS->front->pNext;free(pS->front);pS->front=pS->rear;}}free(pS);pS=0;return;} /*用两个队列模拟入栈操作*/voidpush(PQUEUEpS1,PQUEUEpS2,intval){if(is_empty(pS2))en_queue(pS1,val);elseen_queue(pS2,val);} /*用两个队列模拟出栈操作*/boolpop(PQUEUEpS1,PQUEUEpS2,int*pData){if(is_empty(pS1)&&is_empty(pS2))returnfalse; intDelData;if(!is_empty(pS2)){intlen=length(pS2);while(len-->1){de_queue(pS2,&DelData);en_queue(pS1,DelData);}//将队列的最后一个元素出队,作为出栈元素de_queue(pS2,pData);returntrue;}if(!is_empty(pS1)){intlen=length(pS1);while(len-->1){de_queue(pS1,&DelData);en_queue(pS2,DelData);}//将队列的最后一个元素出队,作为出栈元素de_queue(pS1,pData);returntrue;}}测试结果:
来源: http://www.92to.com/bangong/2017/04-17/20564415.html