【数据结构与算法】6.栈

📚博客主页：爱敲代码的小杨.

✨专栏：《Java SE语法》

❤️感谢大家点赞👍🏻收藏⭐评论✍🏻，您的三连就是我持续更新的动力❤️

🙏小杨水平有限，欢迎各位大佬指点，相互学习进步！

文章目录

• 1. 栈
• 2. 栈的模拟实现
• 3. 完整代码

1. 栈

1.1 栈的概念

栈：一种特殊的线性表，其**只允许在固定的一端进行插入和删除元素操作（表的末端）。**进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

对栈的基本操作有push（入栈）和pop（出栈），前者相当于插入，后者则时删除最后插入的元素。

栈又称为 LIFO（后进先出）表。

栈在生活中的例子：

1.2 栈的使用

2. 栈的模拟实现

栈的定义

1. 定义一个数组，用于存储栈的元素

   public int[] elem; 
   

2. 定义一个变量，用于记录栈的有效元素个数

   public int usedSize; 
   

3. 定义一个常量NUMBER，其值为10，表示栈的默认大小

   public static final int NUMBER = 10;
   

4. 构造方法，初始化栈

   public MyStack() {  
       this.elem = new int[NUMBER];  
   }  
   

栈的定义完整代码：

public class MyStack {
    public int[] elem; // 定义一个数组
    public int usedSize; // 记录数组中数据有效的个数

    public static final int NUMBER = 10; // 默认数组长度为10

    public MyStack() {
        this.elem = new int[NUMBER];
    }
}

入栈（push操作）

1. 定义方法判断栈是否已满（即是否还有入栈空间）：如果usedSize等于数组长度，则表示栈已满，返回true；否则返回false

   public boolean isFull() {
   	return usedSize == elem.length;
   }
   

2. 判断栈是否已满（usedSize等于数组长度），则需要扩展数组的大小）,使用Arrays.copyOf方法将原数组复制一份，长度为原数组的两倍

   public void push(int val) {
       if (isFull()) {
           this.elem = Arrays.copyOf(elem,2 * elem.length);
       }
   }
   

3. 将val存入数组的usedSize位置，并将usedSize加1，表示有一个新元素入栈

elem[usedSize] = val;
usedSize++;

入栈完整代码：

public void push(int val) {
	if (isFull()) {
		this.elem = Arrays.copyOf(elem,2 * elem.length);
    }
    elem[usedSize] = val;
    usedSize++;
}

出栈（pop操作）

1. 判断栈是否为空，如果为空则抛出异常

   if (isEmpty()) {
   	throw new EmptyStackException("栈空");
   }
   

   EmptyStackException异常类：

   public class EmptyStackException extends RuntimeException{
       public EmptyStackException() {
       }
   
       public EmptyStackException(String message) {
           super(message);
       }
   }
   

2. 不为空则usedSize - 1，表示有一个元素出栈

   usedSize--;
   

3. 返回usedSize位置的元素值（即栈顶元素）

    return elem[usedSize];
   

出栈完整代码：

public int pop() {
	if (isEmpty()) {
		throw new EmptyStackException("栈空");
	}
	usedSize--;
	return elem[usedSize];
}

查看栈顶元素（peek操作）

1. 判断栈是否为空，如果为空则抛出异常

   if (isEmpty()) {
       throw new EmptyStackException("栈空");
   }
   

2. 返回uesedSize - 1位置的元素值（即栈顶元素）

   return elem[usedSize - 1];
   

判断栈是否为空

如果usedSize等于0，则表示栈为空，返回true；否则返回false

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

3. 完整代码

MyStack类：

import java.util.Arrays;

public class MyStack {
    public int[] elem; // 定义一个数组
    public int usedSize; // 记录数组中数据有效的个数

    public static final int NUMBER = 10; // 默认数组长度为10

    public MyStack() {
        this.elem = new int[NUMBER];
    }

    // 入栈
    public void push(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem,2 * elem.length);
        }

        elem[usedSize] = val;
        usedSize++;
    }

    // 判断数组是否存满数据
    public boolean isFull() {
        return usedSize == elem.length;
    }

    // 出栈
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException("栈空");
        }
        usedSize--;
        return elem[usedSize];
    }

    // 判断数组是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException("栈空");
        }
        return elem[usedSize - 1];
    }
}

EmptyStackException类：

public class EmptyStackException extends RuntimeException{
    public EmptyStackException() {
    }

    public EmptyStackException(String message) {
        super(message);
    }
}