数据结构与算法5 – 队列

导读:本篇文章讲解 数据结构与算法5 – 队列,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

队列 – 先进先出 – 线性结构

可使用 数组、链表进行实现

1.1 简单数组队列 – 只能存满一次

  • 特点:
    1. 队首出队( front改变 )、队尾入队( rear改变 )
    2. front == rear → 队列为空
    3. rear == 数组最大下标 → 队列为满
    4. rear: 记录上次入队的位置;front: 记录上次出队的位置


  代码实现 – 只能存满一次

class SimpleArrayQueue {
	
	int capacity;   // 队列能存储的最大容量
	int front;     // 存储上一次 从数组中 移出的 元素位置  -- 出队时改变
	int rear;  	   // 存储 上一次  元素被增添在数组内的位置  -- 入队时改变
	int[] array;   // 数组队列的容器
	
	SimpleArrayQueue(int capacity) {
		this.capacity = capacity;
	}
	
	// 如果  上一次出队的位置 跟  上一次入队的位置 相同  -- 说明无元素在队内
	public boolean isEmpty() {
		if(rear == front) {
			return true;
		}
		return false;
	}
	
	// 如果 rear指示上次入队的数组位置,数组最大下标为( 容量-1 ),如果两者相等,说明队已经满,不可在入队
	public boolean isFull() {
		if( rear == capacity - 1) {
			return true;
		}
		return false;
	}
	
	// 入队,先验证上次入队的位置是否等于最大数组小标,在rear进行指针下移动,入队新元素
	public void enQueue(int element) {
		
		if(isFull()) {
			System.out.println("队列已经满");
			return;
		}
		array[++rear] = element;
	}
	
	// 出队,先验证是否上次入队、出队位置重合,不重合,在进行front指针下移,出队指针下移位置的元素
	public int deQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列中没有元素");
		}
		return array[++front];
	}
	
}

1.2 环形数组队列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-udSikSZQ-1587794100258)(en-resource://database/11395:1)]

1.2.1 代码实现

隐喻:好比如front就是你要追的女孩子,rear就是你,front不喜欢你,你在怎么追,永远都会跟她有一步之遥,除非女孩子一步步的靠近你

  代码实现 – rear不能追上front,导致永远会预留一个位置


class CircularQueue {
	int capacity;
	int front = 0;
	int rear = 0;
	int[] array;
	
	CircularQueue(int capacity) {
		this.capacity = capacity;
		array = new int[capacity];
	}
	
	// 查看 如果元素增加,rear指针是否与front重合,如果重合则不能添加
	// 为了保证 isEmpty() 具有空队的 判断
	boolean isFull() {
		return (rear + 1) % capacity == front;
	}
	
	// 一旦front追上rear, 则说明是空队
	boolean isEmpty() {
		return rear == front;
	}

	void add(int a) {
		if (isFull()) {
			System.out.println("已满");
			return;
		}
		array[rear] = a;  // 元素入队成功
		rear = (rear + 1) % capacity;  //计算出下一个元素的入队位置
	}

	int get() {

		if (isEmpty()) {
			System.out.println("无元素可取");
			throw new RuntimeException();
		}
		int result = array[front];  // 元素出队成功
		array[front] = 0;   // 元素值为0,表明那个位置是空的位置;
		front = (front + 1) % capacity; //  计算下一个元素的出队位置
		return result;  
	}

	void show() {

		System.out.println(Arrays.toString(array));
	}

}

1.2.2 测试代码

  

public static void main(String[] args) {


    CircularQueue cq = new CircularQueue(3);
    cq.add(1);
    cq.add(2);     // 队满
    cq.show();     

    cq.add(3);     // 不可添加
    cq.show();    // 数组依然只有 1、2两元素

    System.out.println("--------------------");

    System.out.println(cq.get());	// 出队
    cq.show();		// 只剩元素1
    cq.add(3);     // 添加成功
    cq.show();     // 展示入队后的情况
    cq.add(4);     // 数组满 - 不可入队
}

  运行结果
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FnS6em5U-1587794100268)(en-resource://database/11391:1)]

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/46521.html

(0)
小半的头像小半

相关推荐

极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!