数据结构:双端栈

news/2024/12/13 16:39:36/

基本介绍

在这里插入图片描述

  • 双端栈是线性表的一种,也是栈的一个特殊分类
  • 我们可以用动态数组和栈的思想来实现双端栈
  • 因为它有两边的操作,比较特殊,所以不能借助前面两节实现的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();}
}

在这里插入图片描述


http://www.ppmy.cn/news/606265.html

相关文章

LeetCode简单题之错误的集合

题目 集合 s 包含从 1 到 n 的整数。不幸的是&#xff0c;因为数据错误&#xff0c;导致集合里面某一个数字复制了成了集合里面的另外一个数字的值&#xff0c;导致集合 丢失了一个数字 并且 有一个数字重复 。 给定一个数组 nums 代表了集合 S 发生错误后的结果。 请你找出重…

短视频技术与市场动态

短视频技术与市场动态 今日头条是一个通用信息平台&#xff0c;致力于连接人与信息&#xff0c;让优质丰富的信息得到高效精准的分发&#xff0c;帮助用户看见更大的世界。 今日头条目前拥有推荐引擎、搜索引擎、关注订阅和内容运营等多种分发方式&#xff0c;囊括图文、视频、…

并发-操作系统底层工作的整体认识

冯诺依曼计算机模型 五大模块&#xff1a;输入、输出、计算器【cpu】、存储器【内存】、控制器 现在计算机硬件结构设计 CPU&#xff1a;控制、运算、数据

LeetCode简单题之图片平滑器

题目 包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) &#xff0c;平均灰度的计算是周围的8个单元和它本身的值求平均&#xff0c;如果周围的单元格不足八个&#xff0c;则尽可能多的利用它们。 示例 1: 输入: […

EDA技术与动态

EDA技术与动态 电子设计自动化&#xff08;英语&#xff1a;Electronic design automation&#xff0c;缩写&#xff1a;EDA&#xff09;是指利用计算机辅助设计&#xff08;CAD&#xff09;软件&#xff0c;来完成超大规模集成电路&#xff08;VLSI&#xff09;芯片的功能设计…

谷歌BERT预训练源码解析(一):训练数据生成

目录 预训练源码结构简介 输入输出 源码解析 参数 主函数 创建训练实例 下一句预测&实例生成 随机遮蔽 输出 结果一览 预训练源码结构简介 关于BERT&#xff0c;简单来说&#xff0c;它是一个基于Transformer架构&#xff0c;结合遮蔽词预测和上下句识别的预训练NLP模型。至…

LeetCode刷题:栈和队列的相关题目

前言1.用栈来实现队列1.1思路1.2图示1.3代码2.用队列来实现栈2.2思路2.2代码3.最小栈3.1思路3.2图示3.3代码4.删除字符串中所有相邻重复项4.1思路4.2代码前言 大家如果对于队列的性质等不太了解的话&#xff0c;我推荐一篇博客&#xff0c;写得很细节&#xff0c;大家可以去看看…

LeetCode简单题之机器人能否返回原点

题目 在二维平面上&#xff0c;有一个机器人从原点 (0, 0) 开始。给出它的移动顺序&#xff0c;判断这个机器人在完成移动后是否在 (0, 0) 处结束。 移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R&#xff08;右&#xff09;&#xff0c;L&…