c语言 数据结构 LeetCode 225.用队列实现栈（详解） ૮꒰ ˶• ༝ •˶꒱ა

题目详情：

思路：1.定义两个队列用于存储栈的数据，其中一个为空。

          2.对我们定义的栈进行入数据，就相当于对不为空的队列进行入数据。

          3.对我们定义的栈进行删除，相当于取出不为空的队列中的数据放到为空的队列中，直到此时只剩下一个数据；对剩下的数据进行取出后删除。也就相当于对当前的栈进行删除。（对于栈的顶删相当于对队列的尾删）

        3.返回栈的顶部元素

        4.销毁栈

 注意：用c语言实现队列，没法直接引用，这里需要自己创建一个队列，再完成上述操作。如果还不会队列的小伙伴可以看看我的这篇博客数据结构--队列【详解】~(˶‾᷄ꈊ‾᷅˵)~-CSDN博客

 队列的实现：

typedef int QDataType;

typedef struct QueueNode

{//队列的定义与声明

struct QueueNode* next;

QDataType data;

}QNode;

//创建一个结构体用于存储队列头尾指针

typedef struct Queue

{

QNode* head;

QNode* tail;

}Queue;

//初始化队列

void QueueInit(Queue* pq)

{

assert(pq);

pq->head = pq->tail = NULL;

}

//摧毁队列

void QueueDestory(Queue* pq)

{

assert(pq);

QNode* cur = pq->head;

while (cur)

{//存储下一个节点的指针，防止找不到和野指针的出现

QNode* next = cur->next;

free(cur);

cur = next;

}

pq->head = pq->tail = NULL;

}

// 队尾入

void QueuePush(Queue* pq, QDataType x)

{

assert(pq);//为队列开辟一个新节点

QNode* newnode = (QNode*)malloc(sizeof(QNode));

if (newnode == NULL)

{

printf("malloc fail\n");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;

//若第一个节点为空，则head和tail指向第一个节点

if (pq->tail == NULL)

{

pq->head = pq->tail = newnode;

}//如果不是空，就让尾指针指向新节点，并移动尾指针方便下一次插入

else

{

pq->tail->next = newnode;

pq->tail = newnode;

}

}

// 队头出

void QueuePop(Queue* pq)

{

assert(pq);

assert(pq->head);

// 1、一个，直接释放第一个节点的内存

// 2、多个，要记得保存第一个节点的下一个节点的位置，防止找不到

if (pq->head->next == NULL)

{

free(pq->head);

pq->head = pq->tail = NULL;

}

else

{

QNode* next = pq->head->next;

free(pq->head);

pq->head = next;

}

}

//返回队头节点的数据

QDataType QueueFront(Queue* pq)

{

assert(pq);

assert(pq->head);

return pq->head->data;

}

//返回队尾节点的数据

QDataType QueueBack(Queue* pq)

{

assert(pq);

assert(pq->head);

return pq->tail->data;

}

//返回队列的大小

int QueueSize(Queue* pq)

{

assert(pq);

int size = 0;//这里用cur记录节点的个数

QNode* cur = pq->head;

while (cur)

{

++size;

cur = cur->next;

}

return size;

}

//判断节点是否为空

bool QueueEmpty(Queue* pq)

{

assert(pq);

return pq->head == NULL;

}

 用队列实现栈的函数实现：

//定义一个结构体用于存放两个队列

typedef struct {

Queue q1;

Queue q2;

} MyStack;

//用队列创造栈

MyStack* myStackCreate() {//用ps开辟空间，作为栈存储数据

MyStack* ps=(MyStack*)malloc(sizeof(MyStack));

if(ps==NULL)

{

printf("malloc fail\n");

exit(-1);

}

QueueInit(&ps->q1);

QueueInit(&ps->q2);

return ps;

}

//用队列入栈

void myStackPush(MyStack* obj, int x) {

if(!QueueEmpty(&obj->q1))//选择不为空的那个队列入

{

QueuePush(&obj->q1,x);

}

else

{

QueuePush(&obj->q2,x);

}

}

//用队列进行出栈操作

int myStackPop(MyStack* obj) {

Queue* emptyQ=&obj->q1;//将不为空的队列的数据转移到为空的队列，直到只剩一个

Queue* nonemptyQ=&obj->q2;

if(!QueueEmpty(&obj->q1))

{

emptyQ=&obj->q2;

nonemptyQ=&obj->q1;

}

while(QueueSize(nonemptyQ)>1)

{

QueuePush(emptyQ,QueueFront(nonemptyQ));

QueuePop(nonemptyQ);

}

int top=QueueFront(nonemptyQ);

QueuePop(nonemptyQ);

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

QueueDestory(&obj->q1);

QueueDestory(&obj->q2);

free(obj);

}

 注意：摧毁栈时要先摧毁obj下所对应的队列，再进行free(obj)。如果先free(obj),就无法找到对应的队列了

完整代码： 

typedef int QDataType;

typedef struct QueueNode

{//队列的定义与声明

struct QueueNode* next;

QDataType data;

}QNode;

//创建一个结构体用于存储队列头尾指针

typedef struct Queue

{

QNode* head;

QNode* tail;

}Queue;

//初始化队列

void QueueInit(Queue* pq)

{

assert(pq);

pq->head = pq->tail = NULL;

}

//摧毁队列

void QueueDestory(Queue* pq)

{

assert(pq);

QNode* cur = pq->head;

while (cur)

{//存储下一个节点的指针，防止找不到和野指针的出现

QNode* next = cur->next;

free(cur);

cur = next;

}

pq->head = pq->tail = NULL;

}

// 队尾入

void QueuePush(Queue* pq, QDataType x)

{

assert(pq);//为队列开辟一个新节点

QNode* newnode = (QNode*)malloc(sizeof(QNode));

if (newnode == NULL)

{

printf("malloc fail\n");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;

//若第一个节点为空，则head和tail指向第一个节点

if (pq->tail == NULL)

{

pq->head = pq->tail = newnode;

}//如果不是空，就让尾指针指向新节点，并移动尾指针方便下一次插入

else

{

pq->tail->next = newnode;

pq->tail = newnode;

}

}

// 队头出

void QueuePop(Queue* pq)

{

assert(pq);

assert(pq->head);

// 1、一个，直接释放第一个节点的内存

// 2、多个，要记得保存第一个节点的下一个节点的位置，防止找不到

if (pq->head->next == NULL)

{

free(pq->head);

pq->head = pq->tail = NULL;

}

else

{

QNode* next = pq->head->next;

free(pq->head);

pq->head = next;

}

}

//返回队头节点的数据

QDataType QueueFront(Queue* pq)

{

assert(pq);

assert(pq->head);

return pq->head->data;

}

//返回队尾节点的数据

QDataType QueueBack(Queue* pq)

{

assert(pq);

assert(pq->head);

return pq->tail->data;

}

//返回队列的大小

int QueueSize(Queue* pq)

{

assert(pq);

int size = 0;//这里用cur记录节点的个数

QNode* cur = pq->head;

while (cur)

{

++size;

cur = cur->next;

}

return size;

}

//判断节点是否为空

bool QueueEmpty(Queue* pq)

{

assert(pq);

return pq->head == NULL;

}

//定义一个结构体用于存放两个队列

typedef struct {

Queue q1;

Queue q2;

} MyStack;

//用队列创造栈

MyStack* myStackCreate() {//用ps开辟空间，作为栈存储数据

MyStack* ps=(MyStack*)malloc(sizeof(MyStack));

if(ps==NULL)

{

printf("malloc fail\n");

exit(-1);

}

QueueInit(&ps->q1);

QueueInit(&ps->q2);

return ps;

}

//用队列入栈

void myStackPush(MyStack* obj, int x) {

if(!QueueEmpty(&obj->q1))//选择不为空的那个队列入

{

QueuePush(&obj->q1,x);

}

else

{

QueuePush(&obj->q2,x);

}

}

//用队列进行出栈操作

int myStackPop(MyStack* obj) {

Queue* emptyQ=&obj->q1;//将不为空的队列的数据转移到为空的队列，直到只剩一个

Queue* nonemptyQ=&obj->q2;

if(!QueueEmpty(&obj->q1))

{

emptyQ=&obj->q2;

nonemptyQ=&obj->q1;

}

while(QueueSize(nonemptyQ)>1)

{

QueuePush(emptyQ,QueueFront(nonemptyQ));

QueuePop(nonemptyQ);

}

int top=QueueFront(nonemptyQ);

QueuePop(nonemptyQ);

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

QueueDestory(&obj->q1);

QueueDestory(&obj->q2);

free(obj);

}

博客到这里也是结束了，喜欢的小伙伴可以点赞加关注支持下博主，这对我真的很重要~~

好文推荐