Track a changing queue
Track a changing queue
The video could not load. Check your connection and try again, or download it directly.
Download video
Open Chinese transcript
- 队伍开始是甲、乙、丙、丁。动作有先后,必须一步一步更新,不能同时猜结果。
- 第一步乙离开。删掉乙以后,剩下甲、丙、丁,三人的相对顺序不变。
- 第二步戊站到丙前面。先找到丙,再把戊插在丙的左边。
- 新队伍变成甲、戊、丙、丁。乙已不在队中,不能又写回来。
- 核对其余人:甲仍在丙前,丙仍在丁前,只有题目指定的离开和插入发生。
- 所以最终顺序是甲、戊、丙、丁。队列题要保存每一步的新状态。
Sources for this explanation
Logical thinking
Update the queue after each removal or insertion while preserving all other relative order.
Worked example
The queue is A, B, C, D. B leaves and E stands before C. What is the final order?
Remove B to get A,C,D, then insert E before C to get A,E,C,D.
Try one question
Remove C, then insert E before B: A E B D.