设计_面试题.03.01.三合一

题目

三合一。描述如何只用一个数组来实现三个栈。

你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标，value表示压入的值。

构造函数会传入一个stackSize参数，代表每个栈的大小。

示例1:

输入：

["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]
[[1], [0, 1], [0, 2], [0], [0], [0], [0]]

输出：

[null, null, null, 1, -1, -1, true]
说明：当栈为空时`pop, peek`返回-1，当栈满时`push`不压入元素。

示例2:

输入：

["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"]
[[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]
 输出：
[null, null, null, null, 2, 1, -1, -1]

思路

一开始直接懵逼，看了别人的才懂题意

1. 首先开始创建类时构造函数里面创入的大小是栈的大小 ( stackSize )

2. 其次不管是push还是pop还是peek或者isEmpty 的参数 (stackNum)

   • stackNum输入的值,代表的是哪个栈!!!!
   • 这个题叫三合一就是说 三个栈代表全部放在一个数组里面
   • 例如: 参数stackNum 为 0 时就代表第一个栈
   • 参数stackNum 为 1 时就代表第二个栈
   • 参数stackNum 为 2 时就代表第三个栈

3. 由于是一个数组相当于3个栈,所以创建的时候就 乘 3

4. 每次push的时候 需要先判断头指针是否小于数组的长度

   • 如果小于需要添加值,而且需要把top节点加3
   • 例如: 添加栈0 2, 添加栈0 8, 添加栈0 7

   

   

   此时top[0] = 0 减3之后就是 -3 所以它是空的返回-1

5. 每次peek的时候, 先判断是否为空 空直接返回-1, 不为空话就把top – 3 的下标给它就可以了,此时不是抛出所以不需要改变原来的top的值

参考代码：

class TripleInOne {
	//定义数组栈
	private int[] stack;
	//定义一个头指针的数组
	private int[] stackTop;
	//定义栈的长度
	private int stackSize;

    public TripleInOne(int stackSize) {
    	this.stackSize = stackSize;
    	//初始化三合一的栈
    	stack = new int[stackSize * 3];
    	//初始化三个栈的头结点
    	stackTop = new int[] {0, 1, 2};
    }
    
    
    public void push(int stackNum, int value) {
    	//push首先需要判断栈是否满了，
    	int curStackTop = stackTop[stackNum];
    	if(curStackTop < stackSize * 3) {
    		//赋值
    		stack[curStackTop] = value;
    		//头结点 + 3
    		stackTop[stackNum] += 3;
    	}else {//栈满了
    		return;
    	}
    }
    
    public int pop(int stackNum) {
    	//栈顶出栈首先需要判断栈是否为空
    	if(isEmpty(stackNum)) {
    		return -1;
    	}
    	
    	//原本因为每次进栈后栈顶元素的下标的都会加3，出栈需要先减三
    	stackTop[stackNum] -= 3;
    	
    	return stack[stackTop[stackNum]];
    }
    
    public int peek(int stackNum) {
    	//同理，判断是否为空
    	if(isEmpty(stackNum)) {
    		return -1;
    	}
    	
    	//因为是peek，所以不用改变栈顶指针的值
    	
    	return stack[stackTop[stackNum] - 3];
    }
    
    public boolean isEmpty(int stackNum) {
    	//判断这个栈是否为空，因为每次进栈后栈顶元素的下标的都会加3，所以判空时需要先减三判断是否小于90
    	return stackTop[stackNum] - 3 < 0;
    }
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！