阅读量:3
目录
栈
栈是限定仅在表尾进行插入和删除操作的线性表，一种**先进后出**的数据结构。
栈顶： 允许插入和删除的一端。
栈底：不允许插入和删除的一端。
压栈：栈的插入操作。
出栈：栈的删除操作。
栈的模拟实现
栈的底层可以是顺序表，可以是链表实现。
栈的顺序实现
栈的顺序实现就是使用顺序表为底层实现。
接口实现
实现的接口（成员方法）如下：
顺序表可以多实现一个判满接口。
public class MyStack { //默认构造方法 public MyStack() {} //入栈 public void push(int val) {} //判满 public boolean isFull() { } //出栈 public int pop() {} //获取栈顶元素 但是不删除 public int peek() { } //获取栈元素个数 public int size(){} //判空 public boolean isEmpty() { } } 成员变量
我们使用一个数组，和一个int类型usedSize来表示栈中元素个数。
public int[] elem; public int usedSize; 默认构造方法
在构造方法中我们将数组申请10个int空间。
public MyStack() { this.elem = new int[10]; } 入栈
注意事项：
- 先判断栈是否是满的，满的就要先扩容。
- 入栈时usedSize也要跟着加1。
public void push(int val) { if (isFull()) { this.elem = Arrays.copyOf(elem, 2 * elem.length); } elem[usedSize++] = val; } 判满
直接判断usedSize是否等于数组长度。
public boolean isFull() { return usedSize == elem.length; } 获取栈元素个数
直接返回usedSize即可。
public int size(){ return usedSize； } 出栈
注意事项：
- 要先判断栈是不是空，是空抛一个异常。
- 栈不为空，返回数组最后一个元素，同时usedSize要减1。
public int pop() throws IndexIllegalException{ try { if (isEmpty()) { throw new IndexIllegalException("栈为空"); } }catch (IndexIllegalException e){ e.printStackTrace(); } return elem[--usedSize]; } 获取栈顶元素 但是不删除
注意事项：
- 要先判断栈是不是空，是空抛一个异常。
- 栈不为空，返回数组最后一个元素，同时usedSize不动。
public int peek() throws IndexIllegalException{ try { if (isEmpty()) { throw new IndexIllegalException("栈为空"); } }catch (IndexIllegalException e){ e.printStackTrace(); } return elem[usedSize - 1]; } 判空
直接返回usedSize等不等于0。
public boolean isEmpty() { return usedSize == 0; } 栈的链式实现
在实现栈前我们先思考使用什么样的链表来实现？
由于栈的特性是先入后出，如果使用单链表我们出栈时要拿到最后一个节点前一个节点，使复杂度为O(N)，所以我们使用双向链表。
接口实现
实现的接口如下：
public class MyStack { //入栈 public void push(int val) {} //出栈 public int pop() {} //获取栈顶元素 但是不删除 public int peek() { } //判空 public boolean isEmpty() { } //获取栈元素个数 public int size(){} } 内部类
跟双向链表的内部类实现差不多。
static class ListNode{ public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last; 入栈
实现思路：
- 先判断栈是否为空，空就头尾直接指向入栈节点。
- 不为空就将尾节点的next指向入栈节点，入栈节点的prev指向尾节点，尾节点修改为入栈节点。
public void push(int val){ ListNode cur = new ListNode(val); if(isEmpty()){ head = last = cur; return; } last.next = cur; cur.prev = last; last = cur; } 出栈
实现思路：
- 先判断栈是否为空，栈为空抛异常。
- 栈不为空，将尾节点记录下来，尾节点变为前一个节点，并将next置空。
public int pop() throws NullPointerException{ try{ if(isEmpty()){ throw new NullPointerException; } }catch(NullPointerException e){ e.printStackTrace(); } ListNode cur = last; last = last.prev; last.next = null; return cur.val; } 判空
直接返回头是否为空就行。
public boolean isEmpty(){ return head == null; } 获取栈顶元素 但是不删除
实现思路：
- 先判断栈是否为空，栈为空抛异常。
- 栈不为空，返回尾节点。
public int peek(){ try{ if(isEmpty()){ throw new NullPointerException; } }catch(NullPointerException e){ e.printStackTrace(); } return last.val; } 获取栈元素个数
直接循环遍历即可。
public int size(){ ListNode cur = head; int size = 0; while(cur != null){ cur = cur.next; size++; } return size; } Java中的Stack
实现的接口
接口说明：
- 继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。
- 实现了Cloneable接口，可克隆。
- 实现了RandomAccess接口，支持随机访问。
- Serializable接口表示支持序列化。
常用方法
提供的常用方法如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FhLLHxMB-1720973208640)(https://i-blog.csdnimg.cn/direct/f414e542bd80432095def0a48671fd3f.png)]
