一、栈和队列
（1）优先级队列：根据元素优先级决定弹出顺序，它的数据结构为堆结构（按照优先级，形成最大堆或者最小堆），并不是线性表结构。
（2）深度优先遍历DFS---栈实现，广度优先队列BFS--队列实现
二、题目
（1）定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
public class Solution { Stack<Integer> dataStack=new Stack(); Stack<Integer> minStack=new Stack(); public void push(int node) {//push时判断是否要向minStack中压入数据 dataStack.push(node); if(minStack.isEmpty()){ minStack.push(node); }else{ if(node<=minStack.peek()){ minStack.push(node); } } } public void pop() {//pop时判断minStack是否也要弹出元素 int dataTop=dataStack.pop(); if(dataTop==minStack.peek()){ minStack.pop(); } } public int top() { return dataStack.peek(); } public int min() { return minStack.peek(); } }
--------------------------------------------------------------------------------------------------------------------
编写一个类,只能用两个栈结构实现队列,支持队列的基本操作(push，pop)。
给定一个操作序列ope及它的长度n，其中元素为正数代表push操作，为0代表pop操作，保证操作序列合法且一定含pop操作，请返回pop的结果序列。
测试样例： [1,2,3,0,4,0],6 返回：[3,4] class MyQueue{ Stack<Integer> pushStack=new Stack(); Stack<Integer> popStack=new Stack(); public void push(int a){ pushStack.push(a); } public int pop(){ if(!popStack.isEmpty()){ return popStack.pop(); }else{ while(!pushStack.isEmpty()){ popStack.push(pushStack.pop()); } return popStack.pop(); } } } public class TwoStack { public int[] twoStack(int[] ope, int n) { // write code here MyQueue queue=new MyQueue(); List<Integer> list=new ArrayList(); for(int i=0;i<n;i++){ if(ope[i]>0) queue.push(ope[i]); if(ope[i]==0) { list.add(queue.pop()); } } int[] res=new int[list.size()]; for(int i=0;i<list.size();i++){ res[i]=list.get(i); } /* int[]out=new int[len]; while(!popStack.isEmpty()){ out[--len]=popStack.pop(); } while(!pushStack.isEmpty()){ out[k++]=pushStack.pop(); } return out; */ return res; } }
--------------------------------------------------------------------------------------------------------------------
(3)递归原地实现栈逆序
get 方法：移除栈底元素并返回。
比如栈中压入 3 2 1，三层pop递归：
第一层pop 1，栈不为空，进入第二层，
第二层pop 2，栈不为空，进入第三层
第三层pop 3，栈为空返回result=3，回到递归的第二层
第二层 接收到last=3，执行push（2），并向第一层return last=3
第一层接收到3，执行push（1），并返回最终结果return 3
Reverse:整个栈逆序
还是压入栈3 2 1，三层get递归
第一层 get得到并删除3，栈不为空进入第二层
第二层get 得到并删除2，栈不为空进入第三层
第三层get得到并删除1，站为空，将1push到栈中，返回第二层
第二层栈此时为空，将2push到栈中，返回第一层
第一层此时栈空，将1push
最终逆序
public int get(Stack<Integer> stack){//移除并返回栈底元素 int result=stack.pop(); if(stack.isEmpty()) { return result; } else{//否则进入递归 int last=get(stack); stack.push(result); return last; } } public void reverse(Stack<Integer> stack){ if(stack.isEmpty()) return; else{//进入递归 int i=get(stack); reverse(stack); stack.push(i); } }
实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。
给定一个整数数组A即为给定的栈，同时给定它的大小n，请返回逆序后的栈。
测试样例： [4,3,2,1],4 返回：[1,2,3,4] public class StackReverse { public int[] reverseStack(int[] A, int n) { int index = 0; //表示初始栈顶标记 reverse(A, index, n); return A; } public int getLast(int[] a,int index,int n){//获得并删除栈底元素 if(index==n-1){//栈为空 return a[index]; } int push=a[index]; index++; int last=getLast(a,index,n); a[index]=push; return last; } public void reverse(int[] a,int index,int n){ if(index==n-1) return; int temp=getLast(a,index,n); index++; reverse(a,index,n); index--; a[index]=temp; } }
--------------------------------------------------------------------------------------------------------------------
（4）升序栈
栈的排序：按升序对栈进行排序（即最大元素位于栈顶），要求只能使用一个额外的栈。
给定一个int[] numbers，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。
这个题目有点像河内塔问题，ABC三个柱子分别放圆环，大环在下小环在上。
原输入栈data和辅助栈help：当前元素cur=pop （date）和help的栈顶top比较，如果<top则压入help中，否则弹出top压入date中，重复，直到cur被push到help中。
重复以上步骤直到data为空。将help中元素倒入data中。
NiuKe上输入的是数组，感觉应该是为了后台测验方便吧
public class TwoStacks { public ArrayList<Integer> twoStacksSort(int[] numbers) { int []help=new int[numbers.length]; int n=numbers.length; int i=0,j=n;//++pop,--push while(i<n){ int cur=numbers[i++]; while(j<n&&help[j]<cur){ numbers[--i]=help[j++]; } help[--j]=cur; } while(j<n){ numbers[--i]=help[j++]; } ArrayList<Integer> sort=new ArrayList<Integer>(); while(i<n){ sort.add(numbers[i++]); } return sort; } }
--------------------------------------------------------------------------------------------------------------------
