Java集合框架：栈、Stack详解_java栈

目录

一、栈

二、栈的使用

         1. Stack类

2. 栈的模拟实现

三、栈的应用场景

1. 改变元素的序列

2. 将递归转化为循环（如：逆序打印链表）

3. 栈的oj题练习（oj题中都用到了栈这种数据结构）

四、栈，虚拟机栈，栈帧的区别

---

前言

    栈是一种数据结构，一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。数据插入和删除的操作的一端称作栈顶，另一端称作栈底。栈中的数据元素遵守一个原则：先进后出。   

一、栈

 如下图解：

     栈中的数据元素遵循后进先出的原则（Last in first out）就像子弹的上膛操作和射击操作。

二、栈的使用

    在Java集合框架中，栈使用的具体类是Stack，（但是并不是只有Sack一个类可以当作栈来使用）接下来就具体介绍下集合框架中栈的使用。

 1. Stack类

    Stack类的方法的使用：

    栈方法的使用演示：

public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println(stack.size());
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack.size());
        System.out.println(stack.empty());
    }

要想真正了解Stack类中方法实现的逻辑最好还是模拟实现一个栈；

2. 栈的模拟实现

//用数组/顺序表实现的栈
//顺序栈
 
public class MyStack {
    public int[] elem;
    public int usedSize;
    public MyStack() {
        this.elem = new int[10];
    }
    //压栈
    public void push(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }
    //出栈
    public int pop() {
        if (isEmpty()) {
            throw new EmptyException("栈是空的！");
        }
        /*int val = elem[usedSize - 1];
        usedSize--;
        return val;*/
        return elem[--usedSize];
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }
    //求栈中元素个数
    public int size() {
        return usedSize;
    }
    //获取栈顶元素
    public int peek() {
        if (isEmpty()) {
            throw new EmptyException("栈是空的！");
        }
        return elem[usedSize - 1];
    }

三、栈的应用场景

1. 改变元素的序列

 2. 将递归转化为循环（如：逆序打印链表）

     几种打印链表的方式：

//递归打印链表(逆序打印链表)
    public void display3(ListNode pHead) {
        if (pHead == null) return;
        if (pHead.next == null) {
            System.out.print(pHead.val + " ");
            return;
        }
        display3(pHead.next);
        System.out.print(pHead.val + " ");
    }
 
    //用栈结构打印链表(逆序打印链表)
    public void display4() {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //遍历栈
        while (!stack.isEmpty()) {
            ListNode top = stack.pop();
            System.out.print(top.val + " ");
        }
        System.out.println();
    }
    //遍历打印链表
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

3. 栈的oj题练习（oj题中都用到了栈这种数据结构）

四、栈，虚拟机栈，栈帧的区别