1. 首页
  2. 文章中心
  3. Deque

数据结构之Deque

42 阅读 0 评论
我是靠谱客的博主 英俊山水，最近开发中收集的这篇文章主要介绍数据结构之Deque，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Deque的ADT定义如下：

package com.dzlijian.utils.comments;

/**
 * 
 * @ClassName:  Deque   
 * @Description:双端队列ADT 
 * @author: 长子科技 
 * @date:   2021年7月7日 下午11:03:32   
 *   
 * @param <E>  
 * @Copyright: 2021 www.tydic.com Inc. All rights reserved. 
 */
public interface Deque<E> {
	public int size();
	public boolean  empty();
	public void  addFirst(E e);
	public void  addLast(E e);
	
	public E  removeFirst();
	public E  removeLast();
	
	public E  peekFirst();
	public E  peekLast();

}

1，数组方式实现：

package com.dzlijian.utils.comments;

import java.util.Arrays;

import org.apache.commons.collections.list.GrowthList;
/**
 * 
 * @ClassName:  Deque   
 * @Description:双端队列数组实现
 * @author: 长子科技 
 * @date:   2021年7月7日 下午11:03:32   
 *   
 * @param <E>  
 * @Copyright: 2021 www.tydic.com Inc. All rights reserved. 
 */
public class ArrayDeque<E> implements Deque<E> {
	private static final int DEFAULT_CAPACITY=10;
	private int size;
	private E[] data;
	private int head=-1;
	private int tail=-1;
	
	public ArrayDeque(int capacity){
		data=(E[])new Object[capacity];
		size=0;
	}
	public ArrayDeque(){
		this(DEFAULT_CAPACITY);
	}

	
	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean empty() {
		return size==0;
	}
	
	private void grow(int capacity){
		if(capacity<=0){
			throw new IllegalArgumentException("新建数组长度非法");
		}
		if(capacity<DEFAULT_CAPACITY){
			return;
		}
		if(capacity>data.length){
			data=Arrays.copyOf(data, capacity);
		}else{
			E[] newdata=(E[])new Object[capacity];
			head=0;
			tail=0;
			for(int i=0;i<data.length;i++){
				if(data[i]!=null){
					newdata[tail++]=data[i];
				}
			}
			tail--;
			data=newdata;
		}
		
		
	}

	@Override
	public void addFirst(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			data[0]=e;
			head=0;
			tail=0;
			size++;
			return;
		}
		if(size==data.length){
			grow(size*2);
		};
		if(head==0){
			E[] newdata=(E[])new Object[data.length];
			newdata[0]=e;
			for(int i=1;i<data.length;i++){
				newdata[i]=data[i-1];
			}
			data=newdata;
			tail++;
		}else{
			data[--head]=e;
		}
		size++;
	}

	@Override
	public void addLast(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			data[0]=e;
			head=0;
			tail=0;
			size++;
			return;
		}
		if(size==data.length){
			grow(size*2);
		};
		if(tail<data.length-1){
			data[++tail]=e;
		}else{
			E[] newdata=(E[])new Object[data.length];
			newdata[tail]=e;
			for(int i=data.length-1;i>0;i--){
				newdata[i-1]=data[i];
			}
			data=newdata;
			head--;
		}
		size++;
	}

	@Override
	public E removeFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		E result=data[head];
		data[head]=null;
		head++;
		size--;
		if(size<data.length/2){
			grow(data.length/2);
		}
		
		return result;
	}

	@Override
	public E removeLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		E result=data[tail];
		data[tail]=null;
		tail--;
		size--;
		if(size<data.length/2){
			grow(data.length/2);
		}
		
		return result;
	}

	@Override
	public E peekFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return data[head];
	}

	@Override
	public E peekLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return data[tail];
	}

	public static void main(String[] args) {
		Deque<Integer> test=new ArrayDeque<Integer>();
		for(int i=1;i<6;i++){
			test.addFirst(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.addLast(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.addFirst(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.addLast(i);
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeFirst();
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeLast();
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeFirst();
		}
		System.out.println(test.size());
		for(int i=1;i<6;i++){
			test.removeLast();
		}
		System.out.println(test.size());
	}
}

2，链表实现方式1：

package com.dzlijian.utils.comments;
/**
 * 
 * @ClassName:  Deque   
 * @Description:双端队列链表实现1
 * @author: 长子科技 
 * @date:   2021年7月7日 下午11:03:32   
 *   
 * @param <E>  
 * @Copyright: 2021 www.tydic.com Inc. All rights reserved. 
 */
public class LinkedDeque<E> implements Deque<E> {
	private int size;
	private Node<E> head;
	private Node<E> tail;
	
	private static class Node<E>{
		private Node<E> front;
		private E data;
		private Node<E> next;
		
		public Node(Node<E> front,E e,Node<E> next){
			this.front=front;
			this.data=e;
			this.next=next;
		}
	}
	
	public LinkedDeque(){
		size=0;
		head=null;
		tail=null;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean empty() {
		return size==0;
	}

	@Override
	public void addFirst(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			head=new Node<E>(null,e,null);
			tail=head;
			size++;
			return;
		}
		Node<E> pre=head;
		head=new Node<E>(null,e,head);
		pre.front=head;
		size++;
	}

	@Override
	public void addLast(E e) {
		if(e==null){
			throw new IllegalArgumentException("插入参数为空！！");
		}
		if(size==0){
			head=new Node<E>(null,e,null);
			tail=head;
			size++;
			return;
		}
		Node<E> pre=tail;
		tail=new Node<E>(tail,e,null);
		pre.next=tail;
		size++;
	}

	@Override
	public E removeFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		Node<E> result=head;
		head=result.next;
		if(head!=null){
			head.front=null;
		}
		
		size--;
		if(size==0){
			head=null;
			tail=null;
		}
		return result.data;
	}

	@Override
	public E removeLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		Node<E> result=tail;
		tail=result.front;
		if(tail!=null){
			tail.next=null;
		}
		size--;
		if(size==0){
			head=null;
			tail=null;
		}
		return result.data;
	}

	@Override
	public E peekFirst() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return head.data;
	}

	@Override
	public E peekLast() {
		if(size==0){
			throw new RuntimeException("空队列！");
		}
		return tail.data;
	}
	
	public static void main(String[] args) {
		Deque<Integer> test=new LinkedDeque<Integer>();
		
		for(int i=1;i<6;i++){
			test.addLast(i);
		}
		
		System.out.println(test.size());
		
		for(int i=1;i<6;i++){
			test.addFirst(i);
		}
		System.out.println(test.size());
		
		for(int i=1;i<6;i++){
			test.removeLast();
		}
		System.out.println(test.size());
		
		for(int i=1;i<6;i++){

			test.removeFirst();
		}
		System.out.println(test.size());
		
		
	}

}

3，链表实现Deque2:
package com.dzlijian.utils.comments;
/**
*

  • @ClassName: Deque

  • @Description:双端队列链表实现2

  • @author: 长子科技

  • @date: 2021年7月7日 下午11:03:32

  • @param

  • @Copyright: 2021 www.tydic.com Inc. All rights reserved.
    */
    public class LinkedDeque2 implements Deque {
    private int size;
    private Node head;
    private Node tail;

    private static class Node{
    private E data;
    private Node next;

     public Node(E e,Node<E> next){
 	this.data=e;
 	this.next=next;
 }

    }

    public LinkedDeque2(){
    size=0;
    head=null;
    tail=null;
    }

    @Override
    public int size() {
    return size;
    }

    @Override
    public boolean empty() {
    return size==0;
    }

    @Override
    public void addFirst(E e) {
    if(enull){
    throw new IllegalArgumentException(“插入参数为空！！”);
    }
    if(size    0){
    head=new Node(e,null);
    tail=head;
    size++;
    return;
    }
    head=new Node(e,head);
    size++;
    }

    @Override
    public void addLast(E e) {
    if(enull){
    throw new IllegalArgumentException(“插入参数为空！！”);
    }
    if(size    0){
    head=new Node(e,null);
    tail=head;
    size++;
    return;
    }

     Node<E> pre=tail;
 tail=new Node<E>(e,null);
 pre.next=tail;
 size++;

    }

    @Override
    public E removeFirst() {
    if(size0){
    throw new RuntimeException(“空队列！”);
    }
    Node result=head;
    head=head.next;
    size–;
    if(size    0){
    head=null;
    tail=null;
    }
    return result.data;
    }

    @Override
    public E removeLast() {
    if(size==0){
    throw new RuntimeException(“空队列！”);
    }
    Node result=tail;
    //使用单向节点，此时需要循环查找，非常耗时。
    Node i=head;
    while(i.next!=tail&&i.next!=null){
    i=i.next;

     }
 tail=i;
 i.next=null;
 size--;
 if(size==0){
 	head=null;
 	tail=null;
 }
 return result.data;

    }

    @Override
    public E peekFirst() {
    if(size==0){
    throw new RuntimeException(“空队列！”);
    }
    return head.data;
    }

    @Override
    public E peekLast() {
    if(size==0){
    throw new RuntimeException(“空队列！”);
    }
    return tail.data;
    }

    public static void main(String[] args) {
    Deque test=new LinkedDeque2();
    for(int i=1;i<6;i++){
    test.addFirst(i);
    }
    System.out.println(test.size());
    for(int i=1;i<6;i++){
    test.addLast(i);
    }

     System.out.println(test.size());
 
 for(int i=1;i<6;i++){
 	test.removeFirst();
 }
 System.out.println(test.size());
 
 for(int i=1;i<6;i++){
 	test.removeLast();
 }
 System.out.println(test.size());

    }

}
,
链表实现的2中方式，区别在于，节点是否有前一个和后一个的节点的地址指针。

最后

以上就是英俊山水为你收集整理的数据结构之Deque的全部内容，希望文章能够帮你解决数据结构之Deque所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(28)

相关文章

Extjs4学习笔记-选择器Ext.DomQuery
Extjs4学习笔记-选择器Ext.DomQuery
ext自学方法(思路)
ext自学方法(思路)
php phpdomquery,phpQuery - PHP 处理 HTML DOM 的好帮手
php phpdomquery,phpQuery - PHP 处理 HTML DOM 的好帮手
Ext学习心得（一）
Ext学习心得（一）
数据结构之Deque
数据结构之Deque
环形链表C/C++数据结构什么是环？例题 141. 环形链表公式推导：环形链表二
环形链表C/C++数据结构什么是环？例题 141. 环形链表公式推导：环形链表二
数组实现环形(循环)队列的关键部分总结 获取队列有效元素数，空满判断数组实现环形(循环)队列的关键部分总结
数组实现环形(循环)队列的关键部分总结 获取队列有效元素数，空满判断数组实现环形(循环)队列的关键部分总结
EXT 学习(一)EXTJS 学习(一) :类和对象的概念
EXT 学习(一)EXTJS 学习(一) :类和对象的概念

评论列表共有 0 条评论

立即
投稿
返回
顶部