目录
- 栈
- 栈的模拟实现
-
- 栈的顺序实现
-
- 接口实现
- 成员变量
- 默认构造方法
- 入栈
- 判满
- 获取栈元素个数
- 出栈
- 获取栈顶元素 但是不删除
- 判空
- 栈的链式实现
-
- 接口实现
- 内部类
- 入栈
- 出栈
- 判空
- 获取栈顶元素 但是不删除
- 获取栈元素个数
- Java中的Stack
-
- 实现的接口
- 常用方法
- 栈练习
栈
栈是限定仅在表尾进行插入和删除操作的线性表,一种**先进后出
**的数据结构。
栈顶: 允许插入和删除的一端。
栈底:不允许插入和删除的一端。
压栈:栈的插入操作。
出栈:栈的删除操作。
栈的模拟实现
栈的底层可以是顺序表,可以是链表实现。
栈的顺序实现
栈的顺序实现就是使用顺序表为底层实现。
接口实现
实现的接口(成员方法)如下:
顺序表可以多实现一个判满接口。
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是线程安全的。
- 实现RandomAccess接口,能随机访问。
- 实现了Cloneable接口,可克隆。
- Serializable接口表示支持序列化。
常用方法
提供的常用方法如下:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FhLLHxMB-1720973208640)(https://i-blog.csdnimg.cn/direct/f414e542bd80432095def0a48671fd3f.png)]