栈：一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

2. 栈的使用


public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
//        将e入栈，并返回e
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
//        将栈顶元素出栈并返回
        System.out.println(stack.pop());
//        获取栈顶元素
        System.out.println(stack.peek());
//        检测栈是否为空
        System.out.println(stack.empty());
//        获取栈中有效元素个数
        System.out.println(stack.size());
        System.out.println(stack);
    }

3. 自己动手实现栈（使用动态数组实现栈）

1. 创建一个MyStack类

思路图：


import java.util.Arrays;
import java.util.NoSuchElementException;
//使用泛型
public class MyStack<E> {
    private Object[] data;
    private int size;
 
    public MyStack(int capacity){
        this.data = new Object[capacity];
    }
    public MyStack(){
        this.data = new Object[10];
    }
    
}

2. push入栈


public E push(E val){
        data[size ++] = val;
        if(size == data.length){
            data = Arrays.copyOf(data,data.length<<1);
        }
        return val;
    }

3. pop出栈


public E pop(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empy,cannot pop!");
        }
        E oldVal = (E)data[size - 1];
        size --;
        return oldVal;
    }

4. 查看栈顶元素


public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empy,cannot peek!");
        }
        return (E)data[size - 1];
    }

5. 判断栈是否为空与获取栈长


public boolean isEmpty() {
        return size == 0;
    }
    public int size(){
        return size;
    }

6. toString方法


public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("bottom [");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if(i < size - 1){
                sb.append(",");
            }
        }
        sb.append("] top");
        return sb.toString();
    }

4. 整体实现

4.1 MyStack类


package seqlist.stack_queue;
 
import java.util.Arrays;
import java.util.NoSuchElementException;
 
public class MyStack<E> {
    private Object[] data;
    private int size;
 
    public MyStack(int capacity){
        this.data = new Object[capacity];
    }
    public MyStack(){
        this.data = new Object[10];
    }
    public E push(E val){
        data[size ++] = val;
        if(size == data.length){
            data = Arrays.copyOf(data,data.length<<1);
        }
 
        return val;
    }
 
    public boolean isEmpty() {
        return size == 0;
    }
    public int size(){
        return size;
    }
    public E pop(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empy,cannot pop!");
        }
        E oldVal = (E)data[size - 1];
        size --;
        return oldVal;
    }
    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empy,cannot peek!");
        }
        return (E)data[size - 1];
    }
 
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("bottom [");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if(i < size - 1){
                sb.append(",");
            }
        }
        sb.append("] top");
        return sb.toString();
    }
}

4.2 Test类


public static void main(String[] args) {
        MyStack<Integer> stack = new MyStack<>();
//        将e入栈，并返回e
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println("将栈顶元素出栈并返回");
        System.out.println(stack.pop());
        System.out.println("获取栈顶元素");
        System.out.println(stack.peek());
        System.out.println("检测栈是否为空");
        System.out.println(stack.isEmpty());
        System.out.println("获取栈中有效元素个数");
        System.out.println(stack.size());
        System.out.println(stack);
    }

4.3 测试结果

【例题】一个栈的入栈序列为ABCDE，则不可能的出栈序列为（）

        A. ABCDE

        B. EDCBA

        C. DCEBA

        D. ECDBA

稳妥的做法是画图逐个选项检测，大概率是不会出错的，

如果是E先出，说明ABCDE都已经全部入栈，E出栈之后，此时栈顶元素是D，如果再要出栈应该是D，而不应该是C。故应该选择D。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/611829