一、队列的基本结构及其接口
typedef int QDataType; //队列的结构定义 typedef struct QueueNode{ QDataType val; struct QueueNode *next; }QNode; //用结构体管理队列 typedef struct Queue{ QNode* phead; QNode* ptail; int size; }Queue; //队列的初始化 void QueueInit(Queue* pq) { pq->phead=NULL; pq->ptail=NULL; pq->size=0; } //入队 void QueuePush(Queue *pq,QDataType x) { assert(pq); QNode *newnode=(QNode*)malloc(sizeof(QNode)); if(newnode==NULL) { perror("malloc fail"); exit(-1); } newnode->val=x; newnode->next=NULL; if(pq->phead==NULL)//队列为空 pq->phead=pq->ptail=newnode; else { pq->ptail->next=newnode; pq->ptail=newnode; } pq->size++; } //出队 void QueuePop(Queue* pq) { assert(pq); assert(pq->phead);//空队列 if(pq->phead==pq->ptail) { pq->ptail=NULL; } QNode* tmp=pq->phead; pq->phead=tmp->next; free(tmp); tmp=NULL; pq->size--; } //取队头元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; } //取队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->ptail); return pq->ptail->val; } //判空 bool QueueEmpty(Queue *pq) { assert(pq); return pq->phead==NULL; } //销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QNode *cur=pq->phead; while(cur) { QNode* tmp=cur; cur=cur->next; free(tmp); tmp=NULL; } pq->phead=pq->ptail=NULL; pq->size=0; }
二、我的栈的结构
//我的栈结构 typedef struct { Queue q1; Queue q2; } MyStack;
三、 我的栈的创建及其初始化
//我的栈的创建及其初始化 MyStack* myStackCreate() { MyStack *ps=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&ps->q1); QueueInit(&ps->q2); return ps; }
四、我的栈的入栈
//我的栈入栈 void myStackPush(MyStack* obj, int x) { //利用假设法 Queue *empty=&obj->q1; Queue *noneempty=&obj->q2; if(!QueueEmpty(&obj->q1)) { empty=&obj->q2; noneempty=&obj->q1; } QueuePush(noneempty,x); //QueuePush(&obj->q1,x); }
五、我的栈出栈
//我的栈出栈 int myStackPop(MyStack* obj) { //利用假设法 Queue *empty=&obj->q1; Queue *noneempty=&obj->q2; if(!QueueEmpty(&obj->q1)) { empty=&obj->q2; noneempty=&obj->q1; } while(noneempty->size>1) { QueuePush(empty,QueueFront(noneempty)); QueuePop(noneempty); } int stackpop=QueueFront(noneempty); QueuePop(noneempty); return stackpop; }
六、我的栈取栈顶元素
//我的栈取栈顶元素 int myStackTop(MyStack* obj) { Queue* empty=&obj->q1; Queue* noneempty=&obj->q2; if(!QueueEmpty(&obj->q1)) { empty=&obj->q2; noneempty=&obj->q1; } return QueueBack(noneempty); }
七、我的栈判空
//我的栈判空 bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); }
八、我的栈销毁
//我的栈销毁 void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }
