利用队列实现栈数据结构

225. 用队列实现栈 - 力扣（LeetCode）

typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;int size;
}Queue;void QueueInit(Queue* pq)
{assert(pq);pq->head=NULL;pq->tail=NULL;pq->size=0;
}void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur=pq->head;QueueNode* next=NULL;while(cur!=NULL){next=cur->next;free(cur);cur=next;}pq->head=NULL;pq->tail=NULL;pq->size=0;free(pq);
}//入队
void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode==NULL){perror("QueuePush::Malloc");return;}newnode->next=NULL;newnode->data=x;if (pq->head!=NULL){pq->tail->next=newnode;pq->tail=newnode;}else{pq->head=newnode;pq->tail=newnode;}pq->size++;
}//出队
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head!=NULL);QueueNode* next=pq->head->next;free(pq->head);pq->head=next;if (pq->head==NULL){pq->tail=NULL;}pq->size--;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size==0;
}QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}//
typedef struct 
{Queue* q1;Queue* q2;
} MyStack;MyStack* myStackCreate() 
{MyStack* pst = (MyStack*)malloc(sizeof(MyStack));if (pst==NULL){perror("myStackCreate::malloc");return NULL;}pst->q1 = (Queue*)malloc(sizeof(Queue));if (pst->q1==NULL){perror("myStackCreate::malloc");return NULL;}pst->q2 = (Queue*)malloc(sizeof(Queue));if (pst->q2==NULL){perror("myStackCreate::malloc");return NULL;}QueueInit(pst->q1);QueueInit(pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) 
{assert(obj);if (!QueueEmpty(obj->q1)){QueuePush(obj->q1,x);}else{QueuePush(obj->q2,x);}
}int myStackPop(MyStack* obj) 
{assert(obj);Queue* emptyq=obj->q1;Queue* nonemptyq=obj->q2;if (obj->q1->size!=0){emptyq=obj->q2;nonemptyq=obj->q1;}// while(QueueSize(nonemptyq)>1)int num=QueueSize(nonemptyq); //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!for (int i=0;iq1)){return QueueBack(obj->q1);}else{return QueueBack(obj->q2);}
}bool myStackEmpty(MyStack* obj) 
{assert(obj);return obj->q1->size==0 && obj->q2->size==0;
}void myStackFree(MyStack* obj) 
{assert(obj);QueueDestroy(obj->q1);QueueDestroy(obj->q2);free(obj);
}

一些说明

利用两个队列可以模拟数据结构栈，原理是这样的：因为我们都知道栈的特性就是后进先出，那我们就这样：

1. 当这个栈需要入栈的时候，我们那就往有数据的那个队列里面去入队（当然一开始的话，两个队列都是没有数据的，是空的，我们就随便选一个，然后把数据放到那个队列里面去）。

2. 当这个栈需要出栈时（这个步骤是最为最为核心与关键的），根据栈的尿性，元素出栈的话只能从栈顶出去。因此如果单单依靠单个队列的话是不可能完成的。这时候我们就把队列除了最后一个元素之外的其他所有元素，先全部取出来入到另外一个空的队列里面，然后这些元素每入到一个新队列，我在原先那个队列里面pop一下把它从原先的地方“除籍”，然后接下来原队列到最后弄着弄着就只剩最后一个元素了，这时候就只把它pop一下，这样子的话就相当于完成了出栈。然后到最后其他剩余的元素还是按照原先的顺序，只不过是到了另一个队列里面去了。

3. 要求栈里面非元素个数，判断是否为空，销毁等等，这些操作的话就非常简单，就会多加以赘述

4. 对于结构体嵌套以及之间的指针关系，我想进行进一步的说明：

情形一举例：

1. 一个大结构体a里面有两个小结构体成员b和c，那么当我把这个大结构体a创建出来的时候（无论是在栈区还是堆区malloc出来），这两个小结构体成员也同时被开辟出来（也就是说结构体的完完整整的，实实在在的实体所占据的内存已经被申请出来）。

2. 一个大结构体a里面有两个小结构体成员指针b和c，那么在这种情形之下，如果说把大结构体a创建出来，（无论是在栈区还是堆区malloc出来），但这时候由于这个大结构体a里面的两个成员是结构体指针，并不是结构体的实体，所以b,c结构体这些个实体还并没有被开辟出来，也就是说在内存当中还没有它们的名分。这时候对于大结构体a的两个成员指针虽然是结构体指针，但并不能拿来用，因为他们实际上现在是野指针。在这种情况之下，就只能在去开辟属于结构体b，c实体的内存空间，然后把这些内存空间的地址赋给两个结构体成员指针，这样的话，这两个结构体成员指针才能够正常使用。

情形二举例：

1. 在上述1的情况之下，比如说现在有一个函数，它的参数是结构体指针，那么如果我想要去传参的话，我就要a->b，这样子行吗？这样子是不行的，因为这样子的结果是一个结构体，而我如果想要传入结构体的指针的话，就要这样：&a->b（&优先级低）。

2. 在上述2的情况之下，我的道理，如果我也想往函数参数那边按照它规定传入一个结构体指针，我直接a->b就可以了，懂得吧.

最后，我想说：

for循环除了i之外的那些变量，必须在for循环当中保持不变，否则的话，你苦头有的吃。