1. 为什么要使用双向栈?
通过上一篇博客 -特殊的线性表(栈),不难知道栈的顺序存储(数组实现)性能相对较好,因为它不存在插入和删除时移动元素的问题,但是它有一点缺陷:要事先确定数组存储容量的大小,万一不够,就需要扩充数组容量。这时双向栈就派上用场了,它可以最大限度的利用事先开辟的存储空间。
2.
双向栈有什么特点?
数组有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为0处,另一个栈为数组的末端,即下标为数组长度M-1处。这样,两个栈如果增加元素,就会从两端点向中间延伸(如下图)。
3. Java实现双向栈
// 双向栈的数组实现
public class ShareStack<T> {
private Object[] arr; // 数组实现栈的操作
private int top1; // 栈1: 栈顶指针
private int top2; // 栈2: 栈顶指针
private static Integer DEFAULT_SIZE = 16; // 数组默认长度
private static final Integer STACK_1 = 1; // 栈1
private static final Integer STACK_2 = 2; // 栈2
public ShareStack() {
init();
}
public ShareStack(int size) {
DEFAULT_SIZE = size;
init();
}
// 初始化栈
public void init() {
arr = new Object[DEFAULT_SIZE];
this.top1 = -1;
this.top2 = DEFAULT_SIZE;
}
// 压栈
public boolean push(int stackNum, T data) {
if (top1 + 1 == top2) { // 栈已满
System.out.println("栈已满,不能再push元素了..");
return false;
}
if (stackNum == STACK_1) { // 操作的是栈1
arr[++top1] = data; // 栈1前进一位
return true;
} else if (stackNum == STACK_2) { // 操作的是栈2
arr[--top2] = data; // 栈2后退一位
return true;
} else {
System.out.println("请输入正确的栈编号: 1 或 2");
return false;
}
}
// 弹栈
@SuppressWarnings("unchecked")
public T pop(int stackNum) {
if (stackNum == STACK_1) { // 操作的是栈1
if (top1 == -1) {
System.out.println("栈1已经是空栈...");
return null;
}
return (T) arr[top1--]; // 栈1后退一位
} else if (stackNum == STACK_2) { // 操作的是栈2
if (top2 == DEFAULT_SIZE) {
System.out.println("栈2已经是空栈...");
return null;
}
return (T) arr[top2++]; // 栈2前进一位
} else {
System.out.println("请输入正确的栈编号: 1 或 2");
return null;
}
}
// 获取栈顶元素
@SuppressWarnings("unchecked")
public T getTop(int stackNum) {
if (stackNum == STACK_1) {
if (this.top1 != -1) {
return (T) arr[top1];
}
} else if (stackNum == STACK_2) {
if (stackNum != DEFAULT_SIZE) {
return (T) arr[top2];
}
} else {
System.out.println("请输入正确的栈编号: 1 或 2");
}
return null;
}
// 获取数组长度
public int size() {
return DEFAULT_SIZE + top1 + 1 - top2;
}
// 判断是否为空栈
public boolean isEmpty() {
return this.top1 == -1 && this.top2 == DEFAULT_SIZE;
}
// 置为空栈
public boolean clear() {
this.top1 = -1;
this.top2 = DEFAULT_SIZE;
return true;
}
// 测试方法
public static void main(String[] args) throws Exception {
ShareStack<Integer> stack = new ShareStack<Integer>();
stack.push(1, 1);
stack.push(2, 2);
stack.pop(1);
stack.pop(2);
}
}
4. 什么时候使用双向栈?
1.)两个栈的空间需求有相反关系时,也就是当一个栈增长时另一个栈在缩短的情况。
2.) 两个栈需要具有相同的数据类型,如果数据类型不同,将会使问题复杂化。
分享到:
相关推荐
大话存储2:存储系统架构与底层原理极限剖析》内容简介:网络存储是一个涉及计算机硬件以及网络协议/技术、操作系统以及专业软件等各方面综合知识的领域。目前国内阐述网络存储的书籍少之又少,大部分是国外作品,对...
特别提醒:本文件为《大话数据分析:Tableau数据可视化实战》的数据集,并不是PDF书籍。
一个无比严谨的技术痴迷者创作的一本饱含诚意与想象力的经典存储著作。
大话数据结构 .pptx
基于《大话数据结构》进行数据结构的学习
大话存储2:存储系统架构与底层原理极限剖析.docx
数据结构与算法问题 讲解生动 数据结构不在
Android之大话设计模式——:抽象工厂模式借鉴.pdf
大话Oracle RAC:集群、高可用性、备份与恢复(带目录清晰中文完整版)
大话存储:存储系统底层架构原理极限剖析(终极版)第3部分 大话存储:存储系统底层架构原理极限剖析(终极版)第3部分大话存储:存储系统底层架构原理极限剖析(终极版)第3部分
大话存储:存储系统底层架构原理极限剖析(终极版)_张冬2015.01_P989
《大话存储:存储系统底层架构原理极限剖析(终极版)》内容涉及:计算机IO基本概念,硬盘物理结构、盘片数据结构和工作原理,七种常见RAID原理详析以及性能细节对比,虚拟磁盘、卷和文件系统原理,磁盘阵列系统,...
大话Oracle RAC:集群、高可用性、备份与恢复。 此书被认为不可多得的好资料之一:大话Oracle RAC(PDF经典),看完之后深有感触,发出来共享一下。
大话存储终极版 第一部分 大话存储
数据结构 线性表 栈和队列 串 数和二叉树 图 查找 内部排序
大话存储:存储系统底层架构原理极限剖析(终极版)第5部分 大话存储:存储系统底层架构原理极限剖析(终极版)第5部分
《大话数据结构》——C语言简单实现单链表结构及相关一些操作
资源名称:大话存储:存储系统底层架构原理极限剖析资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
大话存储:存储系统底层架构原理极限剖析(终极版)第4部分 大话存储:存储系统底层架构原理极限剖析(终极版)第4部分