目录

题目：

原理：

结构体MyStack

出栈void myStackPop(MyStack* obj)

入栈void myStackPush(MyStack* obj, int x)

读取栈顶元素int myStackTop(MyStack* obj)

判断栈空bool myStackEmpty(MyStack* obj)

销毁栈void myStackFree(MyStack* obj)

整体结果：

---

题目：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

原理：

结构体MyStack

定义了两个队列，原因在出栈中。

出栈void myStackPop(MyStack* obj)

这里通过队列实现栈，队列满足先进先出相当于上面图中3会先出来了，但出栈应该是1先出，这里通过创建两个单链表队列q1，q2，当一个队列中出队到只剩下一个结点时，这个时候再出队，就是栈顶的结点，把出队的结点放在另一个队列中，下一次要出栈，就重复刚才的操作（即将非空队列中的n-1个结点出队，放在空队列中，出队最后剩余的那一个结点）。

入栈void myStackPush(MyStack* obj, int x)

入栈和入队一样都是从队尾进入，所以这里只需要找到非空队列，进行入队操作即可。

读取栈顶元素int myStackTop(MyStack* obj)

首先要寻找，这两个队列中哪一个有结点（即非空），找到后，利用队列读取队尾元素的函数，直接可以实现读取栈顶元素。

判断栈空bool myStackEmpty(MyStack* obj)

这里需要判断两个队列都为空，则栈就为空。

销毁栈void myStackFree(MyStack* obj)

直接调用队列销毁函数，将两个队列销毁，再将obj释放掉，置为空。

整体结果：

//之前的代码为队列这个数据结构的实现，和之前文章的一样。

typedef int DataType;

typedef struct QueueNode
{
	DataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;
}Queue;

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead==NULL;
}

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

QueueNode* BuyNode(DataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void QueuePush(Queue* pq, DataType x)
{
	assert(pq);
	QueueNode*newnode= BuyNode(x);
	if (pq->phead ==NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
    assert(!QueueEmpty(pq));
    if (pq->phead == pq->ptail)
{
	free(pq->phead);
	pq->phead = pq->ptail = NULL;
}
    else
{
	QueueNode* next = pq->phead->next;
	free(pq->phead);
	pq->phead = next;	
}
pq->size--;	
}

DataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

DataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}



int QueueSize(Queue* pq)
{
	return pq->size;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
    
}

int myStackPop(MyStack* obj) {
    Queue*emp=&obj->q1;
    Queue*noemp=&obj->q2;
    if(QueueEmpty(&obj->q2))
    {
        emp=&obj->q2;
        noemp=&obj->q1;
    }
    while(QueueSize(noemp)>1)
    {
        QueuePush(emp,QueueFront(noemp));
        QueuePop(noemp);
    }
    int top=QueueFront(noemp);
    QueuePop(noemp);
    return top;
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
    

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj=NULL;
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/