你知道如何使用队列实现栈吗？（C语言）

用户10923087

发布于 2024-01-23 14:25:55

2780

文章被收录于专栏：我的计算机成长我的计算机成长

这时一道非常经典的题型，因为栈和队列的性质是相反的，队列的数据是先入先出，栈的数据是后入先出，那么怎样使用两个队列实现栈呢？

225. 用队列实现栈

这是题目的要求，如果使用C语言来实现的话，只能自己写一个队列了，这里我就不详细讲解了，具体实现思路在这：

http://t.csdnimg.cn/0SiCq

代码如下：

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;
void QueueInit(Que* pq)
{
	assert(pq);
	pq->size = 0;
	pq->head = pq->tail = NULL;
}
void QueueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueuePush(Que* pq, QDataType x)
{
	assert(pq);
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	tmp->data = x;
	tmp->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = tmp;
	}
	else
	{
		pq->tail->next = tmp;
		pq->tail = tmp;
	}
	pq->size++;
}
void QueuePop(Que* pq)
{
	assert(pq);
	assert(pq->head);
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
QDataType QueueFront(Que* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}
QDataType QueueBack(Que* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
bool QueueEmpty(Que* pq)
{
	assert(pq);
	return pq->head == NULL;
}
int QueueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}

实现思路：

在实现这个栈之前我们需要有一个具体思路，栈是后进先出，队列是先进后出，那么在插入上是没有区别的，在删除上就需要将对列的尾部删除，那么如何实现对列的尾部删除呢？这就需要将其中一个对列nonempty的数据导入到另一个对列empty，直到nonempty只剩一个数据，然后头删即可。

删除之后将nonempty和empty互换即可，必须保证其中一个队列为空。

1.栈的定义

题目要求是使用两个队列实现栈，那么就直接在栈的定义里面包含两个队列即可。

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

2.栈的初始化

为栈malloc一块空间，在使用QueueInit实现两个队列的初始化。

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

3.数据入栈

数据入栈需要将数据push到不为空的那个队列，使用QueueEmpty判断队列是否为空，再使用QueuePush尾插数据。

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

4.数据出栈

这个是题目的难点，创建两个变量分别为nonempty(非空队列)和empty(空队列），在使用if判断q1和q2哪个为空。使用while循环来实现遍历插入和删除，结束条件为nonempty内的数据为1，也就是队列的尾部数据，在循环内使用QueuePush将nonempty的头部数据插入到empty，每次插入之后要删除掉原节点。到这里还需要注意的是，题目要求返回这个数据，所以要创建一个变量返回这个数据，最后再删除掉，始终保存一个队列为空。

int myStackPop(MyStack* obj) 
{
    Que* empty=&obj->q1;
    Que* nonempty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        nonempty=&obj->q1;
        empty=&obj->q2;
    }
    else
    {
        nonempty=&obj->q2;
        empty=&obj->q1;
    }
    //将前size-1个元素导入空队列
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int ret= QueueFront(nonempty);
    QueuePop(nonempty);
    return ret;
}

5.取栈顶数据

栈顶数据也就是队列的尾部数据，使用QueueBack直接取nonempty的尾部数据即可。

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

6.判断栈是否为空

栈由两个队列组成，直接使用QueueEmpty判断两个队列是否为空即可，配合&&，必须两个都为空才返回true。

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

7.毁栈销

使用QueueDestroy销毁掉两个队列，再free掉栈的空间即可。

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

完整代码：

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


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

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

}

int myStackPop(MyStack* obj) 
{
    Que* empty=&obj->q1;
    Que* nonempty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        nonempty=&obj->q1;
        empty=&obj->q2;
    }
    else
    {
        nonempty=&obj->q2;
        empty=&obj->q1;
    }
    //将前size-1个元素导入空队列
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int ret= QueueFront(nonempty);
    QueuePop(nonempty);
    return ret;
}

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);
}

今天的分享到这里就结束啦！谢谢老铁们的阅读，让我们下期再见。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-11-25，如有侵权请联系 cloudcommunity@tencent.com 删除

int