拓展题 用两个栈实现队列

Background

  队列是一种先进先出（FIFO）的数据结构，而栈是一种后进先出（LIFO）的数据结构。本题要求使用两个栈来模拟队列的行为，这是一个经典的数据结构设计问题，涉及到摊还分析的重要概念。

  通过这个问题，学生将深入理解栈和队列的特性差异，掌握如何巧妙地利用栈的特性来实现队列操作，并学会分析算法的摊还时间复杂度。

Description

  请仅使用两个栈来实现一个队列，支持以下三种操作：

• push(x)：将元素 x 添加到队列尾部
• pop()：从队列头部移除元素
• front()：获取队列头部元素（不移除）

  要求每个操作的摊还时间复杂度为 $O(1)$，并在实验报告中详细说明摊还分析过程。

输入格式

  第一行为一个正整数 $T$，表示操作的总数。

  接下来 $T$ 行，每行描述一个操作：

• push x：将整数 x 添加到队列尾部
• pop：从队列头部移除元素
• front：查询队列头部元素

输出格式

  对于每个 front 操作，输出一行，包含队列头部的元素值。

  对于每个 pop 操作，如果队列不为空则输出 "pop success"，否则输出 "error: empty queue"。

  push 操作不需要输出。

样例 #1

样例输入 #1

8
push 1
push 2
front
pop
push 3
front
pop
front

样例输出 #1

1
pop success
2
pop success
3

样例 #2

样例输入 #2

6
push 5
push 10
pop
push 15
front
pop

样例输出 #2

pop success
10
pop success

算法要求

1. 空间限制：只能使用两个栈数据结构
2. 时间复杂度：每个操作的摊还时间复杂度必须为 $O(1)$
3. 正确性：必须严格按照队列的FIFO特性执行操作

摊还分析提示

  考虑以下关键点：

• 每个元素最多被移动多少次？
• 单次操作的最坏时间复杂度是多少？
• 如何通过摊还分析证明平均时间复杂度为 $O(1)$？