#include<stdio.h> #include<stdlib.h> /*
一定要知道：栈先进后厨，顶进顶出（栈顶）；对先进先出，头出尾进 栈实现队列 1.进栈S1 ，出栈S2 两个栈配合使用 实现队的头进尾出 2.入栈时，直接s1添加即可 出栈需要将s1的压入s2中，出栈，出完再从s1压回s2 */
typedef struct node { int nValue; struct node* pNext; }Node; typedef struct stack { int sCount; Node* pTop; }Stack; typedef struct queue { int qCount; Stack* pStack1; Stack* pStack2; }Queue; //栈 //栈初始化 void InitStack(Stack** pStack) { *pStack = (Stack*)malloc(sizeof(Stack)); (*pStack)->sCount = 0; (*pStack)->pTop = NULL; } //入栈 void PushStack(Stack* pStack,int value) { if(pStack == NULL)return; Node* pTemp = NULL; pTemp=(Node*)malloc(sizeof(Node)); pTemp->nValue = value; pTemp->pNext = pStack->pTop;
pStack->pTop=pTemp; pStack->sCount++; } //出栈 int PopStack(Stack* pStack) { if(pStack == NULL || pStack->sCount == 0)return -1 ; Node* Del=NULL; int num; Del = pStack->pTop; num = Del->nValue;
pStack->pTop = pStack->pTop->pNext; free(Del); Del = NULL; pStack->sCount--; return num; } //队 //初始化队 void InitQueue(Queue** pQueue) { *pQueue=(Queue*)malloc(sizeof(Queue)); (*pQueue)->pStack1= NULL; (*pQueue)->pStack2=NULL; (*pQueue)->qCount=0;
InitStack(&((*pQueue)->pStack1)); InitStack(&((*pQueue)->pStack2)); } //入队 void PushQueue(Queue* pQueue,int svalue) { if(pQueue == NULL || pQueue->pStack1 == NULL || pQueue->pStack2 == NULL)return; //s1入队 while(pQueue->pStack2->sCount != 0) { PushStack(pQueue->pStack1,PopStack(pQueue->pStack2));//s2 入到 s1 } //然后入栈s1 PushStack(pQueue->pStack1,svalue); pQueue->qCount++; } //出队 int PopQueue(Queue* pQueue) { if(pQueue == NULL || pQueue->pStack1 == NULL || pQueue->pStack2 == NULL || pQueue->qCount == 0)return -1; //s1出队 ，s2入队 int Num; while(pQueue->pStack1->sCount != 0) { PushStack(pQueue->pStack2,PopStack(pQueue->pStack1)); } //s2 出栈 Num = PopStack(pQueue->pStack2); pQueue->qCount--; return Num; } //判断是否为空 int main() { Queue* MyQueue = NULL; InitQueue(&MyQueue); PushQueue(MyQueue,5); PushQueue(MyQueue,7); PushQueue(MyQueue,54); PushQueue(MyQueue,12); PushQueue(MyQueue,46); /*int index = MyQueue->qCount; Queue* test = MyQueue; while(index != 0) { printf("%d",test->pStack1->pTop->nValue); test ->pStack1->pTop = test->pStack1->pTop->pNext; index--; }*/ //printf("%d",MyQueue->pStack1->pTop->nValue); printf("\n"); printf("出队:%d\n",PopQueue(MyQueue)); printf("出队:%d\n",PopQueue(MyQueue)); printf("出队:%d\n",PopQueue(MyQueue)); return 0; }
