栈:一种特殊的线性表,其**只允许在固定的一端进行插入和删除元素操作(表的末端)。**进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。
对栈的基本操作有push
(入栈)和pop
(出栈),前者相当于插入,后者则时删除最后插入的元素。
栈又称为 LIFO(后进先出)表。
栈在生活中的例子:
方法 | 功能 |
---|---|
Stack() | 构造一个空的栈 |
E push(E e) | 将e入栈,并返回e |
E pop() | 将栈顶元素出栈并返回 |
E peek() | 获取栈顶元素 |
int size() | 获取栈中有效元素的个数 |
boolean empty() | 检测栈是否为空 |
定义一个数组,用于存储栈的元素
public int[] elem;
定义一个变量,用于记录栈的有效元素个数
public int usedSize;
定义一个常量NUMBER
,其值为10,表示栈的默认大小
public static final int NUMBER = 10;
构造方法,初始化栈
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];
}
}
定义方法判断栈是否已满(即是否还有入栈空间):如果usedSize
等于数组长度,则表示栈已满,返回true
;否则返回false
public boolean isFull() {
return usedSize == elem.length;
}
判断栈是否已满(usedSize
等于数组长度),则需要扩展数组的大小),使用Arrays.copyOf
方法将原数组复制一份,长度为原数组的两倍
public void push(int val) {
if (isFull()) {
this.elem = Arrays.copyOf(elem,2 * elem.length);
}
}
将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++;
}
判断栈是否为空,如果为空则抛出异常
if (isEmpty()) {
throw new EmptyStackException("栈空");
}
EmptyStackException
异常类:
public class EmptyStackException extends RuntimeException{
public EmptyStackException() {
}
public EmptyStackException(String message) {
super(message);
}
}
不为空则usedSize
- 1,表示有一个元素出栈
usedSize--;
返回usedSize
位置的元素值(即栈顶元素)
return elem[usedSize];
出栈完整代码:
public int pop() {
if (isEmpty()) {
throw new EmptyStackException("栈空");
}
usedSize--;
return elem[usedSize];
}
判断栈是否为空,如果为空则抛出异常
if (isEmpty()) {
throw new EmptyStackException("栈空");
}
返回uesedSize - 1
位置的元素值(即栈顶元素)
return elem[usedSize - 1];
如果usedSize
等于0,则表示栈为空,返回true
;否则返回false
public boolean isEmpty() {
return usedSize == 0;
}
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);
}
}