用队列实现栈(C)

时间:2024-04-10 17:18:58

目录

题目:

解题:

代码讲解:

1.构建

2.creat

3.压栈

4.出栈

5.判空

6.释放


题目:

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppop 和 empty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

提示:

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

首先要实现队列

队列的实现-CSDN博客

解题:

整体思路:

利用队列的功能函数,实现栈的基本功能。


//Create类似于初始化

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) {          //返回Pop的值
    
    Q* E_Queue = &obj->q1;   //假设q1是空链表
    Q* None_E_Queue = &obj->q2;   

    if (!QueueEmpty(&obj->q1))  //肯定一个为空、一个不为空
    {
       E_Queue = &obj->q2;
       None_E_Queue = &obj->q1;
    }

    while (QueueSize(None_E_Queue) > 1)        //QueueSize     :  元素个数
    {

        QueuePush(E_Queue, QueueFront(None_E_Queue));     //将头元素传递
        QueuePop(None_E_Queue);

    }

    QDatetype top = QueueFront(None_E_Queue);
    QueuePop(None_E_Queue);

    return top;

}

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

    //不能只释放obj,obj只是含有q1 q2两个成员(q1 、q2只包含指针,只释放该空间,本质是释放掉phead 、ptail 、size 三个成员,无法释放队列的节点)
    
}

代码讲解:

1.构建

typedef struct {        //第三层嵌套(->)

   

    Q q1;       //两个链表

    Q q2;

} MyStack;

两个队列,组成一个栈

2.creat

MyStack* myStackCreate() {          //不传参,希望你创造一个结构体去初始化,再返回

   

    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));   //开辟空间

    QueueInit(&obj->q1); //->的优先级高于&

    QueueInit(&obj->q2); //->的优先级高于&

    return obj;

}

creat功能可以理解为:开辟空间、初始化

3.压栈

void myStackPush(MyStack* obj, int x) {     //往不为空的入数据

   

    if (!QueueEmpty(&obj->q1))   //往不为空的队列录入数据

    {

        QueuePush(&obj->q1, x);

    }

    else

    {

        QueuePush(&obj->q2, x);

    }

}

压栈:往不为空的队列Push元素

4.出栈


 

int myStackPop(MyStack* obj) {          //返回Pop的值

   

    Q* E_Queue = &obj->q1;   //假设q1是空链表

    Q* None_E_Queue = &obj->q2;  

    if (!QueueEmpty(&obj->q1))  //肯定一个为空、一个不为空

    {

       E_Queue = &obj->q2;

       None_E_Queue = &obj->q1;

    }

    while (QueueSize(None_E_Queue) > 1)        //QueueSize     :  元素个数

    {

        QueuePush(E_Queue, QueueFront(None_E_Queue));     //将头元素传递

        QueuePop(None_E_Queue);

    }

    QDatetype top = QueueFront(None_E_Queue);

    QueuePop(None_E_Queue);

    return top;

}

出栈:

需要注意的是,当我们需要分情况对两个对象操作的时候,如果存在可以进行区分的方法,可以采用假设法。

可以先假设q1是空链表。当q1不会空,只需更该指针指向。

5.判空

bool myStackEmpty(MyStack* obj) {   //判空

    return QueueEmpty(&obj->q1)

        && QueueEmpty(&obj->q2);        //只有一个有元素,当两者都是空,栈才会空

   

}

进行判空时,需要两个都为空,stack才会为空

6.释放

void myStackFree(MyStack* obj) {

    QueueDestroy(&obj->q1);

    QueueDestroy(&obj->q2);

    free(obj);  

    //不能只释放obj,obj只是含有q1 q2两个成员(q1 、q2只包含指针,只释放该空间,本质是释放掉phead 、ptail 、size 三个成员,无法释放队列的节点)

   

}

释放:

需要注意的是:需要进行两方面的释放,1.对队列各个节点的释放(在调用队列函数时,开辟了节点)。 2.对creat函数中malloc的my_stack空间的释放。my_stack只包括两个队列phead、ptail、和size三个元素。