队列的数据结构知识点一般有5个：
FIFO队列
循环队列（模板）
单调队列（模板）
堆（模板）
优先级队列
循环队列
classMyCircularQueue{
//已经使用的元素个数
privateintused=0;
//第一个元素所在位置
privateintfront=0;
//rear是enQueue可在存放的位置
//注意开闭原则
//[front,rear)
privateintrear=0;
//循环队列最多可以存放的元素个数
privateintcapacity=0;
//循环队列的存储空间
privateint[]a=null;
publicMyCircularQueue(intk){
//初始化循环队列
capacity=k;
a=newint[capacity];
}
publicbooleanenQueue(intvalue){
//如果已经放满了
if(isFull()){
returnfalse;
}
//如果没有放满，那么a[rear]用来存放新进来的元素
a[rear]=value;
//rear注意取模
rear=(rear+1)%capacity;
//已经使用的空间
used++;
//存放成功!
returntrue;
}
publicbooleandeQueue(){
//如果是一个空队列，当然不能出队
if(isEmpty()){
returnfalse;
}
//第一个元素取出
intret=a[front];
//注意取模
front=(front+1)%capacity;
//已经存放的元素减减
used--;
//取出元素成功
returntrue;
}
publicintFront(){
//如果为空，不能取出队首元素
if(isEmpty()){
return-1;
}
//取出队首元素
returna[front];
}
publicintRear(){
//如果为空，不能取出队尾元素
if(isEmpty()){
return-1;
}
//注意：这里不能使用rear-1
//需要取模
inttail=(rear-1+capacity)%capacity;
returna[tail];
}
//队列是否为空
publicbooleanisEmpty(){
returnused==0;
}
//队列是否满了
publicbooleanisFull(){
returnused==capacity;
}
}
单调队列
classSolution{
//单调队列使用双端队列来实现
privateArrayDequeIntegerQ=newArrayDequeInteger();
//入队的时候，last方向入队，但是入队的时候
//需要保证整个队列的数值是单调的
//(在这个题里面我们需要是递减的)
//并且需要注意，这里是Q.getLast()val
//如果写成Q.getLast()=val就变成了严格单调递增
privatevoidpush(intval){
while(!Q.isEmpty()Q.getLast()val){
Q.removeLast();
}
//将元素入队
Q.addLast(val);
}
//出队的时候，要相等的时候才会出队
privatevoidpop(intval){
if(!Q.isEmpty()Q.getFirst()==val){
Q.removeFirst();
}
}
堆
classHeap{
privateint[]a=null;
privateintn=0;
//下沉
publicvoidsink(inti){
intj=0;
intt=a[i];
//找到i结点的左子结点
while((j=(i1)+1)n){
//jn-1判断是否有右子结点
//如果有，并且右子结点更大，那么
//j指向右子结点
if(jn-1a[j]a[j+1]){
j++;
}
//如果子结点比t大
//那么t的位置还需要往后排
if(a[j]t){
a[i]=a[j];
i=j;
}else{
//找到了t的位置
//此时t是大于所有的子结点的
break;
}
}
//将t放在找到的位置那里
a[i]=t;
}
//上浮
publicvoidswim(inti){
intt=a[i];
intpar=0;
//如果还存在父结点
while(i0(par=(i-1)1)!=i){
//如果父结点比t值小
if(a[par]t){
a[i]=a[par];
i=par;
}else{
break;
}
}
a[i]=t;
}
publicvoidpush(intv){
//push是先把元素追加到数组尾巴上，然后再执行上浮操作
a[n++]=v;
swim(n-1);
}
publicintpop(){
intret=a[0];
a[0]=a[--n];
sink(0);
returnret;
}
publicintsize(){
returnn;
}
}
链表
classMyLinkedList{
//实现单链表
//1.假设链表中的所有节点都是0-index的。
classListNode{
publicintval=0;
publicListNodenext=null;
publicListNode(){}
publicListNode(intx){
val=x;
}
}
privateListNodedummy=newListNode();
privateListNodetail=dummy;
privateintlength=0;
/**Initializeyourdatastructurehere.*/
publicMyLinkedList(){
}
privateListNodegetPreNode(intindex){
ListNodefront=dummy.next;
ListNodeback=dummy;
for(inti=0;iindex;i++){
back=front;
front=front.next;
}
returnback;
}
//获取链表中第index个节点的值。如果索引无效，则返回-1。
publicintget(intindex){
if(index0
index=length){
return-1;
}
returngetPreNode(index).next.val;
}
//在链表的第一个元素之前添加一个值为val的节点。
//插入后，新节点将成为链表的第一个节点。
publicvoidaddAtHead(intval){
ListNodep=newListNode(val);
p.next=dummy.next;
dummy.next=p;
//NOTEchangetail
if(tail==dummy){
tail=p;
}
length++;
}
//将值为val的节点追加到链表的最后一个元素。
publicvoidaddAtTail(intval){
tail.next=newListNode(val);
tail=tail.next;
length++;
}
//在链表中的第index个节点之前添加值为val的节点。
//1.如果index等于链表的长度，则该节点将附加到链表的末尾。
//2.如果index大于链表长度，则不会插入节点。
//3.如果index小于0，则在头部插入节点。
publicvoidaddAtIndex(intindex,intval){
if(indexlength){
return;
}elseif(index==length){
addAtTail(val);
return;
}elseif(index=0){
addAtHead(val);
return;
}
ListNodepre=getPreNode(index);
ListNodep=newListNode(val);
p.next=pre.next;
pre.next=p;
//NOTE:heretailhasbeenchanged
length++;
}
//如果索引index有效，则删除链表中的第index个节点。
publicvoiddeleteAtIndex(intindex){
if(index0
index=length){
return;
}
ListNodepre=getPreNode(index);
//NOTE:delete-changetail
if(tail==pre.next){
tail=pre;
}
length--;
pre.next=pre.next.next;
}
}
树
前序遍历
voidpreOrder(TreeNoderoot,ListIntegerans){
//边界处理：如果树为空，那么不需要处理
if(root!=null){
//先访问根结点
ans.add(root.val);
//再分别访问左子树
preOrder(root.left,ans);
//再访问右子树
preOrder(root.right,ans);
}
}
使用栈来实现的前序遍历的代码如下
classSolution{
publicListIntegerpreorderTraversal(TreeNoderoot){
//用来进行递归的栈
StackTreeNodes=newStack();
//用来存放遍历的结果，不算在空间复杂度里面
ListIntegerans=newArrayList();
//开始利用栈来进行遍历
while(root!=null
!s.empty()){
//模拟递归的压栈过程
while(root!=null){
s.push(root);
ans.add(root.val);
root=root.left;
}
//当无法压栈的时候，将root.right进行压栈
root=s.peek();
s.pop();
root=root.right;
}
returnans;
}
}
中序遍历
voidpreOrder(TreeNoderoot,ListIntegerans){
if(root!=null){
//先遍历左子树
preOrder(root.left,ans);
//然后遍历中间的根结点
ans.add(root.val);
//最后遍历右子树
preOrder(root.right,ans);
}
}
采用非递归的中序代码
classSolution{
publicListIntegerinorderTraversal(TreeNoderoot){
StackTreeNodes=newStack();
ListIntegerans=newArrayList();
//注意这里的判断条件，需要root或stack非空
while(root!=null
!s.empty()){
//往左边走，连续入栈，直到不能再走为止
while(root!=null){
s.push(root);
root=root.left;
}
//到达了最左边，把结点弹出来，进行遍历
root=s.peek();
s.pop();
ans.add(root.val);
//转向右子树
root=root.right;
}
//返回遍历的结果
returnans;
}
}
后序遍历
采用递归实现的后序遍历代码模板如下
voidpostOrder(TreeNoderoot,ListIntegerans){
if(root!=null){
//先遍历左子树
postOrder(root.left,ans);
//最后遍历右子树
postOrder(root.right,ans);
//然后遍历中间的根结点
ans.add(root.val);
}
}
采用非递归的后序遍历代码如下
classSolution{
publicListIntegerpostorderTraversal(TreeNodet){
//存放遍历的结果
ListIntegerans=newArrayList();
//pre表示遍历时前面一个已经遍历过的结点
TreeNodepre=null;
StackTreeNodes=newStack();
//如果栈中还有元素，或者当前结点t非空
while(!s.isEmpty()
t!=null){
//顺着左子树走，并且将所有的元素压入栈中
while(t!=null){
s.push(t);
t=t.left;
}
//当没有任何元素可以压栈的时候
//拿栈顶元素，注意这里并不将栈顶元素弹出
//因为在迭代时，根结点需要遍历两次，这里需要判断一下
//右子树是否遍历完毕
t=s.peek();
//如果要遍历当前结点，需要确保右子树已经遍历完毕
//1.如果当前结点右子树为空，那么右子树没有遍历的必要
//需要将当前结点放到ans中
//2.当t.right==pre时，说明右子树已经被打印过了
//那么此时需要将当前结点放到ans中
if(t.right==null
t.right==pre){
//右子树已经遍历完毕，放到ans中。
ans.add(t.val);
//弹栈
s.pop();
//因为已经遍历了当前结点，所以需要更新pre结点
pre=t;
//已经打印完毕。需要设置为空，否则下一轮循环
//还会遍历t的左子树。
t=null;
}else{
//第一次走到t结点，不能放到ans中，因为t的右子树还没有遍历。
//需要将t结点的右子树遍历
t=t.right;
}
}
returnans;
}
}
并查集
classUF{
//并查集数组
int[]F=null;
//记录并查集中集合的个数
intcount=0;
//记录集合中点的个数，比如要知道i所在集合的点有多少个:C[Find(i)]
//注意：这里不能直接使用C[i]
//因为只有根结点的统计才是正确的
int[]Cnt=null;
//并查集的初始化
voidInit(intn)
{
F=newint[n];
Cnt=newint[n];
for(inti=0;in;i++){
F[i]=i;
Cnt[i]=1;
}
count=n;
}
intFind(intx)
{
if(x==F[x]){
returnx;
}
F[x]=Find(F[x]);
returnF[x];
}
voidUnion(intx,inty)
{
intxpar=Find(x);
intypar=Find(y);
//将x所在集合，合并到y所在集合
if(xpar!=ypar){
F[xpar]=ypar;
//y集合里面的个数要增加
Cnt[ypar]+=Cnt[xpar];
count--;
}
}
intSize(inti){returnCnt[Find(i);}
}
预览时标签不可点收录于话题#个上一篇下一篇