目录
1.什么是栈
2.栈的使用
3.栈的模拟实现
1.什么是栈
栈：是一种特殊的线性表，只允许在其固定的一端进行插入和删除操作。栈中的元素遵循先进后出（后进先出）原则
栈顶：进行插入和删除数据的一端
栈底：始终不进行插入和删除操作的一端
压栈：栈的插入操作，也可叫做进栈、入栈
出栈：栈的删除操作
压栈和出栈都在栈顶
栈类似于弹夹，栈中的元素类似于子弹，最先放入弹夹中的子弹最后打出，最后放入弹夹中的子弹最先打出，同样的，先入栈的元素后出栈，后入栈的元素先出栈
2.栈的使用
栈中存储的是相同类型的数据，因此可以使用链表或是数组来实现栈，而在Java中，提供了Stack类，是用数组实现的栈。
Stack类位于 java.util 包中，使用前需要导包
import java.util.Stack;
Stack的构造方法：
Stack()
无参构造方法，构造一个空的栈
Stack<Integer> stack = new Stack<>();常用的方法：
E push(E e)
作用：将e入栈，并返回e
class Test{public static void main(String[] args) {Stack<Integer> stack = new Stack<>();//创建一个空的栈，栈中存放数据类型为Integerstack.push(3);//将3压入栈中，并返回3stack.push(55);System.out.println(stack.push(44));//输出：33System.out.println(stack);//输出：[3, 55, 44]}
}E pop()
作用：将栈顶元素出栈并返回
class Test{public static void main(String[] args) {Stack<Integer> 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<Integer> stack = new Stack<>();stack.push(22);stack.push(33);stack.push(44);System.out.println(stack.peek());//输出：44System.out.println(stack);//输出：[22, 33, 44]}
}若栈中无元素，调用peek()方法时，也会抛出异常 EmptyStackException
int size()
作用：获取栈中有效元素个数
boolean empty()
作用：判断栈是否为空
class Test{public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(22);stack.push(33);stack.push(44);System.out.println(stack.size());//输出：3System.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+1elem[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+1elem[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();}
}
