笔试大题20分值（用两个栈实现队列）

前言

目前博主在处于秋招求职的关键时期，在暑假这段时间会频繁更新博客，想在暑假期间把一些常考的面试和笔试题过一下，利用这两个月沉淀一下技术，做出一，两个比较大的项目，然后就是封装一下简历，开始投递了，我期待与26届所有毕业生一起学习共同进步。

一、原题

二、解题思路

1.s1用作入队栈，s2用作出队栈。

2.s1入队时，判断两个栈是否栈满了，如果满就算入队失败；如果s1满了，就将s1里的元素出栈入栈到s2,同时也要判断s2是否满了，如果满了就结束s1出栈，s2入栈这个操作，最后s1插入元素。

3.s2出队时，判断两个栈是否为空，如果为空就出队失败；如果s2为空，就将s1所有元素出栈入栈到s2,最后出栈元素。

三、代码实现（c/c++）

C语言代码

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

#define MaxSize 10
typedef int DataType_t;

typedef struct {
    DataType_t data[MaxSize];
    size_t top;
} Stack;

typedef struct {
    Stack s1;
    Stack s2;
} Queue;

void InitStack(Stack* stack) {
    stack->top = 0;
}

bool IsFull(Stack* stack) {
    return stack->top == MaxSize;
}

bool IsEmpty(Stack* stack) {
    return stack->top == 0;
}

bool Push(Stack* stack, DataType_t val) {
    if (IsFull(stack)) {
        printf("栈满，插入元素失败\n");
        return false;
    }
    stack->data[stack->top++] = val;
    return true;
}

bool Pop(Stack* stack, DataType_t* val) {
    if (IsEmpty(stack)) {
        printf("栈空，弹出元素失败\n");
        return false;
    }
    *val = stack->data[--stack->top];
    return true;
}

void InitQueue(Queue* queue) {
    InitStack(&queue->s1);
    InitStack(&queue->s2);
}

bool IsQueueEmpty(Queue* queue) {
    return IsEmpty(&queue->s1) && IsEmpty(&queue->s2);
}

bool IsQueueFull(Queue* queue) {
    return (queue->s1.top + queue->s2.top) == MaxSize;
}

bool Enque(Queue* queue, DataType_t val) {
    if (IsQueueFull(queue)) {
        printf("队满，入队失败\n");
        return false;
    }
    DataType_t temp;
    if (IsFull(&queue->s1)) {
        while (!IsEmpty(&queue->s1) && !IsFull(&queue->s2)) {
            Pop(&queue->s1, &temp);
            Push(&queue->s2, temp);
        }
    }
    return Push(&queue->s1, val);
}

bool Deque(Queue* queue, DataType_t* val) {
    if (IsQueueEmpty(queue)) {
        printf("队空，出队失败\n");
        return false;
    }
    DataType_t temp;
    if (IsEmpty(&queue->s2)) {
        while (!IsEmpty(&queue->s1)) {
            Pop(&queue->s1, &temp);
            Push(&queue->s2, temp);
        }
    }
    return Pop(&queue->s2, val);
}

C++代码实现

#include <iostream>
using namespace std;

const int MAX_SIZE = 100; // 栈的最大容量

// 栈结构定义
struct Stack {
    int data[MAX_SIZE];
    int top = -1; // 栈顶指针，初始为-1
};

// 栈操作函数
void push(Stack &ST, int x) {
    if (ST.top < MAX_SIZE - 1) {
        ST.data[++ST.top] = x; // 栈顶指针先加1，再入栈
    }
}

bool pop(Stack &ST, int &x) {
    if (ST.top == -1) return false; // 栈空，弹出失败
    x = ST.data[ST.top--]; // 取栈顶元素，指针减1
    return true;
}

bool isEmpty(Stack &ST) {
    return ST.top == -1; // 栈空返回 true
}

// 队列结构（由两个栈组成）
struct Queue {
    Stack s1, s2;
};

// 元素入队列
bool enQueue(Queue &q, int x) {
    if (q.s1.top == MAX_SIZE - 1) {
        // s1 已满，尝试转移元素到 s2
        if (!isEmpty(q.s2)) return false; // s2 非空，队列满，入队失败
        // 将 s1 的所有元素转移到 s2（逆序）
        while (!isEmpty(q.s1)) {
            int temp;
            pop(q.s1, temp);
            push(q.s2, temp);
        }
    }
    push(q.s1, x); // 新元素压入 s1
    return true;
}

// 元素出队列
bool deQueue(Queue &q, int &x) {
    if (!isEmpty(q.s2)) { // s2 非空，直接弹出
        pop(q.s2, x);
        return true;
    }
    // s2 为空，转移 s1 的元素到 s2
    while (!isEmpty(q.s1)) {
        int temp;
        pop(q.s1, temp);
        push(q.s2, temp);
    }
    if (isEmpty(q.s2)) return false; // 转移后仍为空，队列空
    pop(q.s2, x); // 弹出 s2 栈顶（即队首）
    return true;
}

// 判断队列是否为空
bool queueEmpty(Queue &q) {
    return isEmpty(q.s1) && isEmpty(q.s2); // 两栈均空时队列为空
}

int main() {
    Queue q;
    // 测试用例
    enQueue(q, 1);
    enQueue(q, 2);
    enQueue(q, 3);
    
    int x;
    deQueue(q, x); // 输出 1
    cout << "Dequeued: " << x << endl;
    
    deQueue(q, x); // 输出 2
    cout << "Dequeued: " << x << endl;
    
    cout << "Queue empty? " << queueEmpty(q) << endl; // 输出 0（非空）
    return 0;
}

结语

在做项目之前，我们的基础一定要打扎实，尤其是，这些简单的线性数据结构，你们学到后面会发现，好多存储结构都逃不掉，顺序存储结构和链式存储结构，一定要自己动手多敲，只有脑子有料，到后面做项目才会得心应手，否则你到后面根本学不下。

希望各位靓仔靓女点赞，收藏，关注多多支持，我们共同进步，后续我会更新更多的面试真题，你们的支持将是我前进最大的动力。