1. AI技术聚合首页
  2. IT

速学数据结构 | 我不允许还有人不会用栈实现队列！

扎眼的阳光 • • IT • 阅读 44


🎬 鸽芷咕：个人主页

 🔥个人专栏:《Linux深造日志》《C++干货基地》
⛺️生活的理想，就是为了理想的生活!

📋 前言

  🌈hello！ 各位铁铁们大家好啊，不知道大家对栈和队列的学习都学过了吧？那么用栈来实现队列你会做嘛？
  ⛳️栈和队列我们前面说了都是一种特殊的线性表，而在学习过程中用栈来尝试实现队列是很有必要来考验一下我们对栈和队列的掌握的！
  📚本期文章收录在《数据结构&算法》，大家有兴趣可以看看呐！
  ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝！

文章目录

  • 📋 前言
  • 一、 栈实现队列具体要求
  • 二、栈实现队列的核心思想
    • 2.1 如何插入的思想
    • 2.2 如何插入呢？
  • 三、栈实现队列的代码实现
      • 3.1 栈实现队列的初始化
      • 3.2 栈实现队列判空
      • 3.3 栈实现队列的插入
      • 3.4 栈实现队列删除
      • 3.5 栈实现队列的头元素
      • 3.6 栈实现队列的销毁
  • 四、栈实现队列的成果检验
  • 📝全篇总结

一、 栈实现队列具体要求

二、栈实现队列的核心思想

  • 栈和队列一个后进先出一个先进先出先先在下图看一下我们的区别：

2.1 如何插入的思想

栈的特点是后进先出而我们要实现的队列是先进先出，诶这刚好和队列的特点相反：

  • 那么我们使用俩个栈
  • 一个用来插入数据
  • 一个用来把插入的数据翻转一下就不可以实现 先进先出的特点 了？

2.2 如何插入呢？

前面说了使用俩个栈来解决队列先进先出的问题，其核心思想就是

  • 一个栈来当 push 栈存放数据
  • 一个栈用来pop数据

那么具体的核心思想是什么？其实只需要把push的 翻转一下然后插入到pop 栈中就好了，这样我们就可以的到一个理论上先进先出的队列了。

  • 每次 pop 的时候都拿翻转完了之后的栈
  • 如何 pop 没有数据了就继续从 push 里面翻转导入数据。

三、栈实现队列的代码实现

核心思路我们有了接下来就是如何实现了，插入和删除解决了。其他问题那就不是问题非常简单就解决了，下面我们来看看把！

3.1 栈实现队列的初始化

初始化和以前一样既然需要俩个栈来模拟实现队列，那么就需要俩个指针来管理栈区就够了：

  • 空间还是和以前 malloc 就好了。
  • 先创建队列的空间在 ， malloc 的空间。

📚 代码演示：

typedef struct {
    ST pushst;
    ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* new = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&new->pushst);
    STInit(&new->popst);

    return new;
}

3.2 栈实现队列判空

判空这就巨简单了，既然我们用了俩个栈来实现队列那么只要这俩个栈都为空不就行了。

  • 核心思想 STEmpty(&obj->pushst) && STEmpty(&obj->popst)
  • 判断栈区是否为空使用栈的判断就好了

📚 代码演示：

bool myQueueEmpty(MyQueue* obj) {

    return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}

3.3 栈实现队列的插入

插入这个就是最简单的了，直接往push栈里面插入就好了：

📚 代码演示：

void myQueuePush(MyQueue* obj, int x) {

    STPush(&obj->pushst,x);
}

3.4 栈实现队列删除

删除队列就是我们前面的思想:

  • 每次取pop 栈里面的元素
  • 如果 pop 为空的话那么就从 push栈里面 翻转导入就好了。

📚 代码演示：

int myQueuePop(MyQueue* obj) {
    if(STEmpty(&obj->popst))
    {
        while(STSize(&obj->pushst))
        {
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }

    int top = STTop(&obj->popst);   
    STPop(&obj->popst);

    return top;
}

3.5 栈实现队列的头元素

头元素的的访问就很简单了，我们 pop 栈的第一个栈顶元素就是头元素：

  • 去直接访问就好了。
  • 但是要注意 pop 为空的时候就需要导入一下了。

📚 代码演示：

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->popst))
    {
        while(STSize(&obj->pushst))
        {
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }

    return STTop(&obj->popst);
}

3.6 栈实现队列的销毁

销毁还是和以前一样，把malloc的空间都销毁：

  • 然后再销毁队列本身的空间

📚 代码演示：

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);

    free(obj);
}

四、栈实现队列的成果检验

好了以上就是栈实现队列的全过程了：

  • 对应练习题在这里: 用栈实现队列

📚 代码演示：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>


//#define N 10
//struct Stack
//{
//	int a[N];
//	int top;
//};

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);

int STSize(ST* ps);
bool STEmpty(ST* ps);


void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	// 11:40
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);

	// 
	assert(ps->top > 0);

	--ps->top;
}

STDataType STTop(ST* ps)
{
	assert(ps);

	// 
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}


typedef struct {
    ST pushst;
    ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* new = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&new->pushst);
    STInit(&new->popst);

    return new;
}

void myQueuePush(MyQueue* obj, int x) {

    STPush(&obj->pushst,x);
}

int myQueuePop(MyQueue* obj) {
    if(STEmpty(&obj->popst))
    {
        while(STSize(&obj->pushst))
        {
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }

    int top = STTop(&obj->popst);   
    STPop(&obj->popst);

    return top;
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->popst))
    {
        while(STSize(&obj->pushst))
        {
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }

    return STTop(&obj->popst);
}

bool myQueueEmpty(MyQueue* obj) {

    return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);

    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

📝全篇总结

☁️ 好了以上就是栈的实现队列的全部解析了，总的来说只要掌握技巧就不难呢！核心思想掌握了那就直接秒杀.
看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！
💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
扎眼的阳光的头像扎眼的阳光普通用户
0
上一篇 2023年12月19日
下一篇 2023年12月19日

相关推荐