本文共 3367 字，大约阅读时间需要 11 分钟。

面试题9：用两个栈实现队列

用两个栈实现一个队列，该队列必须包含添加和删除的功能，分别完成在队尾添加和对头删除的功能。

设计思路：

• 添加的元素放到 stack1 中，当 stack1 满且 stack2 为空时，将 stack1 的元素全部添加到 stack2 中并继续添加。如果 stack1 满且 stack2 不为空，则提示占满，无法添加。
• 删除元素从 stack2 的栈顶删除，如果 stack2 为空，则将 stack1 的元素全部添加到 stack1 中；如果 stack1 也为空，则提示栈空，无法删除。

代码实现：

class Queue {
       Stack
   
     stack1 = new Stack<>();    Stack
    
      stack2 = new Stack<>();    int maxSize1;    int maxSize2;    public Queue(int maxSize1, int maxSize2) {
           this.maxSize1 = maxSize1;        this.maxSize2 = maxSize2;    }    public boolean isFull() {
           if(stack1.size() == maxSize1 && stack2.size() > 0) return true;        else return false;    }    public boolean isEmpty() {
           if(stack1.size() == 0 && stack2.size() == 0) return true;        else return false;    }    public void add(int value) {
           if(isFull()) {
               System.out.println("队列满，无法添加");            return;        } else {
               if(stack1.size() == maxSize1) {
                   while(!stack1.empty()) {
                       stack2.push(stack1.pop());                }            }            stack1.push(value);        }    }    public int delete() {
           if(isEmpty()) {
               throw new RuntimeException("队列空，无法删除");        }        if(stack2.isEmpty()) {
               while(!stack1.isEmpty()) {
                   stack2.push(stack1.pop());            }        }        return stack2.pop();    }}
    
   

相关题目：用两个队列实现一个栈

设计思想：

• 当一个队列中有元素时，另一个队列为空，作为临时的辅助队列
• 添加元素：往有元素的那个队列中添加，若那个队列满，则无法添加
• 删除，将有元素的队列中的元素添加到辅助队列，直到只剩下一个元素为止。

代码实现：

package Question09;import java.util.LinkedList;import java.util.Queue;/** * 用两个队列来模拟栈 */public class T02 {
       public static void main(String[] args) {
           MyStack stack = new MyStack(5, 5);        stack.add(5);        stack.add(3);        stack.add(2);        stack.add(1);        stack.add(7);        stack.add(4);        System.out.println(stack.delete());        System.out.println(stack.delete());    }}class MyStack {
       Queue
   
     queue1 = new LinkedList<>();    Queue
    
      queue2 = new LinkedList<>();    int maxSize1;    int maxSize2;    public MyStack(int maxSize1, int maxSize2) {
           this.maxSize1 = maxSize1;        this.maxSize2 = maxSize2;    }    public boolean isFull() {
           if(queue1.size() == maxSize1 || queue2.size() == maxSize2) {
               return true;        } else return false;    }    public boolean isEmpty() {
           if(queue1.size() == 0 && queue2.size() == 0) return true;        else return false;    }    public void add(int value) {
           if(isFull()) {
               System.out.println("队列满，无法加入");            return;        } else {
               if(!queue1.isEmpty()) {
                   queue1.offer(value);            } else {
                   queue2.offer(value);            }        }    }    public int delete() {
           if(isEmpty()) {
               throw new RuntimeException("队列为空，无法删除");        } else {
               if(!queue1.isEmpty()) {
                   while(queue1.size() != 1) {
                       queue2.offer(queue1.poll());                }                return queue1.poll();            } else {
                   while(queue2.size() != 1) {
                       queue1.offer(queue2.poll());                }                return queue2.poll();            }        }    }}
    
   

转载地址：http://objq.baihongyu.com/