栈面试题

001什么是栈？

栈是一种后进先出（Last in First Out）的数据结构，简称 LIFO。栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

002栈的基本使用

public static void main(String[] args) {
    Stack < Integer > stack = new Stack < Integer > ();
    //入栈
    stack.push(3); //栈底
    stack.push(4);
    stack.push(5);
    stack.push(7); //栈顶
    //出栈：弹出栈顶元素
    System.out.println(stack.pop()); //7
    //再弹一次，此时栈顶元素为5了，如下。
    System.out.println(stack.pop());
    //获取栈顶元素但不删除,这时的栈顶元素以及是4了
    System.out.println(stack.peek());
    //判断栈顶元素是否为空
    System.out.println(stack.empty());
    Stack < Integer > stack1 = new Stack < > ();
    System.out.println(stack1.empty());
    //获取栈中的元素的位置，栈顶为1号，此时stack中有3,4两个元素，所以4元素的位置为1号
    System.out.println(stack.search(4));
    //使用父类的方法，stack继承自Vector
    System.out.println(stack.isEmpty());
}

003下列关于栈叙述正确的是( )。

A. 栈顶元素最先能被删除
B. 栈顶元素最后才能被删除
C. 栈底元素永远不能被删除
D. 栈底元素最先被删除
答案: A    
解析：栈里面的元素都有被删除的机会，只不过栈顶的元素最先删除，栈底的元素最后删除。

004一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是 ( )。

A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
答案: B   
解析：B中1比3先进入，所以1在3之后出来。

005在栈中,( )保持不变。

A. 栈的顶
B. 栈的底
C. 栈指针
D. 栈中的数据
答案: B   
解析：暂无解析。

006new 创建对象时，对象的内存和指向对象的指针分别分配在( ).

A. 堆区，栈区
B. 常量区，堆区
C. 全局区，栈区
D. 栈区，堆区
答案: A   
解析：对象放在堆去，引用放在栈区。

007假设用S表示进栈操作，用X表示出栈操作。如果元素的进栈顺序是abcd，为了得到出栈序列abcd，则相应的S和X的操作序列为( )？

A. SSSSXXXX
B. SSSXXSXX
C. SXSSXXSX
D. SXSXSXSX
答案：D
解析：按照选项中的操作会得到的出栈顺序如下
选项A中，abcd进栈，依次出栈，得到出栈顺序是dcba；
选项B中，abc进栈，cb出栈，d进栈，da出栈，得到出栈顺序是cbda；
选项C中，a进栈，a出栈，bc进栈，cb出栈，d进栈，d出栈，中得到出栈顺序是acbd；
选项D中，a进栈，a出栈，b进栈，b出栈，c进栈，c出栈，d进栈，d出栈，中得到出栈顺序是abcd；所以正确选项为D。

008设若入栈序列的元素顺序为X,Y,Z，判断下列哪一个出栈序列是不可能的( )。

A. XYZ
B. YZX
C. ZXY
D. ZYX
答案: C   
解析：因为栈是先进后出，X在Y之前进入，所以X肯定在Y之后出来，所以ZXY不可能。

009设计一个获取栈中最小元素的栈

class MinStack {
    private Stack < Integer > stack;
    private Stack < Integer > minStack;

    public MinStack() {
        stack = new Stack < > ();
        minStack = new Stack < > ();
    }

    public void push(int val) {
        stack.push(val);
        if (!minStack.empty()) {
            int top = minStack.peek();
            if (val <= top) {
                minStack.push(val);
            }
        } else {
            minStack.push(val);
        }
    }

    public void pop() {
        int popVal = stack.pop();
        if (!minStack.empty()) {
            int top = minStack.peek();
            if (top == popVal) {
                minStack.pop();
            }
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

010判断某个数组是否是正确的出栈顺序。

public class Demo5 {
    public static void main(String[] args) {
        int[] A = {
            1, 2, 3, 4, 5
        };
        int[] B = {
            4, 5, 3, 2, 1
        };
        System.out.println(IsPopOrder(A, B));
    }
    public static boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack < Integer > stack = new Stack < > ();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j < popA.length && !stack.empty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}