左神初级班03
数组结构实现固定的队列和栈
1 栈
新建数组（固定长度）、index指针
index指针指向新加数的位置
基本操作：
1、push压栈：先检查栈是否已满，报异常；否则压栈，index++
2、peek弹出栈顶元素但不删除：检查栈是否已满，弹出的是index - 1（注意index指向的元素含义）
3、 pop弹出栈顶元素并删除：检查栈是否已满，return栈顶元素，–index
代码实现
public class ArrayStack {
public int[] arr;
public int index;
//1 设置一个固定数组大小initSize，初始化数组arr
public ArrayStack(int initSize){
if(initSize < 0){
throw new IllegalArgumentException("The init Size is less than 0");//不合法的参数异常
}
arr = new int[initSize];
index = 0;
}
//2 栈操作：peek\push\pop
public void push(int obj){//压栈
if(index == arr.length){
throw new ArrayIndexOutOfBoundsException("The queue is full");//数组越界
}
obj = arr[index++];
}
public int 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];
}
}
2 队列（难度+）
新建数组（固定长度）；两个指针：start、end；队列中个数size
两指针start和end之间是独立的，无约束关系，end和start一开始均指向0位置。
end变量代表新加一个数应该把它填到什么位置上，start变量代表用户拿一个数时应该拿哪个数。
size与两指针之间分别有约束关系：
1、size < length：将新数放到end位置上，size++，end++
2、size != 0：将start指的数返回给用户，size–，start++
3、end/start只要到底了，就回到开头，start在不断的追end，是一个循环
基本操作： peek、push、poll（同上）
代码实现
public class ArrayQueue {
//1 初始化
public int[] arr;
public int size;
public int start;
public int end;
public ArrayQueue(int initSize){
if(initSize < 0){
throw new IllegalArgumentException("The init size is less than 0");
}
arr = new int[initSize];
size = 0;
start = 0;
end = 0;
}
//2 基本操作
public Integer peek(){
if(size == 0){
return null;
}
return arr[start];
}
public void push(int obj){
if(size == arr.length){
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
size++;
obj = arr[end];
end = end == arr.length - 1 ? 0 : end + 1;//如果end指针到底了就返回头部0位置，否则 + 1
}
public int poll(){
if(size == 0){
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
size--;
int temp = start;
start = start == arr.length - 1 ? 0 : start + 1;
return arr[temp];
}
实现特殊的栈，并返回栈中最小元素（比较著名的题）
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
要求：1、pop、push、getMin操作的时间复杂度O(1)；2、设计的栈类型可以使用现成的栈结构
思路
使用两个栈结构data栈和min栈，两个栈元素一起增长，分别存放数据和当前最小值。设要压入元素num，若num < data栈栈顶，则两个栈同时压入num；若num > data栈栈顶，则data栈压入num，min栈压入min栈的最小值（重复压入），则需要返回时去min栈栈顶即可。
增加空间，维持最小值。
代码实现
public static class MyStack2{
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack2(){
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}
//基本操作
//压栈
public void push(int newNum){
if(this.stackMin.isEmpty()){
this.stackMin.push(newNum);
}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.stackMin.isEmpty()){
throw new RuntimeException("The stack is empty");//该异常在下面详细阐述
}
this.stackMin.pop();
return this.stackData.pop();
}
//获取stackMin栈中栈顶元素
public int getmin(){
if(this.stackMin.isEmpty()){
throw new RuntimeException("The stack is empty");
}
return this.stackMin.peek();
}
}
补充知识点
Exception 和 RuntimeException的区别：
1、其他Exception，受检查异常。
可以理解为错误，必须要开发者解决以后才能编译通过，解决的方法有两种：1.throw到上层 2.try-catch处理。
2、RunTimeException：运行时异常，又称不受检查异常，不受检查！
因为不受检查，所以在代码中可能会有RunTimeException时Java编译检查时不会告诉你有这个异常，但是在实际运行代码时则会暴露出来，比如经典的1/0，空指针等。如果不处理也会被Java自己处理。
如何用队列实现栈，用栈实现队列
适用范围举例：面试官提问使用队列结构来进行图的深度优先遍历？将队列转化为栈进行遍历
1 用队列实现栈
思路
用两个队列实现栈，两个队列data和help，data中装栈读入的数据，help中装不弹出的数据。
举个简单例子，栈中装入数据[1,2,3,4,5]，根据先入后出，应弹出5，则data队列中装入[1,2,3,4,5]，help队列从data队列弹出并装入[1,2,3,4]，留最后一个数返回，data队列弹出数据，并将data和help队列互换。
代码实现
public static class TwoQueuesStack{
private Queue<Integer> data;
private Queue<Integer> help;
public TwoQueuesStack(){
data = new LinkedList<Integer>();//LinkedList双向链表
help = new LinkedList<Integer>();
}
//入栈
public void push(int pushInt){
data.add(pushInt);
}
//读栈顶
public int peek(){
if(data.isEmpty()){
throw new RuntimeException("Stack is empty");
}
while(data.size() > 1){
help.add(data.poll());//pop的安全方法
}
int res = data.poll();
help.add(res);//因为是peek，不改变栈内数据
swap();
return res;
}
//弹栈顶并删除
public int pop(){
if(data.isEmpty()){
throw new RuntimeException("Stack is empty");
}
while(data.size() > 1){
help.add(data.poll());
}
int res = data.poll();
swap();
return 0;
}
public void swap(){
Queue<Integer> tmp = help;
help = data;
data = tmp;
}
}
2 用栈实现队列
思路
用两个栈实现队列，初始化两个栈：push栈和pop栈。push栈压入队列中的数，pop栈用来存放push栈中pop出来的数。弹出pop栈中的元素，即队列顺序。
实现过程中必须要满足的两个原则：
1、push栈只要倒出，必须一次性倒完，否则pop栈从弹出的第一个元素开始顺序错误
2、pop栈中有数据时，push栈中不可以进行倒出操作，否则pop栈顺序错误
代码实现
public static class TwoStacksQueue{
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
public TwoStacksQueue(){
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
//入队列
public void push(int pushInt){
stackPush.push(pushInt);
}
//出队列
public int poll(){
if(stackPush.isEmpty()&&stackPop.isEmpty()){
throw new RuntimeException("Queue is empty");
}else if(stackPop.isEmpty()){
while (!stackPush.isEmpty()){
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
//出队列，不删除
public int peek(){
if(stackPush.isEmpty() && stackPop.isEmpty()){
throw new RuntimeException("Stack is empty");
}else if(stackPop.isEmpty()){
stackPop.push(stackPush.pop());
}
return stackPop.peek();
}
}
上一篇： 1. 了解HTML