用两个栈实现一个队列的功能?要求给出算法和思路!
设2个栈为A,B, 一开始均为空.
入队:
将新元素push入栈A;
出队:
(1)判断栈B是否为空;
(2)如果不为空,则将栈A中所有元素依次pop出并push到栈B;
(3)将栈B的栈顶元素pop出;
这样实现的队列入队和出队的平摊复杂度都还是O(1), 比上面的几种方法要好。
import java.util.Stack; public class AlgorithmTest20190818 { /** * 用两个栈实现队列(先进先出) * 实现思路: * (1)stack1作为队尾栈,元素每次进队列都放到队尾栈的栈顶。 * (2)stack2作为队头栈,元素每次出队列都从队头栈出队。 * (3)当队头栈为空时,将队尾栈的元素循环出栈放到队头栈。队尾栈栈底的元素(先排队的元素)就会变成队头栈的栈顶元素,可以优先出栈(即出队)。 * * @param args */ public static void main(String[] args) { int[] arr = {1, 2, 3}; for (int i = 0; i < arr.length; i++) { push(arr[i]); } System.out.println(pop()); System.out.println(pop()); push(4); System.out.println(pop()); push(5); System.out.println(pop()); System.out.println(pop()); } /** * 队尾栈 */ static Stack<Integer> stack1 = new Stack<Integer>(); /** * 队头栈 */ static Stack<Integer> stack2 = new Stack<Integer>(); public static void push(int node) { stack1.push(node); } public static int pop() { if(stack1.empty() && stack2.empty()){ throw new RuntimeException("队列为空!"); } if (stack2.size() == 0) { // 将队尾栈的元素全部放到队头栈 while (!stack1.empty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } }
import java.util.Stack; public class QueeByStack { /** * @param args * @throws Exception */ public static void main(String[] args) throws Exception { QueeByStack qbs = new QueeByStack(); qbs.put(1); qbs.put(2); qbs.put(3); qbs.put(4); qbs.out(); qbs.out(); qbs.put(5); qbs.put(6); qbs.put(7); qbs.out(); } private Stack<Integer> stack1 =new Stack<Integer>(); private Stack<Integer> stack2 =new Stack<Integer>(); public void put(Integer t){ stack1.push(t); //System.out.println(t); } public void out() throws Exception{ if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } if(stack2.isEmpty()){ throw new Exception("队列为空,无法删除"); } //return stack2.pop(); System.out.println(stack2.pop()); } }