剑指offer刷题总结——堆、栈、队列篇

港控/mmm° 2021-09-21 03:16 187阅读 0赞

### 1.用两个栈实现队列 ###

**【题目】**

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型。

**【代码】**

package swear2offer.construction;
    
    import java.util.Stack;
    
    public class StackToQueue { 
    
        /** * 用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型。 * * 栈的结构是先进后出，队列的结构是先进先出 * * */
    
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
    
        public void push(int node) { 
            stack1.add(node);
        }
    
        public int pop() { 
            if (stack2.empty()) { 
                while (!stack1.empty()) { 
                    stack2.add(stack1.pop());
                }
            }
    
            return stack2.pop();
        }
    
    }

**【思路】**

两个栈stack1和stack2，模拟队列的能力，插入元素直接插入stack1即可，因为存储元素只要保证保存下来，二者的区别关键是弹出元素的顺序，队列弹出的元素位于stack的最下面，所以需要把stack1的元素依次弹出，并放入stack2中，这样弹出元素的时候，只要stack2不为空，就弹出stack2的元素，stack2为空的时候，先把stack1的元素压入stack2，然后继续弹出stack2.

--------------------

### 2.栈的压入、弹出序列 ###

**【题目】**

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

**【代码】**

/** * 输入两个整数序列，第一个序列表示栈的压入顺序， * 请判断第二个序列是否可能为该栈的弹出顺序。 * 假设压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序， * 序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列， * 但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的） * */
    
        public boolean IsPopOrder(int [] pushA,int [] popA) { 
    
            int n,start,end,i,j;
    
            n = pushA.length;
    
            if (n == 0) return false;
    
            Stack<Integer> stack = new Stack<>();
    
            start = 0;
            end = GetIndex(pushA, popA[0]);
    
            if (end < 0) return false;
    
            // 把start和end之间的元素全部压入stack中
            for (j=start; j<=end; j++) { 
                stack.add(pushA[j]);
            }
    
            start = end + 1;
    
            i = 0;
            while (i < n) { 
                if (stack.peek() == popA[i]) { 
                    stack.pop();
                    i++;
                    continue;
                } else { 
                    end = GetIndex(pushA,popA[i]);
                    if (start > end) return false;
                    for (j=start; j<=end; j++) { 
                        stack.add(pushA[j]);
                    }
                    start = end + 1;
                }
            }
    
            return true;
    
        }
    
        // 或者数组指定元素的下标
        public int GetIndex(int[] a, int target) { 
    
            for(int i=0; i<a.length; i++) { 
                if (a[i] == target) { 
                    return i;
                }
            }
            return -1;
        }

**【思考】**

while循环和for循环，同样的 i<n 的条件，最重要的区别就是，while循环的次数是不确定的（大于，小于，等于n次都可以），而for循环必定是小于等于n次的。