基本介绍

在这里插入图片描述

双端栈是线性表的一种，也是栈的一个特殊分类
我们可以用动态数组和栈的思想来实现双端栈
因为它有两边的操作，比较特殊，所以不能借助前面两节实现的ArrayList或ArrayStack来实现，这里需要从头实现双端栈。
因为入栈，出栈这些操作都有两个方向的选择，所以我们可以把这个栈分成两个区，左栈和右栈，id=0,表示这是左栈，id=1表示是右栈，通过传入的参数来决定是对左栈进行操作还是对右栈进行操作

代码

 import java.util.Arrays;/*** @author zengyihong* @create 2022--07--13 16:09*/
public class ArrayDoubleEndStack<E> {//存元素private E[] data;//左栈的栈顶 ltop=-1说明是空栈 ltop+1表示左栈元素的个数private int ltop;//右栈的栈顶 rtop=data.length表示右栈是空栈  data.length-rtop表示右栈元素个数private int rtop;private static int DEFAULT_SIZE = 10;public ArrayDoubleEndStack() {data = (E[]) new Object[DEFAULT_SIZE];ltop = -1;rtop = data.length;}/*** 入栈** @param element 元素* @param stackId 表示左栈或右栈*/public void push(E element, int stackId) {//双端栈满了，需要扩容if (ltop + 1 == rtop) {resize(data.length * 2);}switch (stackId) {case 0://往左栈  入栈元素data[++ltop] = element;break;case 1:data[--rtop] = element;break;}}/*** 出栈** @param stackId* @return*/public E pop(int stackId) {if (isEmpty(stackId)) {throw new NullPointerException("stack is null");}E rs = null;switch (stackId) {case 0:rs = data[ltop];data[ltop--] = null;case 1:rs = data[rtop];data[rtop++] = null;}//如果元素个数<=len/4 && len>DEFAULT,进行缩容if (size(0) + size(1) <= data.length / 4 && data.length > DEFAULT_SIZE) {resize(data.length / 2);}return rs;}/*** 获取有效元素个数** @return*/public int size(int stackId) {switch (stackId) {case 0:return ltop + 1;case 1:return data.length - rtop;}return -1;}/*** 判断某一端的栈是否为空** @param stackId* @return*/private boolean isEmpty(int stackId) {switch (stackId) {case 0:return ltop == -1;case 1:return rtop == data.length;}return false;}/*** 扩容* @param newLen*/private void resize(int newLen) {E[]newData=(E[]) new Object[newLen];//先处理左端栈for (int i = 0; i <=ltop; i++) {newData[i]=data[i];}//再处理右端栈int index=rtop;for (int i = newLen-size(1); i < newData.length ; i++) {newData[i]=data[index++];}rtop=newLen-size(1);data=newData;}/*** 查看当前栈顶元素* @param stackId* @return*/public E peek(int stackId){if (isEmpty(stackId)){throw new NullPointerException("stack is null");}switch (stackId){case 0:return data[ltop];case 1:return data[rtop];}return null;}public void clear(int stackId){switch (stackId){case 0:ltop=-1;break;case 1:rtop=data.length;break;}}@Overridepublic String toString() {StringBuilder builder = new StringBuilder(String.format("ArrayDoubleEndStack:%d/%d\n", size(0)+size(1),data.length));if (isEmpty(0)){builder.append("leftStack[]\n");}else{builder.append("leftStack:[");for (int i = 0; i <= ltop; i++) {builder.append(data[i]);if (i==ltop){builder.append("]");builder.append("\n");}else {builder.append(",");}}}if (isEmpty(1)){builder.append("rightStack[]");}else{builder.append("rightStack:[");for (int i = data.length-1; i >=rtop; i--) {builder.append(data[i]);if (i==rtop){builder.append("]");builder.append("\n");}else {builder.append(",");}}}return builder.toString();}
}