队列接口定义,和栈接口一样:
public interface Queue<Item> {
/**
* 添加一个元素
* @param item
*/
public void push(Item item);
/**
* 获取最后一个添加的元素,并将其从队列中删除
* @return
*/
public Item pop();
/**
* 判断队列是否为空
* @return
*/
public boolean isEmpty();
/**
* 获取队列当前的元素个数
* @return
*/
public int size();
}
基于数组的实现,关键是如何resize:
import java.util.Iterator;
import com.mycode.algorithms.stack.Stack;
/**
* 基于数组的队列实现
* @author imhuqiao
*/
public class ArrayQueue<Item> implements Queue<Item>,Iterable<Item> {
private Item[] data = null;
private int tail = -1;
private int head = -1;
private int count = 0;
public ArrayQueue(){
this(10);
}
public ArrayQueue(int initLength){
data = (Item[]) new Object[initLength];
}
@Override
public void push(Item item) {
if(size()==data.length){
resize(data.length*2);
}
data[++tail] = item;
if(head==-1){
head = 0;
}
count++;
print();
}
@Override
public Item pop() {
if(isEmpty()){
return null;
}
Item item = data[head];
data[head] = null;
head++;
if(size() > 0 && size() == data.length/4) resize(data.length/2);
print();
count--;
return item;
}
private void print(){
System.out.print("[");
for(Item d : data){
System.out.print(d+",");
}
System.out.println("],tial="+tail+",head="+head);
}
@Override
public boolean isEmpty() {
return size()==0;
}
@Override
public int size() {
return count;
}
@Override
public Iterator<Item> iterator() {
return new ArrayStackIterator();
}
private void resize(int length){
Item[] newdata = (Item[]) new Object[length];
int x = 0;
//System.out.println("resize from "+ size()+" to "+length);
for(int i = head;i<=tail;i++){
newdata[x++] = data[i];
data[i] = null;
}
data = newdata;
head = 0;
tail = x==0 ? x : x-1;
}
class ArrayStackIterator implements Iterator<Item>{
private int i = tail;
private int j = head;
@Override
public boolean hasNext() {
return i>=j;
}
@Override
public Item next() {
Item result = data[j++];
return result;
}
@Override
public void remove() {
}
}
}
基于链表的实现,原理和栈一致,只是多了一个记录尾部的变量,push的时候不是替换头而是接在尾巴上:
import java.util.Iterator;
import com.mycode.algorithms.stack.Stack;
/**
* 基于数组的队列实现
* @author imhuqiao
*/
public class ArrayQueue<Item> implements Queue<Item>,Iterable<Item> {
private Item[] data = null;
private int tail = -1;
private int head = -1;
private int count = 0;
public ArrayQueue(){
this(10);
}
public ArrayQueue(int initLength){
data = (Item[]) new Object[initLength];
}
@Override
public void push(Item item) {
if(size()==data.length){
resize(data.length*2);
}
data[++tail] = item;
if(head==-1){
head = 0;
}
count++;
print();
}
@Override
public Item pop() {
if(isEmpty()){
return null;
}
Item item = data[head];
data[head] = null;
head++;
if(size() > 0 && size() == data.length/4) resize(data.length/2);
print();
count--;
return item;
}
private void print(){
System.out.print("[");
for(Item d : data){
System.out.print(d+",");
}
System.out.println("],tial="+tail+",head="+head);
}
@Override
public boolean isEmpty() {
return size()==0;
}
@Override
public int size() {
return count;
}
@Override
public Iterator<Item> iterator() {
return new ArrayStackIterator();
}
private void resize(int length){
Item[] newdata = (Item[]) new Object[length];
int x = 0;
//System.out.println("resize from "+ size()+" to "+length);
for(int i = head;i<=tail;i++){
newdata[x++] = data[i];
data[i] = null;
}
data = newdata;
head = 0;
tail = x==0 ? x : x-1;
}
class ArrayStackIterator implements Iterator<Item>{
private int i = tail;
private int j = head;
@Override
public boolean hasNext() {
return i>=j;
}
@Override
public Item next() {
Item result = data[j++];
return result;
}
@Override
public void remove() {
}
}
}
测试代码:
@Test
public void testArrayQueue(){
Queue<String> as = new ArrayQueue<String>(1);
as.push("a");
as.push("b");
as.push("c");
as.push("d");
as.push("e");
Assert.assertEquals("a",as.pop());
Assert.assertEquals("b",as.pop());
String res = "";
for(String str : as){
res += str;
}
Assert.assertEquals("cde",res);
}
@Test
public void testLinkQueue(){
Queue<String> as = new LinkQueue<String>();
as.push("a");
as.push("b");
as.push("c");
as.push("d");
as.push("e");
Assert.assertEquals("a",as.pop());
Assert.assertEquals("b",as.pop());
String res = "";
for(String str : as){
res += str;
}
Assert.assertEquals("cde",res);
}
分享到:
相关推荐
基于JAVA实现的常用数据结构代码,JAVA实现复杂度、动态数组、链表、栈、队列、二叉搜索树等
主要介绍了Python实现队列的方法,结合实例形式分析了Python基于数组和链表实现队列的相关操作技巧与相关注意事项,需要的朋友可以参考下
包括各种不同形式的栈与队列的实现方式,分基于数组和链表实现的栈与队列,队列有一般队列,双端队列,优先队列等
2.使用链表实现的队列。 先看看两种方式的优劣: .Net Farmework中的普通队列Queue的实现使用了第一种方式,缺点是当队列空间不足会进行扩容,扩容的主要实现是开辟一个原始长度2倍的新数组,然后将原始数组里面的...
主要内容包括:算法效率的输入规模、阶和大O,数据结构的无序和有序列表,队列和栈基于数组和链表的设计实例,递归详解,二叉查找树和AVL树,堆、散列表和排序以及图论等。对于每一种数据结构的性质和用途,《计算机...
leetcode 跳跃 数据结构练习 数组练习 MyArray 大小固定的数组实现 MyDynamicArray 自动扩容数组实现 ...基于数组实现队列,空间不足自动搬移数据 MyCircularQueue 基于固定大小的数组实现的环状队列
优先队列 优先队列(Priority Queue)是一种数据结构,它类似于常规的队列或栈,但每个元素都有与其关联的“优先级”。在优先队列中,元素的出队顺序是基于...下面是一个简单的基于数组和插入排序的优先队列实现示例:
## 队列* 用数组实现一个顺序队列* 用链表实现一个链式队列* 实现一个循环队列 ## 递归* 编程实现斐波那契数列求值f(n)=f(n-1)+f(n-2)* 编程实现求阶乘n!* 编程实现一组数据集合的全排列 ## 排序 * 实现归并排序、...
二叉堆二项式堆D堆斐波那契堆索引堆左派堆对堆队列基于数组的队列基于链表的队列阻塞队列循环队列具有最大值的队列具有最小值的队列使用两个堆栈实现的队列队列排序一个阵列中的三个队列堆基于数组的堆栈基于链表的...
QueueBasedOnArray:基于数组的队列。 PriorityQueue:基于链表的优先队列。 BinaryHeap:基于数组的二进制堆。 SymbolTable:基于链表的符号表。 OrderlySymbolTable:基于优先级队列的有序符号表。 ...
队列-基于数组的有界 队列-基于列表 队列-基于2个堆栈 双端队列-基于数组 演算法 二进制搜索-简单+广义 最大子数组-分而治之,Kadene算法 阵列旋转 想法/待办事项: 堆栈-基于数组的无边界 队列-基于数组的无边界 ...
4.5 比较基于数组的实现和基于链表的实现 148 第5章 作为问题求解技术的递归 155 5.1 定义语言 156 5.1.1 语法知识基础 156 5.1.2 两种简单的语言 158 5.2 代数表达式 160 5.2.1 代数表达式的类型 160 5.2.2 ...
队列(基于数组和基于链表) 两个堆栈(使用一个数组实现两个堆栈) 双端队列 二叉搜索树 堆(最大和最小堆) 哈希表 常见问题 细绳 判断一个字符串是否有唯一字符 确定两个字符串是否是字谜 堆栈 波兰符号 问题...
并查集(基于数组索引) 并查集(基于树) 并查集(使用节点size优化) 并查集(使用rank优化) 平衡二叉树 leetcode按题目类型分类 leetcode按难易分类 写在最后 我的数据结构是从的开始学起的,算是我数据结构的...
内含资源如下: 1.基本数据结构 1.1.Array ........... 动态数组 1.2.LinkedList ... 链表 1.3.BST ................. 并查集_基于数组实现 3.18.QuickUnion ......................... 并查集_基于树思想实现
我们可以看到在javascript概念中的队列与栈都是一种特殊的线性表的结构,也是一种比较简单的基于数组的顺序存储结构。由于javascript的解释器针对数组都做了直接的优化,不会存在在很多编程语言中数组固定长度的问题...
基于链表实现队列、基于循环数组实现队列 : 栈 : 堆 : 集合与映射 :Hash 表 树形结构: : 二分查找树 : 平衡树 : 红黑树 : 线段树 : 字典树 其他: : 图 : 跳表 : 并查集 JDK 集合源码 基本 List, Set, ...
一、队列简介 队列是是一种受限的线性表,特点为先进先出(FIFO:first in first out)。...基于数组实现;基于链表实现; 队列的常见操作: enqueue(element):向队列尾部添加一个(或多个)新的项; dequeu
队列(基于数组的实现、基于链表的实现和基于栈的实现)的数据结构及其相关算法:队列结构包含三个要素,即队头指针head、队尾指针rear和队列大小size,具体操作包括: 入队操作put 出队操作pop 查看队头元素p
算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...