【数据结构与算法】使用队列实现栈（图文详解）

// 链式结构：表示队列 
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);//接收的地址必须是有效的（队列必须存在）
	q->head = q->tail = NULL;
	q->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)//判定是否申请成功
	{
		perror("newnode error\n");
		exit(1);
	}
	newnode->data = data;
	newnode->next = NULL;

	if (q->head == NULL)//对空队列入队的处理
	{
		q->head = q->tail = newnode;
	}
	else               //对非空队列入队的处理
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->head);//队列不能为空
	if (q->head == q->tail)//对只有一个元素的队列的出队处理
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else          //对存在多个元素的队列的出队处理
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->head);//队列不能为空
	return q->head->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->tail->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	while (q->head)//释放所有节点
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->head = q->tail = NULL;
	q->size = 0;
}

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


MyStack* myStackCreate() {
    MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&(stack->q1));//调用队列的初始化函数
    QueueInit(&(stack->q2));
    return stack;
}

void myStackPush(MyStack* obj, int x) 
{
    assert(obj);
    if (QueueEmpty(&(obj->q1)))//将数据插入到非空队列
    {
	    QueuePush(&(obj->q2), x);
    }
    else
	    QueuePush(&(obj->q1), x);
}

int myStackPop(MyStack* obj) 
{
    assert(obj);
    assert(obj->q1.size || obj->q2.size);//必须存在一个非空队列才能出栈
Queue* empty = &(obj->q1);//假设q1是空队列
Queue* nempty = &(obj->q2);
if (!QueueEmpty(&(obj->q1)))//进行判断并调整
{
	empty = &(obj->q2);
	nempty = &(obj->q1);
}
while (nempty->size > 1)//移动元素至最后一个
{
	QueuePush(empty, QueueFront(nempty));
	QueuePop(nempty);
}
int top = QueueFront(nempty);//返回最后的元素
QueuePop(nempty);
return top;
}

int myStackTop(MyStack* obj) 
{
    assert(obj);
    assert(obj->q1.size || obj->q2.size);//必须存在一个非空队列才能获取元素
//如果队列的实现允许查看队尾数据，会比较简单
/*if (QueueEmpty(&(obj->q1)))
	return QueueBack(&(obj->q2));
else
	return QueueBack(&(obj->q1));*/

//如果队列的实现不允许查看队尾数据，依然需要移动元素
Queue* empty = &(obj->q1);//假设q1是空队列
Queue* nempty = &(obj->q2);
if (!QueueEmpty(&(obj->q1)))//进行判断并调整
{
	empty = &(obj->q2);
	nempty = &(obj->q1);
}
while (nempty->size > 1)//移动元素至最后一个
{
	QueuePush(empty, QueueFront(nempty));
	QueuePop(nempty);
}
int top = QueueFront(nempty);//返回最后的元素
QueuePush(empty, QueueFront(nempty));
	QueuePop(nempty);
return top;
}

bool myStackEmpty(MyStack* obj) {
    	return obj->q1.size == 0 && obj->q2.size == 0;
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&(obj->q1));
QueueDestroy(&(obj->q2));
free(obj);//动态申请的空间不要忘记释放
}