实现方式
这里介绍两种实现方式：顺序栈和链栈。
栈的特点
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。
由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。栈也称为后进先出表。
堆栈数据结构使用两种基本操作：压入（push）和弹出（pop）：
压入：将数据放入堆栈的顶端（阵列形式或串行形式），堆栈顶端top指标加一。
弹出：将顶端数据输出（回传），堆栈顶端top指标减一。
顺序栈
顺序栈的存储方式：
image.png
顺序栈的进栈： 对于顺序栈的进栈操作，只要将新的数据元素存入栈内，然后将记录栈内元素个数的size+1即可。同时要保证底层数组的长度可以容纳新的数据元素。
image
顺序栈的出栈：
-
让记录栈内元素个数的size-1
-
释放数组对原栈顶元素的引用
image
顺序栈的Java实现：（api中Stack继承Vector）
package com.liuhao.DataStructures;
import java.util.Arrays;
public class SequenceStack<T> {
private final int DEFAULT_SIZE = 10;
private int capacity;// 保存当前数组长度
private int capacityIncrement = 0;// 数组长度不够时，程序每次增加的数组长度
private Object[] elementData;// 保存顺序栈的数据元素
private int size = 0;// 保存顺序栈中元素的个数
// 以默认长度创建空的顺序栈
public SequenceStack() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
// 以一个初始化元素创建顺序栈
public SequenceStack(T element) {
this();
elementData[0] = element;
size++;
}
/**
* 以指定长度创建顺序栈
*
* @param element
* 指定顺序栈中的第一个元素
* @param initSize
* 指定顺序栈的底层数组的长度
*/
public SequenceStack(T element, int initSize) {
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
size++;
}
/**
* 以指定长度创建顺序栈,同时指定底层数组增量
*
* @param element
* 指定顺序栈中的第一个元素
* @param initSize
* 指定顺序栈的底层数组的长度
* @param capacityIncrement
* 底层数组长度不够时，每次增加的增量
*/
public SequenceStack(T element, int initSize, int capacityIncrement) {
this.capacity = initSize;
this.capacityIncrement = capacityIncrement;
elementData = new Object[capacity];
elementData[0] = element;
size++;
}
// 获取顺序栈的长度
public int length() {
return size;
}
// 入栈
public void push(T element) {
this.ensureCapacity(size + 1);
// 将元素放到数组，同时让长度+1
elementData[size++] = element;
}
// 保证底层数组的长度
private void ensureCapacity(int minCapacity) {
// 如果数组的原有长度小于目前所需的长度
if (minCapacity > capacity) {
// 如果给定了数组长度增量
if (capacityIncrement > 0) {
while (minCapacity > capacity) {
// 不断的将capacity的长度增加，直到大于minCapacity
capacity += capacityIncrement;
}
}
// 若没有给定增量
else {
while (minCapacity > capacity) {
// 不断的将capacity加倍，直到大于minCapacity
capacity <<= 1;
}
}
// 将原来的数组的长度变为新的capacity
elementData = Arrays.copyOf(elementData, capacity);
}
}
// 出栈
public T pop() {
// 若当前为空栈，则弹出null
if (size == 0) {
return null;
}
T oldValue = (T) elementData[size - 1];
// 释放栈顶元素，同时将长度-1
elementData[--size] = null;
return oldValue;
}
// 获取栈顶元素
public T getPeek() {
// 若当前为空栈，则返回null
if (size == 0) {
return null;
}
return (T) elementData[size - 1];
}
// 判断是否为空
public boolean isEmpty() {
return size == 0;
}
// 清除顺序栈
public void clear() {
Arrays.fill(elementData, null);
size = 0;
}
public String toString() {
if (size == 0) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (int i = size - 1; i >= 0; i--) {
sb.append(elementData[i].toString() + ", ");
}
sb.append("]");
int length = sb.length();
// 删除多余的“,”和空格
return sb.delete(length - 3, length - 1).toString();
}
}
}
测试代码：
package com.liuhao.test;
import org.junit.Test;
import com.liuhao.DataStructures.SequenceStack;
public class SequenceStackTest {
@Test
public void test() {
// 以指定第一个元素和底层数组长度的方式构建顺序栈
SequenceStack<String> sStack = new SequenceStack<String>("我", 2);
System.out.println("当前所含内容" + sStack);
// 压入数据元素,元素格式大于了定义栈时底层数组的长度
sStack.push("是");
sStack.push("liuhao");
sStack.push("程序员");
// 发现是先入后出的方式打印的
System.out.println("当前所含内容" + sStack);
// 获取栈中元素个数
System.out.println("当前栈中元素个数是：" + sStack.length());
// 获取栈顶元素
System.out.println("当前栈顶元素是：" + sStack.getPeek());
// 弹出元素
System.out.println("弹出元素：" + sStack.pop());
// 发现是先入后出的方式打印的
System.out.println("当前所含内容" + sStack);
// 获取栈顶元素
System.out.println("当前栈顶元素是：" + sStack.getPeek());
// 获取栈中元素个数
System.out.println("当前栈中元素个数是：" + sStack.length());
// 判断是否为空栈
System.out.println("当前栈是否为空：" + sStack.isEmpty());
// 清空栈
sStack.clear();
// 判断是否为空栈
System.out.println("当前栈是否为空：" + sStack.isEmpty());
// 获取栈顶元素,空栈时返回null
System.out.println("当前栈顶元素是：" + sStack.getPeek());
// 获取栈中元素个数
System.out.println("当前栈中元素个数是：" + sStack.length());
// 空栈时进行弹出元素
System.out.println("弹出元素：" + sStack.pop());
}
}
测试结果：
当前所含内容[我]
当前所含内容[程序员, liu, 是, 我]
当前栈中元素个数是：4
当前栈顶元素是：程序员
弹出元素：程序员
当前所含内容[liu, 是, 我]
当前栈顶元素是：liu
当前栈中元素个数是：3
当前栈是否为空：false
当前栈是否为空：true
当前栈顶元素是：null
当前栈中元素个数是：0
弹出元素：null
顺序栈
链栈的Java实现：
class LinkedStack<E> {
static class StackNode<E> {
E data;
StackNode<E> next = null;
public StackNode(E data) {
this.data = data;
}
}
StackNode<E> top = null; // 栈顶，也是一个node节点
public boolean isEmpty() {
return top == null;
}
/**
* 往栈中push一个数据： 首先将要push的数据的next赋值为栈顶top 然后将栈顶指针指向新push进来的节点
* */
public void push(E data) {
StackNode<E> newNode = new StackNode<E>(data);
newNode.next = top;
top = newNode;
}
/**
* 从栈中弹出一个数据， 将栈顶指针指向弹出节点的下一个
* */
public E pop() {
if (isEmpty()) {
System.out.println("栈已经空啦！不能再出栈啦！！！");
return null;
}
E data = top.data;
top = top.next;
return data;
}
/**
* 返回栈顶数据，但是不出栈。数据任然保存在栈中
* */
public E peek() {
if (isEmpty()) {
return null;
}
return top.data;
}
// 将栈中所有数据出栈
public void printStack() {
System.out.println("开始出栈:");
while (!isEmpty()) {
System.out.println(top.data);
top = top.next;
}
System.out.println("出栈结束！");
}
}
测试代码：
public static void main(String[] args) {
LinkedStack<Integer> myStack2 = new LinkedStack<>(); // 创建一个栈
myStack2.push(1);
myStack2.push(2);
myStack2.push(3);
System.out.println(myStack2.pop());
System.out.println(myStack2.pop());
System.out.println(myStack2.peek()); // 打印出栈顶数据，但是不进行出栈操作，数据任然在栈中
System.out.println(myStack2.pop()); // 继续出栈
// myStack2.printStack();
}
运行结果：
3
2
1
1
顺序栈和链式栈的比较
实现链式栈和顺序栈的操作都是需要常数时间，时间复杂度为O(1)，主要从空间和时间复杂度考虑。
顺序栈初始化的时候必须要给定指定大小，当堆栈不满的时候，会造成一部分的空间浪费，链式栈变长，相对节约空间，但是增加了指针域，额外加大了数据结构的开销。
当需要多个堆栈共享的时候，顺序存储中可以充分的利用顺序栈的单向延伸，将一个数组可以存在两个堆栈里，每个堆栈从各自的栈顶出发延伸，这样减少了空间的浪费。但只有两个为堆栈的空间有相反的需求的时候才能使用。就是最好一个堆栈只能增加，一个只能减少。如果，两个一起增加，可能造成堆栈的溢出。
如果在多个顺序堆栈共享空间，一个堆栈满了，其他可能没满，需要使用堆栈的LIFO 运算法则，将满的堆栈元素向左或者右进行平移操作，这样会造成大量的数据元素移动，使得时间的开销增大。
相对来说，使用两个堆栈共享一个空间是比较适宜的存储方式，但是也增加了堆栈溢出的危险。
由于链式存储结构的不连续性，什么时候需要，就什么时候去存储，不存在溢出的问题，但是增加了结构的开销，总体上来说浪费了空间，但是不需要堆栈共享，
相关博客：
栈的Java实现--顺序栈
java 栈 最大深度
网友评论