栈（Java）

目录

1.什么是栈

2.栈的使用

3.栈的模拟实现

---

1.什么是栈

栈：是一种特殊的线性表，只允许在其固定的一端进行插入和删除操作。栈中的元素遵循先进后出（后进先出）原则

栈顶：进行插入和删除数据的一端

栈底：始终不进行插入和删除操作的一端

压栈：栈的插入操作，也可叫做进栈、入栈

出栈：栈的删除操作

压栈和出栈都在栈顶 

栈类似于弹夹，栈中的元素类似于子弹，最先放入弹夹中的子弹最后打出，最后放入弹夹中的子弹最先打出，同样的，先入栈的元素后出栈，后入栈的元素先出栈

2.栈的使用

栈中存储的是相同类型的数据，因此可以使用链表或是数组来实现栈，而在Java中，提供了Stack类，是用数组实现的栈。

Stack类位于 java.util 包中，使用前需要导包 

import java.util.Stack;

Stack的构造方法：

 Stack()

无参构造方法，构造一个空的栈

Stack stack = new Stack<>();

常用的方法：

E push(E e)

作用：将e入栈，并返回e 

class Test{
    public static void main(String[] args) {
        Stack stack = new Stack<>();//创建一个空的栈，栈中存放数据类型为Integer
        stack.push(3);//将3压入栈中，并返回3
        stack.push(55);
        System.out.println(stack.push(44));//输出：33
        System.out.println(stack);//输出：[3, 55, 44]
    }
}

 E pop()

作用：将栈顶元素出栈并返回

class Test{
    public static void main(String[] args) {
        Stack stack = new Stack<>();
        stack.push(22);
        stack.push(33);
        System.out.println(stack.pop());//输出：33
    }
}

 若栈中无元素，调用pop()方法，会抛出异常 EmptyStackException 

E peek()

作用：获取栈顶元素，但不将栈顶元素出栈

class Test{
    public static void main(String[] args) {
        Stack stack = new Stack<>();
        stack.push(22);
        stack.push(33);
        stack.push(44);
        System.out.println(stack.peek());//输出：44
        System.out.println(stack);//输出：[22, 33, 44]
    }
}

若栈中无元素，调用peek()方法时，也会抛出异常 EmptyStackException 

int size()

作用：获取栈中有效元素个数

boolean empty()

作用：判断栈是否为空

class Test{
    public static void main(String[] args) {
        Stack stack = new Stack<>();
        stack.push(22);
        stack.push(33);
        stack.push(44);
        System.out.println(stack.size());//输出：3
        System.out.println(stack.isEmpty());//输出：false
    }
}

3.栈的模拟实现

我们可以使用链表或是数组来模拟栈

（1）使用数组模拟实现栈

先定义栈，和栈的构造方法

public class MyStack {
    private int[] elem;//使用数组模拟实现栈
    private int usedSize;//表示有效长度，同时也可表示当前位置可以存放元素
    private static final int DEFAULT_CAPACITY = 10;
    public MyStack(){
        //初始化栈
        this.elem = new int[DEFAULT_CAPACITY];
    }
}

计算栈中元素个数

//计算栈中元素个数
public int size(){
    return this.usedSize;
}

判断栈是否为空

若usedSize为0则表明栈中没有元素，返回true，反之，返回false

public boolean empty(){
    return usedSize == 0;
}

入栈

将元素放入栈中，首先要判断栈是否满了，若满了，则需要先扩容，再将元素放入栈中

//入栈
public void push(int data){
    //先判断栈是否满
    if(usedSize == elem.length){
        //扩容
        elem = Arrays.copyOf(elem,2*elem.length);
    }
    //将data放入栈中，并将usedSize+1
    elem[usedSize++] = data;
}

出栈

若栈为空，则抛出异常；不为空，则将栈顶元素出栈

public int pop(){
    if(empty()){
        throw new EmptyStackException();
    }
    int data = elem[usedSize-1];
    usedSize--;
    return data;
}

获取栈顶元素

若栈为空，抛出异常；不为空，返回栈顶元素

public int peek(){
    if(empty()){
        throw new EmptyStackException();
    }
    int data = elem[usedSize-1];
    return data;
}

完整代码

import java.util.Arrays;
import java.util.EmptyStackException;
 
public class MyStack {
    private int[] elem;//使用数组模拟实现栈
    private int usedSize;//表示有效长度，同时也可表示当前位置可以存放元素
    private static final int DEFAULT_CAPACITY = 10;
    public MyStack(){
        //初始化栈
        this.elem = new int[DEFAULT_CAPACITY];
    }
    //计算栈中元素个数
    public int size(){
        return this.usedSize;
    }
    //判断栈是否为空
    public boolean empty(){
        return usedSize == 0;
    }
    //入栈
    public void push(int data){
        //先判断栈是否满
        if(usedSize == elem.length){
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        //将data放入栈中，并将usedSize+1
        elem[usedSize++] = data;
    }
    //出栈
    public int pop(){
        if(empty()){
            throw new EmptyStackException();
        }
        int data = elem[usedSize-1];
        usedSize--;
        return data;
    }
    //获取栈顶元素
    public int peek(){
        if(empty()){
            throw new EmptyStackException();
        }
        int data = elem[usedSize-1];
        return data;
    }
}

（2）使用链表模拟实现栈

public class MyStack {
    static class ListNode {
        private int val;
        private ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    private ListNode head;
    private int size;
    //判断栈是否为空
    public boolean empty(){
        return size == 0;
    }
    //计算栈中元素个数
    public int size(){
        return size;
    }
    //入栈
    public void push(int data){
        ListNode node = new ListNode(data);
        //头插
        if(empty()) {
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;
        }
        size++;
    }
    //出栈
    public int pop(){
        if(empty()){
            throw new EmptyStackException();
        }
        //头删
        int data = head.val;
        head = head.next;
        size--;
        return data;
    }
    //查看栈顶元素
    public int peek(){
        if(empty()){
            throw new EmptyStackException();
        }
        return head.val;
 
    }
    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
}