当前位置：首页 > ds >正文

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

ds 2025/7/20 15:01:18

前言

目前博主在处于秋招求职的关键时期，在暑假这段时间会频繁更新博客，想在暑假期间把一些常考的面试和笔试题过一下，利用这两个月沉淀一下技术，做出一，两个比较大的项目，然后就是封装一下简历，开始投递了，我期待与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--]; // 取栈顶元素，指针减1return 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 已满，尝试转移元素到 s2if (!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); // 新元素压入 s1return true;
}// 元素出队列
bool deQueue(Queue &q, int &x) {if (!isEmpty(q.s2)) { // s2 非空，直接弹出pop(q.s2, x);return true;}// s2 为空，转移 s1 的元素到 s2while (!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); // 输出 1cout << "Dequeued: " << x << endl;deQueue(q, x); // 输出 2cout << "Dequeued: " << x << endl;cout << "Queue empty? " << queueEmpty(q) << endl; // 输出 0（非空）return 0;
}