数据结构-队列

原创
2016/06/15 21:19
阅读数 411

数据结构-队列


1 队列概念

队列是一个能够实现先进先出的存储结构;只允许在队列一端插入,另一端删除。队列分为链式队列和固定队列;固定队列一般用数组来实现,可分为普通队列、环形队列;链式队列是用链表来实现队列的。

1.1 普通队列

  • 每次出队操作,列头位置发生变化,其他元素位置不受影响,队尾位置到达队列大小时,即时队列不满,新的元素也无法添加进来,列头前位置将会被浪费
  • 每次出队操作,列头位置不会发生变化,即后面元素统一向前移动一位,队尾位置也会受到影响;
  • **比如:***我们生活中排队买票,每完成一次购票,前一个人离开后,后面的人依次向前移动;或者售票员依次把票给每位排队乘客,乘客另外票离开,但是剩余乘客位置不动。
  • 这种方式在程序中资源损耗将很严重,缺点比较明显,通常是不建议使用的。*

1.2 环形队列

大小固定,效率高等优点。数据结构由数组构成,通过算法将数组首尾相连构成环形。每一次出队列操作,列头位置发生变化,其他元素位置不受影响;每一次新元素加入队列,队尾位置发生变化,且不影响队列其他元素。在队列大小固定情况下建议使用环形队列。

1.3 链式队列

容量上线,需要的时候再申请分配内存空间,可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存,在链式结构中访问一个特定元素的效率不如数组。

2 实现原理

2.1 基本数据结构

// 列头位置,队尾位置,队列容量
int head,tail,capacity;
// 队列容器
Object[] items;

2.2 基本操作

// 新增元素入队
boolean add(T item);
// 移出队列
boolean remove();
//队列是否已满
boolean isFull();
//队列是否为空
boolean isEmpty();

3 实现方式

实现方式偏向于实际应用,所以会加一些基础结构之外的内容

3.1 接口定义

  • 队列接口定义
public interface Queue<T>{
 /**
  * 参照 2.2基本操作
  */
//获取队列长度
int getLength();
//获取队列容量
int getCapacity();
//获取头元素,并移出队列
T get();
// 清空队列
void clear();
//遍历队列,通过钩子函数实现对元素的操作
void traverse(Collback<T> collback);
}
  • 钩子函数定义
public interface Collback<T> {
	void doCollBack(T t);
}
  • 抽象类
public abstract class AbstractQueue<T> implements Queue<T> {
    /** 列头元素位置*/
    protected int              head;
    /** 队尾元素位置*/
    protected int              tail;
    /** 队列项*/
    protected Object[]         items;
    /** 队列实际大小*/
    protected int              length;
    /** 队列容量*/
    protected int              capacity;
    /** 默认队列容量*/
    protected final static int DEFAULT_CAPACITY = 10;
    @Override
    public boolean isFull() {
        return length >= capacity;
    }
    @Override
    public boolean isEmpty() {
        return length <= 0;
    }
    @Override
    public int getLength() {
        return length;
    }
    @Override
    public int getCapacity() {
        return capacity;
    }
    public void clear() {
        head = 0;
        length = 0;
        tail = 0;
    }
    protected void init(int capacity) {
        this.capacity = capacity;
        clear();
        items = new Object[capacity];
    }
}

3.2 普通队列实现

这里只针对普通队列第一种情况实现,另一种情况无非每次出队时将所有数组下标减1,改变tail。

public class ArrayQueue<T> extends AbstractQueue<T> {
    public ArrayQueue(){
        init(DEFAULT_CAPACITY);
    }
    public ArrayQueue(int capacity){
        init(capacity);
    }
    @Override
    public boolean add(T item) {
        if (isFull()) 
            return false;
        if (!isEmpty()) {
            tail ++;
        }
        items[tail] = item;
        length ++;
        return true;
    }
    @Override
    public boolean remove() {
        if (isEmpty()) 
            return false;
        head ++;
        length --;
        return true;
    }
    @SuppressWarnings("unchecked")
    @Override
    public T get() {
        if (isEmpty()) 
            return null;
        T item = (T) items[head];
        clear();
        return item;
    }
    @Override
    public boolean isFull() {
        return (tail + 1) >= capacity;
    }
    @SuppressWarnings("unchecked")
    @Override
    public void traverse(Collback<T> collback) {
        for (int i = 0; i < length; i++) {
            collback.doCollBack((T) items[i + head]);
        }
    }

}

3.3 环形队列实现

public class AnnularQueue<T> implements AbstractQueue<T> {
	public AnnularQueue(){
		init(DEFAULT_CAPACITY);
	}
	public AnnularQueue(int capacity){
		init(capacity);
	}
	public boolean add(T item){
		if (isFull()) 
			return false;
		if (!isEmpty()) {
			tail ++;
			if(tail == capacity)
				tail = 0;
		}
		items[tail] = item;
		length ++;
		return true;
	}
	public boolean remove(){
		if (isEmpty()) 
			return false;
		head ++;
		if (head == capacity) 
			head = 0;
		length --;
		return true;
	}
	public T get(){
		if (isEmpty()) 
			return null;
		T item = (T) items[head];
		remove();
		return item;
	}
	public void traverse(Collback<T> collback){
		int i = head;
		for (int j = 0; j < capacity; j++) {
			i = (j + head) % capacity ;
			collback.doCollBack((T) items[i]);
			if (i == tail) 
			    break;
		}
	}
}

3.3 链式队列实现

链式队列可以通过单项链表方式实现,通过下面代码可以很清楚的看到链式队列的优点

public class LinkedQueue<T> extends AbstractQueue<T> {
    private Node root;
	@Override
	public boolean add(T item) {
		if (root == null) {
			root = new Node(item);
		} else {
			root.add(item);
		}
		return true;
	}
	@Override
	public boolean remove() {
                if(root == null){
                    return false;
                }
		root = root.getNext();
		return true;
	}
	@Override
	public T get() {
		if (root == null) {
			return null;
		}
		T t = root.get();
		remove();
		return t;
	}
	@Override
	public void traverse(Collback<T> collback) {
		Node next = root;
		while (next != null) {
			collback.doCollBack(next.get());
			next = next.getNext();
		}
	}
	private class Node {
		private T t;
		private Node next;
		Node(T t) {
			this.t = t;
		}
		private void add(T item) {
			if (next == null) {
				next = new Node(item);
			} else {
				next.add(item);
			}
		}
		public T get() {
			return t;
		}
		public Node getNext() {
			return next;
		}
	}
}

4 测试

public class QueueTest {

	public static void main(String[] args) {

		Queue<Integer> linkedQueue = new LinkedQueue<Integer>();
		for (int i = 0; i < 4; i++) {
			linkedQueue.add(i);
		}
		for (int i = 0; i < 3; i++) {
			linkedQueue.remove();
		}
		linkedQueue.traverse(new Collback<Integer>() {
			@Override
			public void doCollBack(Integer t) {
				System.out.println(t);
			}
		});
		/*Queue<Integer> arrayQueue = new ArrayQueue<Integer>(4);
		for (int i = 0; i < 4; i++) {
			arrayQueue.add(i);
		}
		for (int i = 0; i < 3; i++) {
			arrayQueue.remove();
		}
		arrayQueue.traverse(new Collback<Integer>() {
			@Override
			public void doCollBack(Integer t) {
				System.out.println(t);
			}
		});*/
		/*Queue<Integer> annularQueue = new AnnularQueue<Integer>(4);
		for (int i = 0; i < 4; i++) {
			annularQueue.add(i);
		}
		for (int i = 0; i < 3; i++) {
			annularQueue.remove();
		}
		for (int i = 0; i < 2; i++) {
			annularQueue.add(i + 4);
		}
		annularQueue.traverse(new Collback<Integer>() {
			@Override
			public void doCollBack(Integer t) {
				System.out.println(t);
			}
		});*/
	}

}
展开阅读全文
加载中

作者的其它热门文章

打赏
0
4 收藏
分享
打赏
0 评论
4 收藏
0
分享
返回顶部
顶部