自学内容网 自学内容网
自学内容网 > 正文

队列及其应用（用栈实现队列 力扣225）

🕗 发布于 2024-07-21 17:03 leetcode  算法  职场和发展  

队列概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

队列的代码实现

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

typedef int QDataType;

typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;

typedef struct Queue
{
QNode* phead;//链表头，方便删除头结点
QNode* ptail;//链表尾，方便插入新节点
int size;
}Queue;

void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//销毁
void QueuePush(Queue* pq, QDataType x);//队尾插入
void QueuePop(Queue* pq);//对头删除
int QueueSize(Queue* pq);//链表长度
QDataType QueueFront(Queue* pq);//获取头结点
QDataType QueueBack(Queue* pq);//获取尾节点
bool QueueEmpty(Queue* pq);//判断是否为空队列


#include"Queue.h"

void QueueInit(Queue* pq)
{
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
assert(pq);

QNode* cur = pq->phead;
while (cur) {
QNode* temp = cur->next;
free(cur);
cur = temp;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* temp = (QNode*)malloc(sizeof(QNode));
if (temp == NULL) {
perror("malloc fail");
return;
}
temp->next = NULL;
temp->val = x;
if (pq->ptail == NULL) {
pq->phead = pq->ptail = temp;
}
else
{
pq->ptail->next = temp;
pq->ptail = temp;
}
pq->size++;


}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size!=0);
QNode* temp = pq->phead->next;
free(pq->phead);
pq->phead = temp;
if (pq->phead == NULL) {
pq->ptail = NULL;
}
pq->size--;
}
int QueueSize(Queue* pq) {
assert(pq);
return pq->size;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}
bool QueueEmpty(Queue* pq) {
assert(pq);
return pq->size == 0;
}

队列的应用

难点在于，队列只在队尾插入元素，而在队头删除元素。所以在用队列模拟实现栈的时候，我们可以轻松用队列push功能实现栈的push，而栈的pop则要另想方法。

例如，

让q1前面的元素迁移到q2，并pop掉。当q1只剩4的时候，就可以把4删掉；而剩下的数据保存在q2中。这样就可以实现栈的pop功能。

然后每次push元素的时候就push到不为空的队列，删除元素的时候仿造上述过程。

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

typedef int QDataType;

typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;

typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
void QueueInit(Queue* pq)
{
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur) {
QNode* temp = cur->next;
free(cur);
cur = temp;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* temp = (QNode*)malloc(sizeof(QNode));
if (temp == NULL) {
perror("malloc fail");
return;
}
temp->next = NULL;
temp->val = x;
if (pq->ptail == NULL) {
pq->phead = pq->ptail = temp;
}
    else{
    pq->ptail->next = temp;
pq->ptail = temp;
    }
pq->size++;

}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size!=0);
QNode* temp = pq->phead->next;
free(pq->phead);
pq->phead = temp;
if (pq->phead == NULL) {
pq->ptail = NULL;
}
pq->size--;
}
int QueueSize(Queue* pq) {
assert(pq);
return pq->size;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}
bool QueueEmpty(Queue* pq) {
assert(pq);
return pq->size == 0;
}


typedef struct {
    Queue q1;
    Queue 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(!QueueEmpty(&obj->q1)){
        QueuePush(&(obj->q1),x);
    }
    else{
        QueuePush(&(obj->q2),x);
    }
}

int myStackPop(MyStack* obj) {
    Queue*empty=&(obj->q1);
    Queue*nonEmpty=&(obj->q2);
    if(!QueueEmpty(&(obj->q1))){
        empty=&(obj->q2);
        nonEmpty=&(obj->q1);
    }
    while(QueueSize(nonEmpty)>1){
        QueuePush(empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }

    int top=QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    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));
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/


原文地址：https://blog.csdn.net/2301_79894844/article/details/140569243

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024