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<>();//创建一个空的栈，栈中存放数据类型为Integer stack.push(3);//将3压入栈中，并返回3 stack.push(55); System.out.println(stack.push(44));//输出：33 System.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());//输出：44 System.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());//输出：3 System.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+1 elem[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+1 elem[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(); } }
