手写一个Stack（栈）的集合类（链表实现+数组实现）
2022-03-08 本文已影响0人
生不悔改
一、Stack栈集合的原理
栈是程序中一种数据结构，它的出入口是同一个，所以，出栈操作，和入栈操作，都是从同一个口子。看一下示意图。
栈的示意图.png
图中，类似杯子的容器其实就是栈这种容器集合结构。如图所示，将元素A，B，C，D按照顺序加入到栈中，先加入的A元素反而在容器栈的最底端。这时候如果我们需要取元素，那么只能从栈的最上面元素开始取，而D元素，作为栈最上面的元素，却是最后一个加入的。所以栈这种数据结构有一个重要的特性：先进后出（First In Last Out），简称FILO。
二、栈的常见操作：
1.压栈
将元素放进栈中，这个操作叫压栈。
1.弹栈
将元素从栈中取出来，这个操作叫弹栈，也可以叫出栈。
三、实现Stack数据结构的思路
1.链表实现思路
这里的链表我们采用单向链表，双向的链表也可以实现，只是相对来说会比单向链表复杂一点。我们要理解栈的特性：先进后出。所以我们可以让每次新加入的元素，放在后加入元素的前面，例如：0，加入一个元素1，变成0->1；如果再加入一个元素2，此时变成了0->2->1；再加入3，变成0->3->2->1。由于我们的链表只能从头节点开始遍历，这样我们在遍历链表的时候，就可以完成栈这个先进后出的特性了。
a.链表实现代码
/**
* @author:
* @date: 2022/3/8 09:45
* @description: 实现栈的思路：链表实现
*/
public class MeOneTypeStack<T> implements Iterable<T> {
/**
* 首先需要一个头节点
*/
private Node<T> head;
/**
* 记录栈中元素的个数
*/
private int size;
/**
* 无参构造函数
*/
public MeOneTypeStack() {
// 初始化头节点
this.head = new Node<>(null, null);
// 初始化元素个数
this.size = 0;
}
/**
* 栈的元素个数获取
*
* @return
*/
public int size() {
return size;
}
/**
* 栈是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 压栈操作
* 例子：0->1
* 0->2->1
* 0->3->2->1
*
* @param t
*/
public void push(T t) {
// 如果头节点下一个为空，那么直接加入头节点后面
if (head.next == null) {
head.next = new Node<>(t, null);
// 元素个数自增一
size = size + 1;
return;
}
// 如果头节下一个节点有值了，那么这时候再加入，需要插入在头节点和下一个节点之间：0->1 再插入一个变成 0->2->1
Node<T> oldNode;
Node<T> newNode = new Node<>(t, null);
// 将头节点后面所有的节点剥离出来
oldNode = head.next;
// 将新节点接入到头结点后面
head.next = newNode;
// 将老的节点再接到新的节点后面
newNode.next = oldNode;
// 元素个数自增一
size = size + 1;
}
/**
* 弹栈操作
*/
public T pop() {
// 检查头节点后面有没有数据
if (head.next == null) {
return null;
}
Node<T> currentNode = head.next;
// 头节点后面有节点，0->2->1 变成 0->1
Node<T> oldNode = head.next.next;
// 将头节点接回到去掉第一个元素后的链表上
head.next = oldNode;
// 元素个数减一
size = size - 1;
return currentNode.item;
}
private class Node<T> {
/**
* 当前节点里面的对象
*/
private T item;
/**
* 下一个元素
*/
private Node<T> next;
public Node(T item, Node<T> next) {
this.item = item;
this.next = next;
}
}
@Override
public Iterator<T> iterator() {
return new SIterator();
}
/**
* 实现Iterator接口，从而实现栈的增强for循环
*/
class SIterator implements Iterator {
// 指针节点
private Node cursor;
// 初始化指针节点为头节点
public SIterator() {
cursor = head;
}
@Override
public boolean hasNext() {
// 只要指针节点的next不等于null就说明还有元素
return cursor.next != null;
}
@Override
public T next() {
// 从当前指针拿到下一个节点
Node<T> currNode = cursor.next;
// 将指针变为下一节点
cursor = cursor.next;
// 从当前节点中拿到元素
return currNode.item;
}
}
}
以上我们就用链表这种数据结构实现了一个MeOneTypeStack栈集合，接下来我们可以开测试一下。
b.测试代码
/**
* @author:
* @date: 2022/3/8 10:35
* @description:
*/
public class MeOneTypeStackTest {
public static void main(String[] args) {
MeOneTypeStack<String> stack = new MeOneTypeStack<>();
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
// ABCD顺序压栈后，数据在栈中的顺序应该是DCBA
for(String s:stack){
System.out.println(s);
}
System.out.println("=======================");
//弹栈测试
System.out.println("第一次弹出元素："+stack.pop());
for(String s:stack){
System.out.println(s);
}
}
}
c.测试结果
D
C
B
A
=======================
第一次弹出元素：D
C
B
A
2.数组实现思路
其实用数组实现会相对链表实现会复杂一下，因为数组你需要初始化容量，如果容量不够了需要进行扩容操作，如果容器中元素过少了，为了节约内存空间，需要进行缩容操作，有点类似于ArrayList集合里面的动态扩容，缩容。现在有一个数组[1,2]，我们按照栈的要求，放进数组，我们可以直接顺序放入，比如这个数组再放入3，变成[1,2,3]，但是弹栈怎么让3，这个最后进去的先出来呢？这里我们可以利用数组的特性，从后往前遍历，这样我们就能让最后放进数组的元素先拿出来，同时再用一个变量去记录元素的个数即可。
a.数组实现代码
/**
* @author:
* @date: 2022/3/8 10:47
* @description: 数组实现栈
*/
public class MeTwoTypeStack<T> implements Iterable<T> {
/**
* 数组
*/
private T[] elementData;
/**
* 栈中的元素个数
*/
private int elementCount;
/**
* 默认数组长度
*/
private int default_capacity = 10;
/**
* 无参构造函数
*/
public MeTwoTypeStack() {
this.elementData = (T[]) new Object[default_capacity];
this.elementCount = 0;
}
/**
* 获取当前栈的元素个数
*
* @return
*/
public int size() {
return elementCount;
}
/**
* 判断当前栈是否为空
*
* @return
*/
public boolean isEmpty() {
return elementCount == 0;
}
/**
* 压栈 我们就正常往数组中放入元素即可
* 1,2,3,4
* 这样放入数组
*
* @param t
*/
public void push(T t) {
// 如果当前元素个数和数组容器大小一样时，需要对容器进行两倍的扩容
if (elementCount == elementData.length) {
reSize(2 * elementData.length);
}
elementData[elementCount++] = t;
}
/**
* 弹栈，由于弹栈需要先进后出，所以我们从数组的后面开始遍历弹出
* 这里我们弹栈操作后，数组里面的数据并没有减少，我们仅仅是将最后一个元素的值返回，
* 我们要用数组元素个数这个变量来控制，下次返回的元素的下标应该是elementCount-1
*
* @return
*/
public T pop() {
// 如果当前栈中元素为空，则直接返回null
if (elementCount == 0) {
return null;
}
// 拿到数组最后一位的元素
T current = elementData[elementCount - 1];
// 数组的长度减一
elementCount = elementCount - 1;
// 元素个数小于等于数组容器长度的四分之一时，需要缩容两倍
if (elementCount <= elementData.length / 4) {
reSize(elementData.length / 2);
}
return current;
}
/**
* 数组的扩容缩容
*
* @param capacity
*/
private void reSize(int capacity) {
// 创建一个临时数组
T[] temp = elementData;
// 原来的数组指向新的扩容或者缩容后的数组
elementData = (T[]) new Object[capacity];
// 将原来的数组中的元素赋值到新的数组中
for (int i = 0; i < elementCount; i++) {
elementData[i] = temp[i];
}
}
@Override
public Iterator<T> iterator() {
return new SIterator();
}
class SIterator implements Iterator {
// 设置指针
private int n;
public SIterator() {
// 初始化指针的位置，从数组末尾开始遍历，所以是数组的最后以为开始
this.n = elementCount - 1;
}
@Override
public boolean hasNext() {
return n >= 0;
}
@Override
public T next() {
T current = elementData[n];
n = n - 1;
return current;
}
}
}
以上就是我们数组的实现栈的思路了，可能有人会疑惑，我出栈的操作，并没有让数组中的元素减少，只是让最后一个元素的值返回了，这样不等于没有删除吗，这里我用了元素个数elementCount来标识数组中出栈后应该还剩的元素个数，所以每次出栈操作我都会让元素个数减一，因为元素是按照顺序排列的，下标识固定的。而且在缩容的时候，会重新创建一个新的数组去取代原来的数组，此时就会把里面实际应该清除，但是没有清除的数据让JVM在垃圾回收时将这个没有被引用的对象给清除掉。
b.测试代码
加入十一个元素，目的是检验扩容功能有没有问题，我们初始化数组长度是10，如果有问题，在加入第十一个元素的时候就会出现数组越界。
/**
* @author:
* @date: 2022/3/8 10:35
* @description:
*/
public class MeTwoTypeStackTest {
public static void main(String[] args) {
MeTwoTypeStack<String> stack = new MeTwoTypeStack<>();
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
stack.push("E");
stack.push("F");
stack.push("G");
stack.push("H");
stack.push("I");
stack.push("J");
stack.push("K");
// ABCD顺序压栈后，数据在栈中的顺序应该是DCBA
for(String s:stack){
System.out.println(s);
}
System.out.println("=======================");
//弹栈测试
System.out.println("第一次弹出元素："+stack.pop());
for(String s:stack){
System.out.println(s);
}
}
}
c.测试结果
K
J
I
H
G
F
E
D
C
B
A
=======================
第一次弹出元素：K
J
I
H
G
F
E
D
C
B
A
注意：jdk里面的Stack类其实就是用了数组的这种形式实现了栈，它是通过继承Vector集合类，然后使用Vector类的api组合从而实现的栈的这种先进后出的特性。
总结
或许你会再次疑惑我们为什么要实现已经有了的数据结构，主要是我们通过自己实现更好的理解设计者的思路，并且这种思路往往可以解决现实中的很多业务场景问题。
