服务周到的上海网站建设公司,南京做网站南京乐识赞,罗湖网站公司,昆山网站建设公司目录 前言 1. 题目#xff1a;使用队列实现栈 2. 思路 3. 分析 3.1 创建栈 3.2入栈 3.3 出栈 3.4 栈顶数据 3.5 判空和 “ 栈 ” 的销毁 4. 题解 总结 前言 我们已经学习了栈和队列#xff0c;也都实现了它们各自的底层接口#xff0c;那么接下我们就要开始栈和队列的专项刷… 目录 前言 1. 题目使用队列实现栈 2. 思路 3. 分析 3.1 创建栈 3.2入栈 3.3 出栈 3.4 栈顶数据 3.5 判空和 “ 栈 ” 的销毁 4. 题解 总结 前言 我们已经学习了栈和队列也都实现了它们各自的底层接口那么接下我们就要开始栈和队列的专项刷题训练。 1. 题目使用队列实现栈
题目描述 题目链接
队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/ 2. 思路 队列的结构是先进先出题目的要求是让我们利用队列的底层接口来实现栈不可以改变队列的底层逻辑所以如果你的思路是逆置队列这个链表那这个思路就被pass掉了。 那我们要如何利用队列尾进头出的特性来实现栈的尾进尾出呢题目中给了我们两个队列我们要使用这两个队列实现栈。 入栈操作好说问题在于出栈问题思路是这样的我们有两个队列一个队列用于存储数据另外一个队列空队列用于拷贝数据将原队列的前n-1个数据拷贝到空队列中然后再将原队列剩余的最后一个元素出队列这样就模拟实现了栈的尾出。 3. 分析 根据上述的思路分析队列实现栈入栈不需要什么特殊操作例如我们入栈1、2、3、4、5出栈呢就是5、4、3、2、1。 上述的思路已经介绍了解决办法也是非常简单的但有人可能会问那这样算法的效率岂不是很低这种方法的效率确实低但是这道题目考察的并不是效率的问题而实性质问题这也是一道经典的面试题目。这道题目并不难但它考察对数据结构的理解各各接口的实现中有很多需要注意的细节。 首先这道题目是并没有给现成的队列使用C语言解决需要我们现成造轮子这也是C语言刷题的弊端有很多题目都需要造轮子。那么这里我们就可以直接复制前边我们实现的队列。 接下来就是我们开始注意实现接口 首先题目中给了我们两个队列为了便于传参和使用我们可以定义一个结构体
typedef struct {
Que q1; //注意这里定于的队列类型一定要与自己定义的队列结构体类型对应
Que q2;
} MyStack; 这里我们在前边介绍结构体时提到过匿名结构体。 3.1 创建栈
MyStack* myStackCreate() {} 题目给出的接口如上那这里我们要怎么创建我们的栈呢是这样吗
MyStack* myStackCreate() {MyStack st;//…return st;
} 对函数和指针比较熟悉的同学可能就已经发现不行为什么不行这里就牵扯到了函数相关的知识函数内创建的变量都是存储在栈区出了函数就会被销毁内存已经被销毁返回指针还有什么意义呢所以这里需要使用malloc函数动态内存分配开辟的空间在堆区程序结束前不主动释放就一直存在。所以上述的创建变量的方法不可取。
正确的方法
MyStack* myStackCreate() {MyStack* pst(MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);QueueInit(pst-q2);return pst;
} 这里的pst-q1,就等价于我们在创建的队列的结构体变量Que q在调用接口时需要传地址过去。
3.2入栈 接下来就是入栈题目中给了我们两个队列为了后续出栈操作我们需要确保一个队列为空用于拷贝数据所以我们入栈时需要在不为空的队列入。
void myStackPush(MyStack* obj, int x) {if(!IsEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}
如果两个都为空那就随便选一个都可以。
3.3 出栈 在进行出栈操作的时候我们需要判断哪一个队列为空然后将非空队列的前n-1个元素依次拷贝到空队列当中。这里我们可以先假设队列1为空然后在判断队列1是否为空如果不为空那就是队列2为空进行修改。这个假设的方法还是很实用的。 拷贝过程如下 注意这里是拷贝不是将原队列的节点插入到空队列而是通过队头数据这个函数接口来将数据传过去然后入队调用入队接口入队之后及时更新队头出队。 int myStackPop(MyStack* obj) {Que* Emptyobj-q1;Que* NoEmptyobj-q2;if(!IsEmpty(obj-q1)){Emptyobj-q2;NoEmptyobj-q1;}while(QueueSize(NoEmpty)1){QueuePush(Empty,QueueFront(NoEmpty));QueuePop(NoEmpty);}int topQueueFront(NoEmpty);//最后保存非空队列最后一个队列节点的数据便于返回QueuePop(NoEmpty); //最后一个元素出队。return top;
} 3.4 栈顶数据 栈顶数据接口实现就简单了我们前边对队列进行实现时有队头和队尾数据的接口我们可以直接调用。
int myStackTop(MyStack* obj) {if(!IsEmpty(obj-q1)){return QueueBlack(obj-q1);}else{return QueueBlack(obj-q2);}
}3.5 判空和 “ 栈 ” 的销毁 判空就很简单如果两个队列都为空那么这个 “ 栈 ” 也就为空。
bool myStackEmpty(MyStack* obj) {return (IsEmpty(obj-q1)IsEmpty(obj-q2));
} “ 栈 ”的销毁这里就不能直接free掉obj了如果直接释放那我们程序中的两个队列就会丢失无法释放所以在释放掉obj之前我们需要先将两个队列销毁。
void myStackFree(MyStack* obj) {DestoryQueue(obj-q1);DestoryQueue(obj-q2);free(obj);
} 4. 题解 完整代码如下
typedef int Datatype;
typedef struct QueueNode
{struct QueueNode* next;Datatype data;}QueueNode;
typedef struct Queue
{QueueNode* head;QueueNode* tail;int size;
}Que;
//初始化队列
void QueueInit(Que* pq);
//入队
void QueuePush(Que* pq, Datatype x);
//出队
void QueuePop(Que* pq);
//队头数据
Datatype QueueFront(Que* pq);
//队尾数据
Datatype QueueBlack(Que* pq);
//判空
bool IsEmpty(Que* pq);
//队列大小
int QueueSize(Que* pq);
//销毁队列
void DestoryQueue(Que* pq);void QueueInit(Que* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}
void QueuePush(Que* pq, Datatype x)
{assert(pq);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}
void QueuePop(Que* pq)
{assert(pq);assert(!IsEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QueueNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}
Datatype QueueFront(Que* pq)
{assert(pq);assert(!IsEmpty(pq));return pq-head-data;
}
Datatype QueueBlack(Que* pq)
{assert(pq);assert(!IsEmpty(pq));return pq-tail-data;
}
bool IsEmpty(Que* pq)
{assert(pq);return (pq-head NULL);
}
int QueueSize(Que* pq)
{assert(pq);return pq-size;
}
void DestoryQueue(Que* pq)
{assert(pq);QueueNode* cur pq-head;while (cur){QueueNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}
typedef struct {
Que q1;
Que 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(!IsEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}int myStackPop(MyStack* obj) {Que* Emptyobj-q1;Que* NoEmptyobj-q2;if(!IsEmpty(obj-q1)){Emptyobj-q2;NoEmptyobj-q1;}while(QueueSize(NoEmpty)1){QueuePush(Empty,QueueFront(NoEmpty));QueuePop(NoEmpty);}int topQueueFront(NoEmpty);QueuePop(NoEmpty);return top;
}int myStackTop(MyStack* obj) {if(!IsEmpty(obj-q1)){return QueueBlack(obj-q1);}else{return QueueBlack(obj-q2);}
}bool myStackEmpty(MyStack* obj) {return (IsEmpty(obj-q1)IsEmpty(obj-q2));
}void myStackFree(MyStack* obj) {DestoryQueue(obj-q1);DestoryQueue(obj-q2);free(obj);
} 总结 本文队列模拟实现栈让我们在实践中深入思考了数据结构的本质和应用为我们的编程能力和问题解决能力提供了锻炼。本期内容到此结束感谢阅读
