队列和栈的底层实现、环形数组、最小栈、栈相关
2020-11-23 本文已影响0人
简朴_
01实现一个可以在两端进出的栈、队列
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Code04_DoubleEndsQueueToStackAndQueue {
public static class Node<T> {
public T value;
public Node<T> last;
public Node<T> next;
public Node(T data) {
value = data;
}
}
public static class DoubleEndsQueue<T> {
public Node<T> head;
public Node<T> tail;
// 从头部添加节点
public void addFromHead(T value) {
Node<T> cur = new Node<T>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.next = head;
head.last = cur;
head = cur; // head 向前移动
}
}
public void addFromBottom(T value) {
Node<T> cur = new Node<T>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.last = tail;
tail.next = cur;
tail = cur; // tail 向后移动
}
}
public T popFromHead() {
// 一个数也没有
if (head == null) {
return null;
}
Node<T> cur = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
cur.next = null;
head.last = null;
}
return cur.value;
}
public T popFromBottom() {
if (head == null) {
return null;
}
Node<T> cur = tail;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.last;
tail.next = null;
cur.last = null;
}
return cur.value;
}
public boolean isEmpty() {
return head == null;
}
}
public static class MyStack<T> {
private DoubleEndsQueue<T> queue;
public MyStack() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T pop() {
return queue.popFromHead();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
public static class MyQueue<T> {
private DoubleEndsQueue<T> queue;
public MyQueue() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T poll() {
return queue.popFromBottom();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
public static boolean isEqual(Integer o1, Integer o2) {
if (o1 == null && o2 != null) {
return false;
}
if (o1 != null && o2 == null) {
return false;
}
if (o1 == null && o2 == null) {
return true;
}
return o1.equals(o2);
}
public static void main(String[] args) {
int oneTestDataNum = 100;
int value = 10000;
int testTimes = 100000;
for (int i = 0; i < testTimes; i++) {
MyStack<Integer> myStack = new MyStack<>();
MyQueue<Integer> myQueue = new MyQueue<>();
Stack<Integer> stack = new Stack<>();
Queue<Integer> queue = new LinkedList<>();
for (int j = 0; j < oneTestDataNum; j++) {
int nums = (int) (Math.random() * value);
if (stack.isEmpty()) {
myStack.push(nums);
stack.push(nums);
} else {
if (Math.random() < 0.5) {
myStack.push(nums);
stack.push(nums);
} else {
if (!isEqual(myStack.pop(), stack.pop())) {
System.out.println("oops!");
}
}
}
int numq = (int) (Math.random() * value);
if (stack.isEmpty()) {
myQueue.push(numq);
queue.offer(numq);
} else {
if (Math.random() < 0.5) {
myQueue.push(numq);
queue.offer(numq);
} else {
if (!isEqual(myQueue.poll(), queue.poll())) {
System.out.println("oops!");
}
}
}
}
}
System.out.println("finish!");
}
}
环形数组
public class Code05_RingArray {
/**
*
* 设计一个固定大小的 MyQueue
*
*
* */
public static class MyQueue {
private int[] arr;
private int pushi;
private int polli;
private int size;
private final int limit;
//初始化
public MyQueue(int limit) {
arr = new int[limit]; // 设置数组大小limit
pushi = 0;
polli = 0;
size = 0; // 一开始进来0个数字 size等于0
this.limit = limit;
}
/**
*
* 不用关心push 和pop 什么关系
* */
public void push(int value) {
if (size == limit) {
throw new RuntimeException("栈满了，不能再加了");
}
size++;
arr[pushi] = value;
pushi = nextIndex(pushi);
}
public int pop() {
// size等于0 空
if (size == 0) {
throw new RuntimeException("栈空了，不能再拿了");
}
size--;
int ans = arr[polli];
polli = nextIndex(polli);
return ans;
}
public boolean isEmpty() {
return size == 0;
}
// 如果现在的下标是i，返回下一个位置
private int nextIndex(int i) {
return i < limit - 1 ? i + 1 : 0;
}
}
public static void main(String[] args) {
MyQueue myQueue = new MyQueue(5);
myQueue.push(9);
myQueue.push(3);
myQueue.push(2);
myQueue.push(1);
myQueue.push(8);
System.out.println(myQueue.pop());
System.out.println(myQueue.pop());
System.out.println(myQueue.pop());
System.out.println(myQueue.pop());
System.out.println(myQueue.pop());
}
}
最小栈GetMinStack
import java.util.Stack;
public class Code06_GetMinStack {
/**
*
* 当前栈和最小栈同步上升
*
* 实现一个特殊栈、在基本功能上，在实现返回栈中最小元素的功能
* 1）pop 、 push 、getMin() 操作时间复杂度是O(1)
*
*
* */
// M1
public static class MyStack1 {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack1() {
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);
}
this.stackData.push(newNum);
}
public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
int value = this.stackData.pop();
if (value == this.getmin()) {
this.stackMin.pop();
}
return value;
}
public int getmin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}
// M2
/*
* 设计两个栈 Data 栈 表现为 所有数据的栈
* Data 3 4
* min 3 ？
* min 3 3
*
* Data 3 4 2
* min 3 3 2
*
* 当前的数 和 最小栈的栈顶 做比较 谁小压栈谁 3
*
*
* 弹出时候 就是一起弹出
* */
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);
}
// stackData 就一直压数
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();
}
}
public static void main(String[] args) {
MyStack1 stack1 = new MyStack1();
stack1.push(3);
System.out.println(stack1.getmin());
stack1.push(4);
System.out.println(stack1.getmin());
stack1.push(1);
System.out.println(stack1.getmin());
System.out.println(stack1.pop());
System.out.println(stack1.getmin());
System.out.println("=============");
MyStack1 stack2 = new MyStack1();
stack2.push(3);
System.out.println(stack2.getmin());
stack2.push(4);
System.out.println(stack2.getmin());
stack2.push(1);
System.out.println(stack2.getmin());
System.out.println(stack2.pop());
System.out.println(stack2.getmin());
}
}
两个栈实现一个队列 TwoStacksQueue
import java.util.Stack;
public class Code07_TwoStacksImplementQueue {
/**
*
* 两个栈 实现一个 队列
*
*
*
* */
public static class TwoStacksQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;
// 初始化
public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
// push栈向pop栈倒入数据
private void pushToPop() {
if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
}
public void add(int pushInt) {
stackPush.push(pushInt);
pushToPop();
}
public int poll() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.pop();
}
public int peek() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.peek();
}
}
public static void main(String[] args) {
TwoStacksQueue test = new TwoStacksQueue();
test.add(1);
test.add(2);
test.add(3);
System.out.println(test.peek());
System.out.println(test.poll());
System.out.println(test.peek());
System.out.println(test.poll());
System.out.println(test.peek());
System.out.println(test.poll());
}
}
两个队列实现一个栈 TwoQueueImplementStack
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Code08_TwoQueueImplementStack {
public static class TwoQueueStack<T> {
public Queue<T> queue;
public Queue<T> help;
public TwoQueueStack() {
queue = new LinkedList<>();
help = new LinkedList<>();
}
public void push(T value) {
queue.offer(value);
}
public T poll() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public T peek() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
help.offer(ans);
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
public static void main(String[] args) {
System.out.println("test begin");
TwoQueueStack<Integer> myStack = new TwoQueueStack<>();
Stack<Integer> test = new Stack<>();
int testTime = 1000000;
int max = 1000000;
for (int i = 0; i < testTime; i++) {
if (myStack.isEmpty()) {
if (!test.isEmpty()) {
System.out.println("Oops");
}
int num = (int) (Math.random() * max);
myStack.push(num);
test.push(num);
} else {
if (Math.random() < 0.25) {
int num = (int) (Math.random() * max);
myStack.push(num);
test.push(num);
} else if (Math.random() < 0.5) {
if (!myStack.peek().equals(test.peek())) {
System.out.println("Oops");
}
} else if (Math.random() < 0.75) {
if (!myStack.poll().equals(test.pop())) {
System.out.println("Oops");
}
} else {
if (myStack.isEmpty() != test.isEmpty()) {
System.out.println("Oops");
}
}
}
}
System.out.println("test finish!");
}
}
