【Leetcode】队列实现栈和栈实现队列

一.【Leetcode225】队列实现栈

1.链接

队列实现栈

2.题目再现

3.解法

这道题给了我们两个队列，要求去实现栈；

首先，我们要知道栈和队列的特征：

栈：后进先出，只能从栈顶入数据和出数据；

队列：先进先出，从队尾入数据，队头出数据；

根据这些特点，我们可以采用两边倒的方法来实现；

具体来说：

1.入栈时就是在不为空的队列插入数据，若两个队列都为空，就随便插入到一个队列中；

2.出栈时将不为空的队列的数据倒入为空的队列中，当不为空的队列就剩一个数据时，就停止向空队列倒数据，然后再删点那最后一个数据；

3.判空时，需要两个队列都为空，才算栈为空；

4.取栈顶元素即取不为空的队列的队尾元素，在取栈顶元素前要判断栈是否为空；

5.销毁栈时，要先销毁其中的两个队列，然后再销毁栈。

因为是用C语言实现的，所以得自己手搓个队列。

typedef int Qdatatype;

typedef struct QueueNode
{
    struct QueeuNode* next;
    Qdatatype data;
}QueueNode;

typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;
void Queueinit(Queue* pq)
{
    assert(pq);
    pq->head = NULL;
    pq->tail = NULL;
}

void Queuedestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;

    while (cur != pq->tail)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }

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

void Queuepush(Queue* pq, Qdatatype x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}

void Queuepop(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    QueueNode* next = pq->head->next;
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        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(Queuesize(pq) > 0);

    return pq->tail->data;
}

int Queuesize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur != pq->tail->next)
    {
        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() {
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj==NULL)
        exit(-1);
    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) {
    Queue*empty=&obj->q1;
    Queue*noempty=&obj->q2;
    if(!Queueempty(&obj->q1))
    {
        empty=&obj->q2;
        noempty=&obj->q1;
    }
    while(Queuesize(noempty)>1)
    {
        Queuepush(empty,Queuefront(noempty));
        Queuepop(noempty);
    }
    int front=Queuefront(noempty);
    Queuepop(noempty);
    return front;
}

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

二.【Leetcode232】栈实现队列

1.链接

栈实现队列

2.题目再现

3.解法

这个的解法和上面的类似，只不过这个不用总是来回倒；

根据栈和队列的特征，我们会发现将一个栈中的数据倒入另一个栈时，数据的顺序刚好符合队列的要求，不需要再重复地倒数据，所以我们可以让一个栈专门用来入数据（Pushst），一个栈专门用来出数据（Popst），当我们要出数据而这个栈为空时，我们才将用来入数据的栈中的数据倒入用来出数据的栈 。

如图：

1.判空时，需要两个栈都为空，队列才为空；

2.返回队头数据时，和出数据的操作类似，只是不需要删除队头的数据，还有在之前要判断队列是否为空；

3.销毁队列前，要先销毁两个栈。

同样，因为是C语言，得先手搓个栈。

#define MR_CAP 5
typedef int STdatatype;

typedef struct Stack
{
    STdatatype* arr;
    int top;
    int capacity;
}ST;

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

    ps->arr = (STdatatype*)malloc(MR_CAP * sizeof(STdatatype));
    if (ps->arr == NULL)
    {
        perror("Stackinit malloc");
        exit(-1);
    }

    ps->top = 0;
    ps->capacity = MR_CAP;
}

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

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

void Stackpush(ST* ps, STdatatype x)
{
    assert(ps);

    if (ps->top == ps->capacity)
    {
        STdatatype* tmp = (STdatatype*)realloc(ps->arr, ps->capacity * 2 * sizeof(STdatatype));
        if (tmp == NULL)
        {
            perror("Stackpush realloc");
            exit(-1);
        }
        else
        {
            ps->arr = tmp;
            ps->capacity *= 2;
        }
    }

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

void Stackpop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);

    ps->top--;
}

STdatatype Stacktop(ST* ps)
{
    assert(ps);

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

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

    return ps->top;

}

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

    if (ps->top == 0)
    {
        return true;
    }
    else
        return false;
     
}

typedef struct {
    ST Pushst;
    ST Popst;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
        exit(-1);
    Stackinit(&obj->Pushst);
    Stackinit(&obj->Popst);

    return obj;
}

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

int myQueuePeek(MyQueue* obj) {
     if(Stackempty(&obj->Popst))
    {
        while(!Stackempty(&obj->Pushst))
        {
            Stackpush(&obj->Popst,Stacktop(&obj->Pushst));
            Stackpop(&obj->Pushst);
        }
    }

    return Stacktop(&obj->Popst);
    
}

int myQueuePop(MyQueue* obj) {
   
    int front=myQueuePeek(obj);
    Stackpop(&obj->Popst);
    return front;
}

bool myQueueEmpty(MyQueue* obj) {

    return Stackempty(&obj->Pushst)&&Stackempty(&obj->Popst);
}

void myQueueFree(MyQueue* obj) {
    Stackdestroy(&obj->Pushst);
    Stackdestroy(&obj->Popst);

    free(obj);
}

🐲👻这两道题的讲解就到这里了，若有错误或是建议欢迎小伙伴们指出。🐯🤖

🥰🤩希望小伙伴们可以多多支持博主哦。😍😃

😁😄谢谢你的阅读。😼😸