1. 什么是栈(Stack
)
栈是一种数据结构。要阐明栈的定义,咱们须要从栈的个性说起,只有合乎这种个性的数据结构就能够叫做栈。
上面咱们来看看栈的个性是什么。
栈的个性是存入栈中的元素先进后出。先进后出是什么意思呢?
咱们思考有一个桶,桶有 5
层,每层只能放一个球,并且只有桶的最下面有个闭口用来放球和拿球。
当初假如咱们有三个球叫A
,B
,C
,桶也是空的。
咱们依照 A,B,C 的先后顺序把球放进桶里,那么此时的桶外面的球的排布如下:
第五层 | |
第四层 | |
第三层 | C |
第二层 | B |
第一层 | A |
此时咱们再从桶里逐个把球拿进去。首先只能拿 C
球,把 C
球拿掉后能力拿 B
球,而后才是 A
球。
依据以上场景,咱们能够晓得放球程序是A
,B
,C
;拿球程序是C
,B
,A
。
即后面所说的栈的个性:先进后出,并且栈只提供栈顶供咱们放元素和取元素。
2. java 实现
栈能够通过链表实现,也能够通过数组实现。
背刺抉择双链表作为实现栈的载体。
对于链表以及双链表的实现,能够参考以前的文章:
Segment Fault
Bugkit
package org.bugkit.structure;
/**
* @author bugkit
* @since 2021.10.27
*/
public class LinkedList<E> extends AbstractList<E> implements List<E>, Queue<E>, Stack<E> {
private Node<E> head;
private Node<E> tail;
// 创立一个空栈
public LinkedList() {tail = head = null;}
// 放入元素到栈中
@Override
public boolean push(E e) {Node<E> node = new Node<>(e);
if (isEmpty()) {tail = head = node;}else{
node.prev = tail;
tail.next = node;
tail = node;
}
size++;
return true;
}
// 取出栈中的一个元素
@Override
public E pop() {if (isEmpty()) {throw new RuntimeException("Stack is empty");
}
E e = tail.e;
if (size() == 1) {tail = head = null;}else{
tail = tail.prev;
tail.next = null;
}
size--;
return e;
}
@Override
public String toString() {StringBuilder sb = new StringBuilder();
sb.append("LinkedList: {");
Node<E> node = head;
while (node != null) {sb.append(node.e).append("<->");
node = node.next;
}
sb.append("null}");
return sb.toString();}
private static class Node<E> {
E e;
Node<E> next;
Node<E> prev;
public Node(E e) {this.e = e;}
}
}