数据结构之通过“ 队列 ”实现的“ 栈 ”功能。

2024-07-15 05:36:03
开发
22

🌹专栏🌹：数据结构

前言

本节内容是利用“ 队列 ”先进先出的特点实现 “ 栈 ” 先进后出。

一、题目

1.1 题目描述：

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

实现 MyStack 类：

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

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

int top() 返回栈顶元素。

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

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

1.2 分析题目

我们要通过队列实现栈，怎么实现呢？我们发现一个队列无论如何都无法实现栈的功能，所以我们就尝试创建两个队列来试试。分别为 empty（为空的队列）、 noempty（不为空的队列）。我们把noempty的数据导入到empty的数据里面，也就是在两个队列里面进行数据倒换。文字比较抽象，所以接下来看图帮助理解。

二、模拟“ 栈 ”实现的功能

2.1 MyStack* myStackCreate()//初始化

根据我们之前对题目的分析可以知道我们要创建两个队列，所以我们就在结构体里面定义两个队列。

typedef struct //匿名结构体
{
    Queue s1;//创建两个队列
    Queue s2;

} MyStack;

再对里面的结构体的队列进行初始化！，因为我们前面写的队列是基于单链表完成，要动态开辟空间。所以要malloc一下。具体操作如下：

MyStack* myStackCreate()//初始化
{
    MyStack* pst = (MyStack* )malloc(sizeof(MyStack));
    if(pst==NULL)
    {
        perror("malloc fail");
        return -1;
    }
    QueueInit(&(pst->s1));
    QueueInit(&(pst->s2));

    return pst;
}

2.2 myStackPush(MyStack* obj, int x)//插入数据

我们要进行插入数据，就要想明白。我们要实现栈的特点 “ 后进先出 ”。我们这里插入数据任何一个队列中都是一样的。所以我们分为，当两个队列都是空时，进行随便插入。如果一个队列有数据那就在这个有数据的队列进行继续插入。代码很简单，要理解为什么这样插入。

void myStackPush(MyStack* obj, int x)//插入数据
{
    if(!QueueEmpty(&(obj->s1)))
    {
        QueuePush(&(obj->s1),x);//如果s1里面有数据就继续进行数据插入
    }
    else
    {
        QueuePush(&(obj->s2),x);//如果是s1为空那么就向s2里面插入数据
    }

}

2.3 myStackPop(MyStack* obj)//删除并且返回栈定元素

我们这里要实现删除栈顶元素并返回栈顶元素。我们这里采用了之前用到过的假设法，我们把不为空的队列里面数据倒换到为空的队列，这样我们就只需要把不为空里面的数据进行pop（删除）就可以了，因为还要返回栈顶元素 so 我们要把最后一个数据储存后进行pop在返回栈顶元素。

千万注意要把不为空里面数据pop！！

int myStackPop(MyStack* obj)//删除并且返回栈定元素
{
    //假设法
    MyStack* empty = &(obj->s1);
    MyStack* nonempty = &(obj->s2);
    if(!QueueEmpty(&(obj->s1)))
    {
        empty = &(obj->s2);
        nonempty = &(obj->s1);
    }
    while(QueueSize(nonempty) > 1 )
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int ret = QueueFront(nonempty);
     QueuePop(nonempty);

     return ret;
}

2.4 myStackTop(MyStack* obj) //获取栈顶元素

获取栈顶元素就很简单了，直接返回队列的最后一个数据就可以了。在这之前我们判一下空，不然一个空队列里面都没有数据怎么返回栈顶元素。

int myStackTop(MyStack* obj) //获取栈顶元素
{
    if(!QueueEmpty(&obj->s1))
    {
        return QueueBack(&obj->s1);
    }
    else
    {
        return QueueBack(&obj->s2);
    }
}

2.5 myStackEmpty(MyStack* obj) //判空

因为判空用到的地方比较多建议早点写他！ 很简单我们把两个队列与一下在返回就可以了。

return QueueEmpty(&obj->s1) && QueueEmpty(&obj->s2);

2.6 myStackFree(MyStack* obj) //销毁

销毁我们要小心一点，因为我们不仅仅动态申请了Mystack的空间，我们还动态申请了队列的空间。所以两个队列也要进行销毁。我们直接调用我们之前写的队列销毁函数后，进行free操作。

还要进行置为空指针。

void myStackFree(MyStack* obj) //销毁
{
    QueueDestory(&obj->s1);
    QueueDestory(&obj->s2);

    free(obj);
    obj=NULL;
}

三、代码展示

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

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

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

void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* pur = pq->phead;

	while (pur)
	{
		QNode* cur = pur->next;
		free(pur);
		pur = cur;
	}

	pq->phead = 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");
		return;
	}
	Newnode->next = NULL;
	Newnode->val = x;

	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)//只有一个节点
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else//多个节点
	{
		QNode* tmp = pq->phead->next;
		free(pq->phead);
		pq->phead = tmp;
	}
	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;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

typedef struct //匿名结构体
{
    Queue s1;//创建两个队列
    Queue s2;

} MyStack;


MyStack* myStackCreate()//初始化
{
    MyStack* pst = (MyStack* )malloc(sizeof(MyStack));
    if(pst==NULL)
    {
        perror("malloc fail");
        return -1;
    }
    QueueInit(&(pst->s1));
    QueueInit(&(pst->s2));

    return pst;
}

void myStackPush(MyStack* obj, int x)//插入数据
{
    if(!QueueEmpty(&(obj->s1)))
    {
        QueuePush(&(obj->s1),x);
    }
    else
    {
        QueuePush(&(obj->s2),x);
    }

}

int myStackPop(MyStack* obj)//删除并且返回栈定元素
{
    //假设法
    MyStack* empty = &(obj->s1);
    MyStack* nonempty = &(obj->s2);
    if(!QueueEmpty(&(obj->s1)))
    {
        empty = &(obj->s2);
        nonempty = &(obj->s1);
    }
    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->s1))
    {
        return QueueBack(&obj->s1);
    }
    else
    {
        return QueueBack(&obj->s2);
    }
}

bool myStackEmpty(MyStack* obj) //判空
{
    return QueueEmpty(&obj->s1) && QueueEmpty(&obj->s2);
}

void myStackFree(MyStack* obj) //销毁
{
    QueueDestory(&obj->s1);
    QueueDestory(&obj->s2);

    free(obj);
    obj=NULL;
}

总结

我们这里的代码都是基于队列来实现的，我们要掌握这个倒换数据思路来解题。好了谢谢大家的观看！！下期见ヾ(•ω•`)o

原文地址:https://blog.csdn.net/2302_80867815/article/details/140383731 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1812601978082168832.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部