1.用静态数组模拟栈
想法就是创建一个index变量,index指向含有值得下一个数组空间(假设数组中有两个值,index指向2)
/**
* 用静态数组模拟栈
* 用一个变量index来辅助
*/
public class Stack1 {
public static void main(String[] args) {
stack s = new stack(10);
s.push(1);
s.push(2);
s.push(3);
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
}
public static class stack{
static int [] arr ;
int index;
public stack(int size) {
if(size<0) {
throw new IllegalArgumentException("the array size is less than 0");
}
arr = new int[size];
}
//压栈
public void push(int i) {
if(index == arr.length) {
throw new ArrayIndexOutOfBoundsException("stack is full");
}
arr[index++] = i;
}
//出栈
public int pop() {
if(index == 0) {
throw new IllegalArgumentException("the stack is null");
}
return arr[--index];
}
//返回栈顶值
public int peek() {
if(index == 0) {
throw new ArrayIndexOutOfBoundsException("the stack is null");
}
return arr[index-1];
}
}
}
2.实现一个特殊的栈,有栈的正常方法,能返回栈里的最小值。要求时间复杂度为O(1)
思路:创建两个栈,一个栈 data 放正常的数据。另一个栈 mins 放当前数据中的最小值。例如:若新添加的数据小于当前的最小值,两个栈都添加新的数据。若新添加的数据大于当前栈中的最小值,mins 仍然添加当前最小值。
而且,data出数据的时候,mins同时出栈。
import java.util.Stack;
/**
* 实现一个特殊的栈,有栈的正常方法,还能返回栈里的最小值
* 时间复杂度O(1)
* @author hasee
*
*/
public class stack2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
StackDemo demo = new StackDemo();
demo.push(1);
demo.push(2);
demo.push(3);
demo.push(4);
System.out.println(demo.getMin());
System.out.println(demo.getMin());
}
static class StackDemo {
private Stack datas = new Stack();
private Stack mins = new Stack();
int min =Integer.MAX_VALUE;
//出栈
public int pop() {
// TODO Auto-generated method stub
mins.pop();
return (int) datas.pop();
}
/**
* 入栈的时候,两个栈同时入,datas正常操作
* mins入当前数据中最小值。
*/
public void push(int i) {
datas.push(i);
min = min<i?min:i;//放入当前所有数据中的最小值
mins.push(min);
}
public int getMin() {
return (int) mins.peek();//返回当前栈顶最小值
}
}
}
3.用队列实现栈的功能
思路:创建两个队列,一个data ,一个help。当输入数据的时候,往data中添加。当要输出的时候,将data中的数据全部输出到help中,然后输出help的栈顶。输出后,再讲help中的所有数据输入到data 中。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* 用队列实现栈的功能
* @author hasee
*
*/
public class stack3 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack3 stack = new Stack3();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack.pop());
}
static class Stack3 {
Queue<Integer> data = new LinkedList<Integer>();
Queue<Integer> help = new LinkedList<Integer>();
//压栈
public void push(int i) {
data.offer(i);
}
//出栈
public int pop() {
if(data.size()==0)
throw new NullPointerException("the stack is null");
int size1 = data.size();
for(int i = 0;i < size1;i++) {
help.add(data.remove());
}
int result = help.poll();
int size2 = help.size();
for(int j = 0;j < size2;j++) {
data.add(help.poll());
}
return result;
}
//返回第一个元素 但不删除
public int peek() {
while(data.size()>0) {
help.add(data.remove());
}
int result = help.peek();
while(help.size()>0){
data.add(help.poll());
}
return result;
}
}
}