7.栈
一.包含min函数的栈
1.题目描述：
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
2.示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
3.解:
（1）我的答案:
import java.util.Stack;
class MinStack {
private Stack<integer> stack;</integer>
public MinStack() {
stack = new Stack<>();
}
public void push(int x) {
stack.push(x);
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
int minValue = stack.firstElement();
for (int i = 0; i < stack.size(); i++) {
if (minValue > stack.get(i)) minValue = stack.get(i);
}
return minValue;
}}
(2)网友答案：
private Node head;
public MinStack() {
}
public void push(int x) {
if (head == null)
head = new Node(x, x, null);
else
head = new Node(x, Math.min(head.min, x), head);
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int min() {
return head.min;
}
private class Node {
int val;
int min;
Node next;
public Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}class MinStack:
def __init__(self):
self.stack = []
self.minstack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.minstack or x <= self.minstack[-1]:
self.minstack.append(x)
def pop(self) -> None:
if self.stack.pop() == self.minstack[-1]:
self.minstack.pop()
def top(self) -> int:
return self.stack[-1]
def min(self) -> int:
return self.minstack[-1]直接一个数组，就可以实现，因为调用的次数有限，所以可以先分配一个二倍调用次数大小的数组，其中偶数下标存储之前进栈的最小值，奇数下标存储进栈值，每次每次进栈最小值和进栈值同时添加。
class MinStack {
/** initialize your data structure here. */
int[] stack=new int[40000];
int topIndex=-1;
public MinStack() {
}
public void push(int x) {
if(topIndex==-1)
{
stack[topIndex+1]=x;
}
else
{
if(x<=stack[topIndex-1])
{
stack[1+topIndex]=x;
}
else{
stack[1+topIndex]=stack[topIndex-1];
}
}
stack[2+topIndex]=x;
topIndex+=2;
}
public void pop() {
topIndex-=2;
}
public int top() {
return stack[topIndex];
}
public int min() {
return stack[topIndex-1];
}}
4.总结：
我的答案其实并不好，是用栈来实现栈，不符合题目要求。
网友的答案都很好，有的用链表，有的用两个数组，有的用一个数组。但是其本质都是一边添加元素，一边和未入栈之前的最小值比较，然后记录下当前的最小值。用链表的话，每添加一个节点，就拿该节点的值和之前节点里记录的上一轮栈的最小值作比较，然后将新的最小值记录到新添加的节点中。用两个数组的话，就是一个数组添加元素，一个数组添加最新的最小值。用一个数组的话就是奇数位记录元素，偶数位记录最新的最小值。
二.用两个栈实现队列
1.题目描述：
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
2.示例：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
这一行表示每一行代码的操作
[[],[3],[],[]]
这个表示每一行代码操作所需要的参数
举例：
CQueue 表示新建一个CQueue对象，对应的所需参数为[]，即此操作不需要参数。
appendTail 表示执行一个appendTail()操作，对应要被操作的元素为3。
deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。
deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。
以上的输入其实是一个代码执行的步骤描述与其对应所需参数。
即两个纬度：
1、操作描述
2、此次操作所需参数
3、操作描述与操作所需参数是通过默认顺序一一对应的。
3.解:
（1）我的答案：
import java.util.Stack;
class CQueue {
Stack<integer> stackIn;
Stack<integer> stackOut;
int popValue;</integer></integer>
public CQueue() {
stackIn = new Stack<>();
stackOut = new Stack<>();
popValue = -1;
}
public void appendTail(int value) {
stackIn.push(value);
}
public int deleteHead() {
if (stackOut.isEmpty()) {
if (stackIn.isEmpty()) popValue = -1;
else {
while (!stackIn.isEmpty()) stackOut.push(stackIn.pop());
popValue = stackOut.pop();
}
}
else {
popValue = stackOut.pop();
}
return popValue;
}}
（2）网友答案：
class CQueue {
LinkedList<integer> stack1;
LinkedList<integer> stack2;</integer></integer>
public CQueue() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
public void appendTail(int value) {
stack1.add(value);
}
public int deleteHead() {
if (stack2.isEmpty()) {
if (stack1.isEmpty()) return -1;
while (!stack1.isEmpty()) {
stack2.add(stack1.pop());
}
return stack2.pop();
} else return stack2.pop();
}}
class CQueue {
LinkedList<integer> stack1;
LinkedList<integer> stack2;</integer></integer>
public CQueue() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
public void appendTail(int value) {
stack1.add(value);
}
public int deleteHead() {
if (stack2.isEmpty()) {
if (stack1.isEmpty()) return -1;
while (!stack1.isEmpty()) {
stack2.add(stack1.pop());
}
return stack2.pop();
} else return stack2.pop();
}}
4.总结
我的答案比网友的第一个答案好，网友的答案并没有真正的把两个栈连接起来，使两个栈的两个顶点分别成为队列的头和尾。我的答案真正的将两个栈连接起来，而且执行删除节点操作时最多只需要执行一次while。其连接两个栈的原理是：当输入输出栈都有元素得时候，就是正常得队列的出队入队。当输出栈里没有元素，即输出完了以后，就会将输入栈的元素“平移”到输出栈中，这里是实现了两个栈的连接的关键点。
而网友2的答案和我的答案的原理一样，只不过它使用的不是java的栈类，而是LinkedList类，使用这个类的优点如该网友所说：“使用java的同学请注意，如果你使用Stack的方式来做这道题，会造成速度较慢； 原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。 可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。 但是我的意思不是像100%代码那样直接使用一个LinkedList当做队列，那确实是快，但是不符题意。 贴上代码，这样的优化之后，效率提高了40%，超过97%。”