【数据结构与算法】顺序队列与链式队列及其实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【数据结构与算法】顺序队列与链式队列及其实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2202字,纯文字阅读大概需要4分钟。
内容图文
![【数据结构与算法】顺序队列与链式队列及其实现](/upload/InfoBanner/zyjiaocheng/646/3439207d19dc42e1a2181c8bea245918.jpg)
关于队列,我们先想一个生活中的例子,就是排队买票,先来的先买,后来的只能站在队尾,先进者先出,这就是典型的队列结构。
队列是一种限制访问点的线性表。队列的元素只能从表的一端插入,另一端删除。允许删除的一端称为队头,另一端,也就是允许插入的一端称为队尾,先进入队列的元素先离开,队列的操作是按照先进先出的原则进行。
顺序队列
用顺序存储结构来实现队列就形成了顺序队列。
顺序队列需要分配一块连续的区域来存储队列的元素,需要事先知道或估算队列的大小。
基于数组实现顺序队列
public class ArrayQueue {
/**
* 数组items
*/
private String[] items;
/**
* 数组大小n
*/
private int n=0;
/**
* head表示队头下标 tail表示队尾下标
*/
private int head=0;
private int tail=0;
/**
* 申请一个大小为capacity的数组
* @param capacity
*/
public ArrayQueue(int capacity){
items=new String[capacity];
n=capacity;
}
/**
* 入队
* @param item
* @return
*/
public boolean enqueue(String item){
if(tail==n){
return false;
}
items[tail]=item;
++tail;
return true;
}
/**
* 出队
* @return
*/
public String dequeue(){
if(head==tail){
return null;
}
String ret=items[head];
++head;
return ret;
}
}
测试顺序队列
public class Test {
public static void main(String[] args) {
ArrayQueue arrayQueue=new ArrayQueue(5);
arrayQueue.enqueue("a");
arrayQueue.enqueue("b");
arrayQueue.enqueue("c");
arrayQueue.dequeue();
arrayQueue.dequeue();
}
}
队列变化
链式队列
链式队列是队列的链式实现,是对链表的简化。
基于链表实现链式栈
public class LinkedQueue {
public class Node{
private String value;
private Node next;
public Node(String value,Node node){
this.value=value;
this.next=node;
}
}
/**
* 队列的队首和队尾
*/
private Node head=null;
private Node tail=null;
/**
* 入队
* @param value
*/
public void enqueue(String value){
Node newNode=new Node(value,null);
if(tail==null){
head=newNode;
tail=newNode;
}else{
tail.next=newNode;
tail=tail.next;
}
}
/**
* 出队
* @return
*/
public String dequeue(){
if(head==null){
return null;
}
String value = head.value;
head=head.next;
if(head==null){
tail=null;
}
return value;
}
}
测试链式栈
public class Test {
public static void main(String[] args) {
LinkedQueue linkedQueue=new LinkedQueue();
linkedQueue.enqueue("a");
linkedQueue.enqueue("b");
linkedQueue.enqueue("c");
linkedQueue.dequeue();
linkedQueue.dequeue();
}
}
队列变换
内容总结
以上是互联网集市为您收集整理的【数据结构与算法】顺序队列与链式队列及其实现全部内容,希望文章能够帮你解决【数据结构与算法】顺序队列与链式队列及其实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。