- 一、栈是什么?
- 二、栈的实现
一、栈是什么?
栈是一种存储数据的结构,只能从一端插入,也只能从这一端取出元素。栈其实就是操作受限的线性表。
栈的特点: 先进后出,后进先出(LIFO)的线性表。添加和删除元素的一端称为栈顶,另一端称为栈底。
如上图,将1,2,3,4,5按顺序插入栈中,栈顶就保存的是5,栈底就是1。从栈中取出元素的顺序和栈中添加元素的顺序恰好相反。
基于数组实现的栈叫顺序栈,基于链表实现的栈叫链式栈。
只能在栈顶插入元素,在栈顶删除元素。
就是在数组的末尾插入和删除元素,此时的数组末尾就是栈顶。
栈的三个核心操作:
- push(E e) 向栈中添加元素 ,也叫入栈,或压栈。
- pop() 出栈操作,弹出栈顶元素。
- peek() 查看栈顶元素,但不出栈。
我们来实现一个基于动态数组的栈。
代码如下:
import java.util.ArrayList; import java.util.List; import java.util.NoSuchElementException; public class MyStack{ //记录当前元素个数 private int size; //实际存储数据的动态数组,此时在栈中只能在数组末尾添加和删除元素 private List data = new ArrayList<>(); //向当前栈中添加元素 public void push(E val) { //默认在数组的尾部插入 data.add(val); size++; } //出栈操作 public E pop() { //进行判空 if (isEmpty()) { throw new NoSuchElementException("栈空,无法出栈"); } //数组末尾删除元素,返回删除前的元素值 E val = data.remove(size - 1); size --; return val; } //判断当前栈是否为空 private boolean isEmpty() { return size == 0; } //查看当前栈顶元素值,不弹出该元素 public E peek() { if (isEmpty()) { throw new NoSuchElementException("栈空,无法查看"); } return data.get(size - 1); } //覆写toString方法 public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); for (int i = 0; i < size; i++) { sb.append(data.get(i)); if (i != size-1) { sb.append(","); } } sb.append("] top"); return sb.toString(); } }
创建一个测试类 代码如下:
public class MyStackTest {
public static void main(String[] args) {
MyStack stack = new MyStack<>();
stack.push(1);
stack.push(3);
stack.push(5);
System.out.println(stack);
System.out.println(stack.pop());
System.out.println(stack);
System.out.println(stack.peek());
}
}
运行结果如下:
有了前面动态数组的基础,其实栈里的操作都是在调用动态数组的方法,因为本来就是基于动态数组实现的栈。



