基礎：
1棋返、用數(shù)組結(jié)構(gòu)實現(xiàn)大小固定的隊列和棧
數(shù)組實現(xiàn)棧思路：用一個指針來確定位置,當大于數(shù)組長度或者為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];
}
}
數(shù)組實現(xiàn)隊列思路：先定義一個size為隊列大小，初始size為0雷猪，當push添加數(shù)時睛竣，end+1，直到size滿了求摇，再從0開始循環(huán)射沟；當poll取數(shù)時，size先-1与境，然后start+1验夯，當start滿了，再從0開始循環(huán)摔刁。
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挥转、實現(xiàn)一個特殊的棧，在棧的基本功能基礎上共屈，再實現(xiàn)返回棧中最小元素的操作
【要求】
1．pop绑谣、push、getMin操作的時間復雜度都是O(1)
2．設計的棧類型可以使用現(xiàn)成的棧結(jié)構(gòu)
思路：準備兩個棧拗引，一個data棧域仇，一個min棧，data棧存數(shù)取數(shù)寺擂，min棧只存最小值，當新來一個數(shù)時泼掠，與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);
}
// 壓棧時若新數(shù)據(jù)小于等于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、用隊列實現(xiàn)棧腻豌，用棧實現(xiàn)隊列
4家坎、轉(zhuǎn)圈打印矩陣
【題目】 給定一個整型矩陣matrix嘱能，請按照轉(zhuǎn)圈的方式打印它。 例如： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 打印結(jié)果為：1虱疏，2惹骂，3，4做瞪，8对粪，12，16装蓬，15著拭，14，13牍帚，9儡遮， 5，6暗赶，7鄙币，11， 10
【要求】 額外空間復雜度為O(1)
5忆首、旋轉(zhuǎn)正方形矩陣
【題目】 給定一個整型正方形矩陣matrix爱榔，請把該矩陣調(diào)整成 順時針旋轉(zhuǎn)90度的樣子。
【要求】 額外空間復雜度為O(1)糙及。
7详幽、“之”字形打印矩陣
【題目】 給定一個矩陣matrix，按照“之”字形的方式打印這 個矩陣浸锨，例如： 1 2 3 4 5 6 7 8 9 10 11 12 “之”字形打印的結(jié)果為：1唇聘，2，5柱搜，9迟郎，6，3聪蘸，4宪肖，7，10健爬，11控乾， 8，12 【要求】 額外空間復雜度為O(1)娜遵。
8蜕衡、在行列都排好序的矩陣中找數(shù)
【題目】 給定一個有N*M的整型矩陣matrix和一個整數(shù)K， matrix的每一行和每一 列都是排好序的设拟。實現(xiàn)一個函數(shù)慨仿，判斷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、入棧出棧問題
