两个队列实现一个栈-----队列面试题3

问题

使用两个队列实现一个栈

这是 两个栈实现一个队列的孪生问题，对该问题解法不清楚的可以移步

两个栈实现一个队列—–队列面试题2

使用两个队列实现一个栈比其他的孪生问题来说，能复杂一些

思路

1. 设置一个队列为 queue1， 另一个为 queue2
2. 入栈时，将元素入队列非空队列
3. 出栈时，将非空队列的前 n-1 个元素出队列到另一个空队列中，然后出栈元素就是此时非空队列剩下的最后一个元素，出队列它即可
4. 获取栈顶元素与出栈同理

方法实现

在求解过程中，我们将使用顺序表实现的队列作为载体，所以对顺序表实现的队列和基本操作不清楚的可以移步

队列(顺序表实现)概念及相关函数

stackby2queue.h

#pragma once
#include "seqqueue.h"

typedef struct StackBy2 {
    SeqQueue queue1;
    SeqQueue queue2;
}StackBy2;

// 出栈
void StackBy2Pop(StackBy2* stack);

// 入栈
void StackBy2Push(StackBy2* stack, Datatype value);

// 获取栈顶元素
int StackBy2Top(StackBy2* stack, Datatype* value);

stackby2queue.c

内含单元测试函数，可以通过条件编译将测试模块关闭

#include "stackby2queue.h"

// 初始化队列
void SeqQueueInit(SeqQueue* queue) {
    // 非法输入
    if(queue == NULL) {
        perror("Init");
        return;
    }
    queue->head = queue->tail = 0;
    queue->size = 0;
}

// 销毁队列
void SeqQueueDestroy(SeqQueue* queue) {
    // 非法输入
    if(queue == NULL) {
        perror("Destroy");
        return;
    }
    queue->tail = queue->head = queue->size = 0;
}

// 入队列，尾插
int SeqQueuePush(SeqQueue* queue, Datatype value) {
    // 非法输入
    if(queue == NULL) {
        perror("Push");
        return;
    }
    // 1. 队列未满
    if(queue->size < MAX_SIZE-1) {
        // a. 已达到数组最后一个元素，从数组头开始存储
        if(queue->tail == MAX_SIZE-1) {
            queue->tail = 0;
            queue->data[queue->tail++] = value;
            queue->size++;
        }else {
            // b. 未达到，继续向后存储
            queue->data[queue->tail++] = value;
            queue->size++;
        }
    }else {
        // 2. 队列满
        // a. 尾插失败
        return 0;
    }
    return 1;   
}

// 出队列，头删
int SeqQueuePop(SeqQueue* queue) {
    // 非法输入
    if(queue == NULL) {
        perror("Pop");
        return 0;
    }
    // 空队列
    if(queue->size == 0) {
        return 0;
    }
    if(queue->head == MAX_SIZE-1) {
        queue->head = 0;
    }else {
        queue->head++;
        queue->size--;
    }
    return 1;
}

// 取队首元素
int SeqQueueTop(SeqQueue* queue, Datatype* value) {
    // 非法输入
    if(queue==NULL || value==NULL) {
        perror("Top");
        return 0;
    }
    // 空队列
    if(queue->size == 0) {
        return 0;
    }

    *value = queue->data[queue->tail-1];
    return 1;
}




/* ************************************************ * ******************** test********************** * ***********************************************/

#if 0
#include <stdio.h>

#define FUNCTION() printf("\n================ %s ===============\n", __FUNCTION__)

// 队列打印
void print(SeqQueue queue, const char* msg) {
    printf("\n%s\n", msg);

    int i = 0 ;
    int index = queue.head;
    printf("head = %d, 队首:>\n", i);
    for( ; i < queue.size; i++) {
        if(index == MAX_SIZE) {
            index = 0;
        }   
        printf("%c\n", queue.data[index]);
        index++;
    }
}

// 入队列测试
void TestPush() {
    FUNCTION();
    SeqQueue queue;
    SeqQueueInit(&queue);

    SeqQueuePush(&queue, 'a');
    SeqQueuePush(&queue, 'b');
    SeqQueuePush(&queue, 'c');
    SeqQueuePush(&queue, 'd');
    print(queue, "入队列1，2，3，4");
}

// 出队列测试
void TestPop() {
    FUNCTION();
    SeqQueue queue;
    SeqQueueInit(&queue);   
    SeqQueuePush(&queue, 'a');
    SeqQueuePush(&queue, 'b');
    SeqQueuePush(&queue, 'c');
    SeqQueuePush(&queue, 'd');
    print(queue, "队列初始化");

    int ret = SeqQueuePop(&queue);
    SeqQueuePop(&queue);
    print(queue, "出队列两个");

    SeqQueuePop(&queue);
    print(queue, "出队列一个");

    SeqQueuePop(&queue);
    print(queue, "出队列一个");

    SeqQueuePop(&queue);
    print(queue, "空队列出队列");
}

// 取栈顶元素测试
void TestTop() {
    FUNCTION();
    SeqQueue queue;
    SeqQueueInit(&queue);   
    SeqQueuePush(&queue, 'a');
    SeqQueuePush(&queue, 'b');
    SeqQueuePush(&queue, 'c');
    SeqQueuePush(&queue, 'd');
    print(queue, "队列初始化");

    Datatype value;
    SeqQueueTop(&queue, &value);
    printf("top is %c\n", value);

    // 销毁队列
    SeqQueueDestroy(&queue);
    print(queue, "销毁队列");
}

int main() {
    TestPush();
    TestPop();
    TestTop();

    return;
}
#endif