`

大话数据结构七:两栈共享存储空间(双向栈)

 
阅读更多

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.) 两个栈需要具有相同的数据类型,如果数据类型不同,将会使问题复杂化。



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics