用数组实现栈
实现栈太简单了，直接上代码
代码
public class Stack {
private Integer[] arr;
private Integer idx;
public Stack(int size) {
if(size < 0)
throw new StackOverflowError("please input again and input numer must more than 0");
arr = new Integer[size];
idx = 0;
}
public Integer peek() {
if(idx == 0)
return null;
return arr[idx - 1];
}
public void push(int obj) {
if(idx == arr.length)
throw new StackOverflowError("The Stack is full");
arr[idx++] = obj;
}
public Integer pop() {
if(idx == 0)
throw new StackOverflowError("The Stack is null");
return arr[--idx];
}
public static void main(String[] args) {
Stack stack = new Stack(5);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}用数组实现队列
题解
队列可能稍微有点复杂，定义队列的时候需要定义三个变量，分别是end,start,size，先说说他们分别的作用，每次用户拿队中的元素，都从start下标位置取，每次进队都从s=end位置进，每次出队或者进队size都要++或--
假设数组长度是3，如果size没有到3，进队时就把元素放到end的位置上，这是end和size之间的约束关系；如果size不等于0，出队时就总出start位置，这是start和size之间的约束关系。end本身还有一个约束，end是控制进队的，所以每次进一个元素end就++，但在++前，如果end==数组长度，那么end就回到开头也就是0位置；同样的，start也有这个约束
代码
public class Queue {
private int start = 0,end = 0,size = 0;
private int[] arr;
Queue(int size) {
arr = new int[size];
}
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 int pop(){
if(size == 0)
throw new ArrayIndexOutOfBoundsException("The Queue is full");
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];
}
public static void main(String[] args) {
Queue queue = new Queue(3);
queue.push(3);
queue.push(2);
queue.push(1);
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
}
}题目链接：LeetCode155
题解
如何在常数时间内检索到最小元素这是关键，可以开辟一个新的min栈，当min为空或者push的值比min的栈顶元素小时，就将该值push到min中去，否则就再次压入min栈的栈顶元素
同时如果用户调用了一次pop()函数，那么min栈也要跟着pop
代码
class MinStack {
int[] data = new int[10000];
int[] min = new int[10000];
int idx_data,idx_min;
public MinStack() {
idx_data = 0;
idx_min = 0;
}
public void push(int x) {
data[idx_data++] = x;
if(idx_min == 0 || x < min[idx_min - 1])
min[idx_min++] = x;
else
min[idx_min++] = min[idx_min - 2];
}
public void pop() {
idx_min--;
idx_data--;
}
public int top() {
return data[idx_data - 1];
}
public int getMin() {
return min[idx_min - 1];
}
}题目链接：LeeCode225
题解
这个题不要觉得很简单就不想写，很多地方有可能会用到，比方说图的深度优先遍历，别人不让你用栈去实现深度优先遍历，怎么办，其实就和这个道题的思路一样，用两个队列合成一个栈，然后再去遍历
那么说一下这道题的思路。假设现在有元素12345入队，要按照栈的方式弹出，应该怎么做，很简单，再设一个辅助队列help，将1234全部弹出到help中，然后弹出5返回给用户即可
代码
class MyStack {
Queue<Integer> myQueue;
public MyStack() {
myQueue = new LinkedList();
}
/** Push element x onto stack. */
public void push(int x) {
int n= myQueue.size();
Queue<Integer> tempQueue= new LinkedList();
for(int i= 0; i<n; i++){
tempQueue.add(myQueue.poll());
}
myQueue.add(x);
for(int i= 0; i<n; i++){
myQueue.add(tempQueue.poll());
}
}
/** Removes and returns the element on top of the stack. */
public int pop() {
return (int)myQueue.poll();
}
/** Get the top element. */
public int top() {
return (int)myQueue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return myQueue.isEmpty();
}
}题目链接：LeetCode232
题解
用两个栈实现一个队列更简单，假设先在有两个栈data和help，12345首先进data栈，然后将data栈中的元素全部倒到help栈里，然后依次从help栈弹出即可，所以进元素全从data栈进，出元素全从help栈出，但是这两个栈交互的时候有两个条件：
- data栈每次倒元素必须倒完
- 如果help栈里有东西，绝对不能将data栈的元素倒入help栈
代码
class MyQueue {
private Stack<Integer> data = new Stack<Integer>();
private Stack<Integer> help = new Stack<Integer>();
public MyQueue() {
}
/** Push element x to the back of queue. */
public void push(int x) {
data.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if(help.isEmpty())
data_to_help();
return help.pop();
}
/** Get the front element. */
public int peek() {
if(help.isEmpty())
data_to_help();
return help.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return data.isEmpty() && help.isEmpty();
}
public void data_to_help() {
while(!data.isEmpty()) {
help.push(data.pop());
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/