思路用两个栈实现一个队列。分别实现appendTail函数【队列尾部插入节点】和deleteHead【队列头部删除节点】功能
- 我们首先要注意栈和队列的特点:栈顶元素是最晚加入的元素,而对于队列来说,尾元素是最晚加入的元素;栈底元素对应队列首元素。
- 基于以上特点,我们不难发现,当stack1依次出栈到stack2后,此时stack2栈顶元素对应队列首元素,因此deleteHead的实现直接通过stack2出栈即可。
- 而appendTail的实现直接通过stack1入栈即可,因为此时栈顶元素对应的就是队列的尾元素。
public static void appendTail(Stackstack1,char val) { //将val插入到队尾 stack1.push(val); } public static void deleteHead(Stack stack1, Stack stack2) { if(stack2.isEmpty()) { //说明此时stack1的栈底才是队首 while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } //删除队首元素 stack2.pop(); }else { //说明此时队首在stack2栈顶 stack2.pop(); } }
题目来源于《剑指Offer:名企面试官精讲经典编程题》



