微信官方版官方网站wordpress 中文附件

---

栈（Stack）

---

一、 栈的概念

• 栈：先进后出，后进先出
• 

1.栈的方法

• push 压栈，栈的插入操作，插入栈顶
• pop 出栈，栈的删除操作，从栈顶删除
• peek 查看栈顶的元素，不进行改变
• size 查看栈的大小
• isEmpty 判断栈是否为空

 public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);//压栈，存进数据stack.push(2);stack.push(3);Integer pop = stack.pop();//出站System.out.println(pop);//取出3Integer peek = stack.peek();//查看栈顶的元素System.out.println(peek);//2Integer peek1 = stack.peek();System.out.println(peek);System.out.println(stack.size());//2boolean empty = stack.isEmpty();System.out.println(empty);//false}

2.源码分析

虽然栈自身的方法少，但是继承了Vector,可以调用Vector里面的方法
Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的

栈的底层由数组组成，因为栈继承自Vector,Vector的底层是一个数组
所以也叫顺序栈

二、MyStack的实现

1.MyStack的成员变量

public class MyStack {public int[] elem;public int userSize;public MyStack() {this.elem = new int[10];}

定义存储数据的elem数组
定义数组的使用大小
通过构造器，创建数组的大小

2.push方法

    public void push(int val) {//压栈if (isFull()) {//判断是否满了elem = Arrays.copyOf(elem, elem.length * 2);//扩容}elem[userSize++] = val;//后置++,}public boolean isFull() {return userSize == elem.length;}

1.要插入元素，先通过isFull方法判断数组是否满了
2.如果满了进行2倍的扩容
3.val值存进userSize索引的数组内
4.userSize++是后置的++,在存入到elem[userSize]位置后，userSize加一

3.isEmpty方法和pop方法

 public int pop() {//出栈if (isEmpty()){throw new EmptyException("栈是空的");}/* int val = elem[userSize-1];userSize--;return val;*//*   userSize--;return elem[userSize];*/return elem[--userSize];//前置-- 先--再返回下标的值}public boolean isEmpty() {return userSize == 0;}

1.先写isEmpty方法，如果userSize等于0，证明栈为空
2.在pop方法，调用isEmpty方法，如果为空，抛出异常
3.返回userSize减1后，数组中下标的值（注意前置–）

4.peek方法

    public int peek(){if (isEmpty()){throw new EmptyException("栈是空的");}return elem[userSize-1];}

先判断是否为空，不为空，返回userSize-1处数组的值

三、栈的应用

1.将递归转化为循环

逆序打印链表

1.调用递归打印

  public void disPlay2(ListNode pHead) {if (pHead == null) {return;}if (pHead.next==null){System.out.print(pHead.val+" ");return;}disPlay2(pHead.next);System.out.println(pHead.val+" ");}

直到头结点的下一个结点为空时，打印头结点的值，否则移动头结点，再次执行
将最后的结点打印完后，返回到上一步打印，依次完成逆序打印

2.通过栈逆序打印链表

 public void disPlay3(){Stack<ListNode> stack = new Stack<>();ListNode cur = head;while (cur!=null){//遍历链表，压栈stack.push(cur);cur = cur.next;}//遍历栈while (!stack.isEmpty()){ListNode pop = stack.pop();System.out.println(pop.val);//依次出栈打印取出的pop的值}System.out.println();}

1.先遍历链表，依次压栈
2.遍历栈，当栈不为空的时候，依次取出栈，打印取出结点的val值
3.完成逆序打印

点击移步博客主页，欢迎光临~