社区首页 >专栏 >栈和队列的习题详解（3）：用栈实现队列

栈和队列的习题详解（3）：用栈实现队列

用户11295429

发布于 2024-10-16 09:03:51

11000

代码可运行

文章被收录于专栏：王的博客专栏王的博客专栏

运行总次数：0

代码可运行

前言：

小编在上一篇博客中写过了用队列实现栈的操作，可能很多读者朋友会好奇用两个栈是否可以实现队列呢》这是当然可以的，下面小编将要讲述用栈实现队列这个习题，废话不多说，开始今天的做题之旅~

正文：

1.用栈实现队列

老规矩，小编先把习题链接发过来：232. 用栈实现队列 - 力扣（LeetCode）

1.1.题干的解读

可能很多读者朋友看到这个题的时候和小编当时想的一样，这个题是不是和用队列实现栈一样的思路来写呢？就是两个栈之间进行来回倒数据来实现，这个题的确也是按照类似的思路来实现的，不过此时小编还得再说一下栈和队列的各自的特点，栈是后进先出，队列是先进先出，所以队列是第一个进去的元素第一个出去，而栈反而是第一个进去的元素最后一个除出去，所以小编当时也是想了很久也没想明白这个题是如何来写的，因为倒数据似乎也是有一点麻烦的，于是乎小编在听完老师的讲解以后，便了解了这个题其中一个解法，下面小编将会讲述这个题目的大致思路：

1.2.题目的解题思路

解决这个题目的思路类似倒数据，但是此时与上个题不一样的是，这里两个栈是分工明确的，我们可以让其中一个栈作为储存元素的，一个栈是用来进行出队列，取队头元素的；我们在使用队列实现栈的时候，两个队列是不确定的，有时候一个空一个不空，有时候一个不空另一个空，这么做是为了考虑各自的结构，栈是半封闭式，所以当我们想要删除队头元素的时候，我们仅需把那个储存数据的栈里面的数据通过提供栈顶元素之后出栈的方式，循环放入到另一个栈中，此时我们就可以发现第二个栈的元素和原来第一个栈的元素是倒置的，此时我们直接让第二个栈的元素出栈，这么做就可以实现出队列操作，因为出队列出的就是第一个，而我们将第一个栈的元素放入第二个栈以后，此时第一个栈的栈底元素就是第二个栈的栈顶元素，即进入栈的第一个因素，所以此时我们就可以实现出栈操作，而这也是小编为什么会讲两个栈的功能固定住，此时我们就实现了出队列操作，此时我们在现简单说一下队列每个功能的实现，对于入队列操作，我们直接把元素放入第一个栈就好；对于出队列操作，首先需要检测一下第二个栈是否有元素，如果有元素直接出栈就好，没有的话上面也说了，把第一个栈的元素循环放入第二个栈然后出栈；对于取栈顶元素，此时就和出队列是类似的，只不过我们直接返回第二个栈的栈顶元素就好了；至于初始化和销毁小编会在等会教写代码的时候说的，此时我们已经完成了队列的所有功能，可能很多读者朋友和我一样，光知道思路，但是代码不会写，下面小编将会讲述队列的功能如何用代码实现~

1.3.队列的功能实现

再讲解功能之前，我们首先需要写出这个队列的结构体，其实这个在小编在上面写解题思路就有体现，我们需要准备两个栈，分别是用来存储数据和消除数据的，其代码如下：

typedef struct {
    ST q1;  //存放数据的
    ST q2;  //进行出队列或者取队头操作的
} MyQueue;

1.3.1.队列的初始化（MyQueue* myQueueCreate()）

我们在写队列的时候肯定有初始化操作，首先我们需要先注意它的返回值，它的返回值是结构体指针，旨在说明我们需要创建一个队列指针，此时就要涉及动态内存的开辟了，我们需要开辟一个大小为结构体类型的变量的指针，在我们创建好以后，我们就要对里面的内容进行初始化，这时候我们仅需调用它们各自的初始化函数就好了，此时我们已经完成了初始化操作，我们直接返回这个指针即可，代码如下所示：

MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq -> q1);
    STInit(&pq -> q2);
    return pq;
}

1.3.2.入队列操作（void myQueuePush(MyQueue* obj, int x)）

入队列操作其实是很简单就可以实现的，此时我们讲我们想要的数据直接放入第一个栈就好，我们仅需调用一下入栈操作，把元素放入第一个栈即可，此时我们就实现了入队列操作，代码如下所示：

void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj -> q1,x);
}

1.3.3.判断队列是否为空（myQueueEmpty(MyQueue* obj)）

我们在进行出队列操作之前，我们需要去判断队列是否为空或者取队头数据的时候，如果为空的话我们就不可以再去进行出队列操作了，所以我们需要一个函数判断队列是否为空，此时队列为空的条件就是两个栈均为空，可能很多读者朋友要说，如果第二个栈就是空的，我们直接返回空不就好了，那样就大错特错了，还记着小编在上面的习题思路说过吗，对于出队列操作，我们首先需要判断第二个栈是否为空，如果第二个栈为空的话，我们直接把第一个栈的数据导入到第二个栈中，然后在出栈，所以第二个栈为空队列不一定就是空的，但如果第一个和第二个都是空的，那队列指定就是空的了，因为此时第一个栈就没元素倒入到第二个栈，第二个栈自然就无法实现出栈操作了，以上就是队列是否为空的实现，下面给予代码：

bool myQueueEmpty(MyQueue* obj) {
    return panduan(&obj -> q1) && panduan(&obj -> q2);
}

1.3.4.出队列操作（int myQueuePop(MyQueue* obj)）

这个操作便是所有功能实现最为复杂的部分了，不过小编会将它简单化的教给大家，首先我们需要先判断队列是否为空的，之后我们需要先判断第二个栈是否为空，此时我们可以直接调用判断栈是否为空的函数来检查此时第二个栈是不是空的，如果不为空，我们先保存栈顶数据，然后进行出栈操作，返回栈顶元素就好了；如果为空，此时我们需要进行倒数据，我们需要把第一个栈的数据通过循环的方式倒入到第二个栈，然后在进行不为空情况的操作，此时循环的条件就是栈中元素的个数，当栈中的元素个数为0时，此时我们就实现了数据的倒入，之后我们在进行保存栈顶的元素，然后出栈操作，返回栈顶元素即可，以上就是此函数功能的实现，可能很多读者朋友还是不明白其中原理，小编通过图文进行解释，此时我们栈里面依次放入1，2，3，如下图所示：

下面展示代码：

int myQueuePop(MyQueue* obj) {
    assert(!myQueueEmpty(obj));
    int size = STSize(&obj -> q1);
    if(STSize(&obj -> q2))
    {
        int b = STTop(&obj -> q2);
        STPop(&obj -> q2);
        return b;
    }
    //如果q2里面是空的，那么就执行下面操作
    while(size)
    {
        int front = STTop(&obj -> q1);
        STPush(&obj -> q2,front);
        STPop(&obj -> q1);
        size--;
    }
    int c = STTop(&obj -> q2);
    STPop(&obj -> q2);
    return c;
}

1.3.5.取队头操作（int myQueuePeek(MyQueue* obj)）

取队头操作其实是最简单的操作，当然是我建立在写完了出队列操作才说的，其实仔细看一看我们在写出队列操作的时候就已经展现出了取队头的操作，所以此时我们仅需把上面的代码复制下来，在把出队列操作删掉就好了，这便是这个操作的实现，是不是很简单，下面给出代码：

int myQueuePeek(MyQueue* obj) {
        assert(!myQueueEmpty(obj));
    int size = STSize(&obj -> q1);
    if(STSize(&obj -> q2))
    {
        int b = STTop(&obj -> q2);
        return b;
    }
    //如果q2里面是空的，那么就执行下面操作
    while(size)
    {
        int front = STTop(&obj -> q1);
        STPush(&obj -> q2,front);
        STPop(&obj -> q1);
        size--;
    }
    int c = STTop(&obj -> q2);
    return c;
}

1.3.6.销毁队列的操作（void myQueueFree(MyQueue* obj)）

销毁队列操作其实就是和上一篇写过的销毁栈操作是类似的，此时我们需要先把结构体里面的开辟出来的空间给释放掉，此时我们需要调用它们各自的销毁函数就好，操作结束后，由于此时的队列结构体也是开辟出来的，我们也需要释放掉，然后把它指向空就好，养成良好的习惯，减少野指针，这便是销毁操作的实现，下面给出代码：

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj -> q1);
    STDestroy(&obj -> q2);
    free(obj);
    obj = NULL;
}

以上便就是此队列所有结构函数的实现，现在肯定有很多读者朋友想要知道完整的代码怎么去写，下面小编就给出完整的代码：

1.4.代码展示

typedef int STDataType;
typedef struct Strak {
	STDataType* arr;   //存放的数据
	int caoticity;  //总空间大小
	int top;
}ST;

void STInit(ST* ps)
{
	ps->arr = NULL;
	ps->caoticity = ps->top = 0;
}



void STDestroy(ST* ps)
{
	if (ps->arr)
	{
		free(ps -> arr);
	}
	ps->arr = NULL;
	ps->caoticity = ps->top = 0;
}



void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->caoticity == ps->top)
	{
		int newcaseasd = ps->caoticity == 0 ? 4 : 2 * ps->caoticity;
		STDataType* arr1 = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newcaseasd);
		assert(arr1);
		ps->caoticity = newcaseasd;
		ps->arr = arr1;
	}//空间满了就进行扩容操作
	ps->arr[ps->top++] = x;
}



bool panduan(ST * ps)
{
	assert(ps);
	return ps->top == 0;
}
void STPop(ST* ps)
{
	assert(ps);
	assert(!panduan(ps));
	ps->top--;
}


STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!panduan(ps));
	return ps->arr[ps -> top - 1];
}

int STSize(ST* ps)
{
	return ps->top;
}


typedef struct {
    ST q1;  //存放数据的
    ST q2;  //进行出队列或者取队头操作的
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq -> q1);
    STInit(&pq -> q2);
    return pq;
}


bool myQueueEmpty(MyQueue* obj) {
    return panduan(&obj -> q1) && panduan(&obj -> q2);
}


void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj -> q1,x);
}

int myQueuePop(MyQueue* obj) {
    assert(!myQueueEmpty(obj));
    int size = STSize(&obj -> q1);
    if(STSize(&obj -> q2))
    {
        int b = STTop(&obj -> q2);
        STPop(&obj -> q2);
        return b;
    }
    //如果q2里面是空的，那么就执行下面操作
    while(size)
    {
        int front = STTop(&obj -> q1);
        STPush(&obj -> q2,front);
        STPop(&obj -> q1);
        size--;
    }
    int c = STTop(&obj -> q2);
    STPop(&obj -> q2);
    return c;
}

int myQueuePeek(MyQueue* obj) {
        assert(!myQueueEmpty(obj));
    int size = STSize(&obj -> q1);
    if(STSize(&obj -> q2))
    {
        int b = STTop(&obj -> q2);
        return b;
    }
    //如果q2里面是空的，那么就执行下面操作
    while(size)
    {
        int front = STTop(&obj -> q1);
        STPush(&obj -> q2,front);
        STPop(&obj -> q1);
        size--;
    }
    int c = STTop(&obj -> q2);
    return c;
}


void myQueueFree(MyQueue* obj) {
    STDestroy(&obj -> q1);
    STDestroy(&obj -> q2);
    free(obj);
    obj = NULL;
}