学习资源：慕课网liyubobobo老师的《玩儿转数据结构》
1、简介
- 栈也是一种线性结构
- 栈对应的操作是数组的子集，它只能从一端添加元素，也只能从一端取出元素
- 添加和取出元素的这一端称为栈顶
- 栈是一种后进先出Last In First Out (LIFO)的数据结构
- 对于外界而言，只有栈顶的元素是暴露的
- 在计算机的世界里，栈拥有着不可思议的作用
2、栈的应用
- Undo操作(撤销)，一般的编辑器都有撤销功能
- 程序调用的系统栈
- 括号匹配：编译器在括号匹配不成功时会报错
3、栈的实现
底层有多种实现方式，只要可以满足栈的定义和接口
3.1、栈的接口
public interface Stack<E> {
int getSize();
boolean isEmpty();
void push(E e); //入栈
T pop(); //弹栈
T peek(); //查看栈顶元素
}
3.2、基于动态数组的栈
- 实现简单：只需内部封装一个动态数组，复用动态数组的方法实现栈的接口即可
- 容量动态化
- 支持泛型
package stack;
import array.Array;
//基于动态数组的栈实现
public class ArrayStack<T> implements Stack<T> {
Array<T> array;
public ArrayStack(int capacity) {
array = new Array<>(capacity);
}
public ArrayStack() {
array = new Array<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isFull();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void push(T t) {
array.insertToLast(t);
}
@Override
public T pop() {
return array.removeLast();
}
@Override
public T peek() {
return array.getLast();
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("Stack:[");
for(int i=0; i<array.getSize(); i++){
stringBuilder.append(array.getElement(i));
if(i!=array.getSize()-1){
stringBuilder.append(", ");
}
}
stringBuilder.append("] top");
return stringBuilder.toString();
}
}
3.3、测试
public class Test {
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<>();
System.out.println("栈容量为:"+stack.getCapacity());
System.out.println("当前栈是否为空:"+stack.isEmpty());
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.push(50);
System.out.println(stack);
System.out.println("当前栈是否为空:"+stack.isEmpty());
System.out.println("当前栈的大小为:"+stack.getSize());
System.out.println("栈顶元素为:"+stack.peek());;
stack.pop();
stack.pop();
System.out.println("弹栈后的栈为:"+stack);
}
}
4、Java中的栈
java.util.Stack，继承了Vector（也是一个动态数组，与ArrayList不同）
public
class Stack<E> extends Vector<E> {
}
API接口
