面试题目——《CC150》栈与队列

面试题3.1：描述如何只用一个数组来实现三个栈。

方法1：固定分割

方法2：弹性分割（较难）

package cc150;

public class ArrayStack {

	public static void main(String[] args) throws Exception {

		// TODO 自动生成的方法存根

		ArrayStack theStack = new ArrayStack();

		theStack.push(0, 1);

		theStack.push(0, 2);

		theStack.push(1, 10);

		theStack.push(1, 11);

		theStack.push(2, 20);

		theStack.push(2, 21);

		System.out.println(theStack.peek(1));

	}

	int stackSize = 100;

	int[] buffer = new int[stackSize * 3];

	int[] stackPointer = {-1,-1,-1};	//用于记录每个栈的栈顶在数组的位置，开始是0,100,200

	//返回不是的栈的栈顶在数组中的当前位置

	int absTopOfStack(int stackNum){

		return stackNum * stackSize + stackPointer[stackNum];

	}

	//入栈

	void push(int stackNum,int value) throws Exception{

		if(stackPointer[stackNum] + 1 >= stackSize){

			throw new Exception("超出范围");

		}

		//栈顶指针自增，并把值放进对应的栈

		stackPointer[stackNum]++;

		buffer[absTopOfStack(stackNum)] = value;

	}

	//出栈

	int pop(int stackNum)throws Exception{

		if(stackPointer[stackNum] == -1){

			throw new Exception("当前栈为空");

		}

		int value = buffer[absTopOfStack(stackNum)];

		buffer[absTopOfStack(stackNum)] = 0;	//清零指定的数组

		stackPointer[stackNum]--;	//指针自减

		return value;

	}

	//返回栈顶元素

	int peek(int stackNum){

		int index = absTopOfStack(stackNum);

		return buffer[index];

	}

	//判断栈是否为空

	boolean isEmpty(int staqckNum){

		return (stackPointer[staqckNum] == -1);

	}

}

面试题3.2：请设计一个栈，除pop与push方法，还支持min方法，可返回栈元素中的最小值。push、pop和min三个方法的时间复杂度必须为O（1）。——《Leetcode》155. Min Stack

　　思路：利用额外的栈来记录每一个状态的最小值，注意当所有小于栈底的元素都弹出后，最小的就是栈底元素

public class MinStack {

    Stack<Integer> theStack;

    Stack<Integer> theStack_temp;    //最小的元素

    /** initialize your data structure here. */

    public MinStack() {

        theStack = new Stack<Integer>();

        theStack_temp = new Stack<Integer>();    //最小的元素

    }

    public void push(int x) {

        if(theStack.empty() || x<=theStack_temp.peek())

            theStack_temp.push(x);

        theStack.push(x);//这句放在前会空栈

    }

    public void pop() {

        int temp = theStack.pop();

        if(temp == theStack_temp.peek())

            theStack_temp.pop();

    }

    public int top() {

        return theStack.peek();

    }

    public int getMin() {

        return theStack_temp.peek();

    }

}

/**

 * Your MinStack object will be instantiated and called as such:

 * MinStack obj = new MinStack();

 * obj.push(x);

 * obj.pop();

 * int param_3 = obj.top();

 * int param_4 = obj.getMin();

 */

面试题3.3：设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。

package cc150;

import java.util.ArrayList;

public class SetOfStacks {

	public static void main(String[] args) {

		// TODO 自动生成的方法存根

	}

	ArrayList<ArrayList<Integer>> stacks = null;

	ArrayList<Integer> curStack = null;

	public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {//第一个表示push或者pop，第二个为待处理的元素

        // write code here

		stacks = new ArrayList<ArrayList<Integer>>(size);

		curStack = new ArrayList<Integer>(size);

		stacks.add(curStack);

		for(int i=0;i<ope.length;i++){

			if(ope[i][0] == 1)

				push(ope[i][1],size);

			else if(ope[i][0] == 2)

				pop(size);

		}

		return stacks;

    }

	public void push(int v,int size){

		if(curStack.size() != size){//数组未满

			curStack.add(v);

		}else{

			curStack = new ArrayList<Integer>(size);

			curStack.add(v);

			stacks.add(curStack);

		}

	}

	public void pop(int size){

		int temp=0;

		if(curStack.size() != 0){//数组未满

			temp = curStack.get(curStack.size()-1);

			curStack.remove(curStack.size()-1);

		}else{

			stacks.remove(stacks.size()-1);

			curStack = stacks.get(stacks.size()-1);

			temp = curStack.get(size-1);

			curStack.remove(curStack.size()-1);

		}

		//return temp;

	}

}

面试题3.4：汉诺塔问题——部分参考 Java递归算法——汉诺塔问题

面试题3.5：实现一个MyQueue类，该类用两个栈实现一个队列。——《Leetcode》232 Implement Queue using Stacks

面试题3.6：编写程序，按升序对栈进行排序（即最大元素位于栈顶）。最多只能使用一个额外的栈存放临时数据，但不得讲数据复制到别的数据结构中（如数组）。该栈支持如下操作：push、pop、peek和isEmpty。

面试题3.7：猫狗收容所

巴特西

面试题目——《CC150》栈与队列

最新文章

热门文章