【数据结构】栈和队列-相互实现OJ题

前言：

本题目是关于栈和队列的OJ题目，需对栈和队列有一定了解再进行做题，若不了解可以根据我之前这篇文章进行学习：【数据结构】栈和队列-CSDN博客,题中需要的栈和队列的实现也在该文章中有源代码

前言：

一.用队列实现栈

1.解题思路

2.解题代码

二.用栈实现队列

1.解题思路

2.解题代码

法一：

法二：

一.用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

1.解题思路

栈和队列区别在于出数据时的不同，栈遵循“后入先出”，而队列遵循“先入先出”，但在入数据时并没有不同，因此在Push时只需要依照队列的Push即可，将数据进入一个队列。

而在出数据时就不能直接出该队列的数据了，因为此处是模拟栈，需要移除的是队列中的最后一位（最晚进）的数据，而队列只能对队首的数据进行出操作，那么此时第二个队列（此时为空）就有用处了，将第一个队列（有数据的队列）的队首数据插入到第二个队列中，再进行出队，直到第一个队列仅剩最后一个数据（这个数据就是出栈操作要移除的数据），移除该数据不进行插入到第二个队列，如此第一个队列为空，第二个队列就是进行出栈操作后的结果了。

下图大致能演示这个模拟出栈的过程

2.解题代码

队列的实现前言中有，这里不贴出来浪费篇幅了。明白了上图所示的思路，那么整道题就好解决了。关键在于将两个队列分为空队列和非空队列，入栈时与入队操作相同，直接对非空队列（都为空则默认一个）入队即可，出栈时进行两队列的数据交换，其余函数根据两队列性质来即可。

typedef struct {
  Queue q1;
  Queue q2;  
} MyStack;

//初始化
MyStack* myStackCreate() {
    MyStack* s = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&(s->q1));
    QueueInit(&(s->q2));
    return s;
}

//判断非空与否的条件就是两个队列是否都为空
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

//入栈，与入队是相同的操作，只需要向非空的队列入队即可
void myStackPush(MyStack* obj, int x) {
    if(QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q2,x);
    }
    else
    {
        QueuePush(&obj->q1,x);
    }

}

//出栈，找到非空队列和空队列进行转换
//注：返回值int是栈顶数据，也就是非空队列的队尾数据（移动后最后一个数据，同时也是队首）
int myStackPop(MyStack* obj) {
    //找到空队列和非空队列
    Queue* empty = &(obj->q1);
    Queue* notempty = &(obj->q2);
    if(QueueEmpty(&obj->q2))
    {
        empty = &obj->q2;
        notempty = &obj->q1;
    }
    while(QueueSize(notempty)>1)
    {
        QueuePush(empty,QueueFront(notempty));
        QueuePop(notempty);
    }
    int ret = QueueFront(notempty);
    QueuePop(notempty);
    return ret;
}

//栈顶数据就是非空队列的队尾数据
int myStackTop(MyStack* obj) {
    if(QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q2);
    }
    else
    {
        return QueueBack(&obj->q1);
    }
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

二.用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

1.解题思路

与上道题同理，这次只是反了过来，用栈来实现队列，思路完全可以照搬，区别只在于用出栈模拟出队，不过有一点有差异，取出的栈顶元素（如图中4）插入到Stack2中顺序是相反的，因此需要来转换一下，这里我利用了数组下标进行转化的方法，具体实现方法在下文的方法一中。

不过这种方法比较麻烦，也不美观，破坏了封装性，不推荐。在这里给出另一个更为巧妙的方法，直接将两个Stack分为Pushst（插入）和Popst（删除）两个栈，分别对应插入删除，同样能实现。在需要删除时将Pushst中的数据倒如Popst中即可。巧妙的点在于倒数据的过程中，恰巧使得顺序颠倒，而出栈正好就满足了出队的要求，就如下图所示，具体代码在下方法二。

2.解题代码

法一：

本方法与前一题的方法如出一辙，思路简单，但不推荐。

typedef struct {
    ST s1;
    ST s2;
} MyQueue;


//初始化
MyQueue* myQueueCreate() {
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&q->s1);
    STInit(&q->s2);
    return q;
}

//对非空栈进行入栈
void myQueuePush(MyQueue* obj, int x) {
    if(STEmpty(&obj->s1))
    {
        STPush(&obj->s2,x);
    }
    else
    {
        STPush(&obj->s1,x);
    }
}

//出栈
int myQueuePop(MyQueue* obj) {
    //找出非空栈和空栈
    ST* empty = &obj->s1;
    ST* notempty = &obj->s2;
    if(STEmpty(&obj->s2))
    {
        empty = &obj->s2;
        notempty = &obj->s1;
    }

    //注意此处要用size保存，否则在后续循环内STPop时top变化会导致错误
    int size = notempty->top;
    //移入空栈（顺序是正确的）
    for(int i = 1;i<size;i++)
    {
        STPush(empty,notempty->a[i]);
    }
   
    //得到返回的数据，并将原非空栈Pop为空
    int ret = notempty->a[0];
    for(int i = 0;i<size;i++)
    {
        STPop(notempty);
    }
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->s1))
    {
        return obj->s2.a[0];
    }
    else
    {
        return obj->s1.a[0];
    }
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->s1) && STEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->s1);
    STDestroy(&obj->s2);
}

法二：

推荐该方法，更为巧妙简单。

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


MyQueue* myQueueCreate() {
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&q->Pushst);
    STInit(&q->Popst);
    return q;
}

//插入直接向Pushst插入即可
void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->Pushst,x);
}

//取得队首数据，但位于栈底，需要倒数据到另一个栈
int myQueuePeek(MyQueue* obj) {

    if(STEmpty(&obj->Popst))
    {
        //倒数据
        while(!STEmpty(&obj->Pushst))
        {
            STPush(&obj->Popst,STTop(&obj->Pushst));
            STPop(&obj->Pushst);
        }
    }
    
    return STTop(&obj->Popst);
}

//需要取得队首，使用peek既可以倒数据，又能得到队首数据，一举两得
int myQueuePop(MyQueue* obj) {
    int ret = myQueuePeek(obj);
    STPop(&obj->Popst);
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->Pushst) && STEmpty(&obj->Popst);
}

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

两种方法均能通过该题的全部样例。