基础：
1、用数组结构实现大小固定的队列和栈
数组实现栈思路：用一个指针来确定位置,当大于数组长度或者为0时抛出异常
public static class ArrayToStack{
private Integer[] arr;
private Integer index;
public ArrayToStack(int initSize){
if(initSize < 0){
throw new IllegalArgumentException("The init size is less than 0");
}
arr = new Integer[initSize];
index = 0;
}
public void push(int obj){
if(index == arr.length){
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
arr[index++] = obj;
}
public Integer pop(){
if(index == 0){
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
return arr[index--];
}
public Integer peek(){
if(index == 0){
return null;
}
return arr[index - 1];
}
}
数组实现队列思路：先定义一个size为队列大小，初始size为0，当push添加数时，end+1，直到size满了，再从0开始循环；当poll取数时，size先-1，然后start+1，当start满了，再从0开始循环。
public static class ArrayToQueue{
private Integer[] arr;
private Integer size;
private Integer start;
private Integer end;
public ArrayToQueue(int initSize){
if(initSize < 0){
throw new IllegalArgumentException("The init size is less than 0");
}
arr = new Integer[initSize];
size = 0;
start = 0;
end = 0;
}
public void push(int obj){
if(size == arr.length){
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
size++;
arr[end] = obj;
end = end == arr.length - 1 ? 0 : end + 1;
}
public Integer poll(){
if(size == 0){
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
size--;
int tmp = start;
start = start == arr.length -1 ? 0 : start + 1;
return arr[tmp];
}
public Integer peek(){
if(size == 0){
return null;
}
return arr[start];
}
}
2、实现一个特殊的栈，在栈的基本功能基础上，再实现返回栈中最小元素的操作
【要求】
1．pop、push、getMin操作的时间复杂度都是O(1)
2．设计的栈类型可以使用现成的栈结构
思路：准备两个栈，一个data栈，一个min栈，data栈存数取数，min栈只存最小值，当新来一个数时，与min栈的栈顶元素比较，若小则压入，若大于则不操作，弹出时data栈与min栈同步弹出即可。
public class getMinStack{
private Stack<Integer> stackMin;
private Stack<Integer> stackData;
public getMinStack(){
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}
public void push(int newNum){
if(this.stackMin.isEmpty()){
this.stackMin.push(newNum);
}
// 压栈时若新数据小于等于min栈的栈顶元素则压入,否则将min栈栈顶元素重复压入一次
else if(newNum <= this.getMin()){
this.stackMin.push(newNum);
}
else{
int newMin = this.stackMin.peek();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}
public int pop(){
if(this.stackData.isEmpty()){
throw new RuntimeException("Your stack is empty.");
}
// 同步弹出即可
this.stackMin.pop();
return this.stackData.pop();
}
public int getMin(){
if(this.stackMin.isEmpty()){
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}
3、用队列实现栈，用栈实现队列
4、转圈打印矩阵
【题目】 给定一个整型矩阵matrix，请按照转圈的方式打印它。 例如： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 打印结果为：1，2，3，4，8，12，16，15，14，13，9， 5，6，7，11， 10
【要求】 额外空间复杂度为O(1)
5、旋转正方形矩阵
【题目】 给定一个整型正方形矩阵matrix，请把该矩阵调整成 顺时针旋转90度的样子。
【要求】 额外空间复杂度为O(1)。
7、“之”字形打印矩阵
【题目】 给定一个矩阵matrix，按照“之”字形的方式打印这 个矩阵，例如： 1 2 3 4 5 6 7 8 9 10 11 12 “之”字形打印的结果为：1，2，5，9，6，3，4，7，10，11， 8，12 【要求】 额外空间复杂度为O(1)。
8、在行列都排好序的矩阵中找数
【题目】 给定一个有N*M的整型矩阵matrix和一个整数K， matrix的每一行和每一 列都是排好序的。实现一个函数，判断K 是否在matrix中。 例如： 0 1 2 5 2 3 4 7 4 4 4 8 5 7 7 9 如果K为7，返回true；如果K为6，返 回false。 【要求】 时间复杂度为O(N+M)，额外空间复杂度为O(1)
9、
进阶：
1、括号是否匹配
2、最长括号匹配
3、逆波兰表达式
4、入栈出栈问题
