算法入门之基本数据结构：队列和栈

大家都知道，算法和数据结构是息息相关，学习数据结构能帮助我们更好的理解算法，理解编程，这是一种编程思想的培养；今天我们要介绍的数据结构是：队列，可以把队列想象成一个双向管道，一边进另一边出

代码示例

public classQueueDemo{

public static voidmain(String[]args) {

//1.初始化一组数据

int[] start={1,2,3,4,5,6,7,8,9};

//2.初始化一个空队列

QueuelinkedList= newLinkedList();

//3.数据入列

for(inti=;i

linkedList.offer(start[i]);

System.out.println("入列:"+JSON.toJSONString(linkedList));

}

while(linkedList.size()>){

System.out.print("出列:"+linkedList.poll()+"");

}

}

}

结果：入列:[1]

入列:[1,2]

入列:[1,2,3]

...

入列:[1,2,3,4,5,6,7,8,9]

出列:1出列:2出列:3出列:4出列:5出列:6出列:7出列:8出列:9

分析

Java中 Queue是一个接口继承Collection接口，我们可以选择一些实现了queue接口的类来构建一个队列，例如本例中的linkedList，从上面结果我们不难发现队列的一些基本特征：

三大组成元素：数据块data，头节点head，尾节点tail

数据为线性结构

先进先出(FIFO)原则

两大操作：只允许在队列的尾部进行添加(入队)，只允许在队列的头部进行删除(出队)

队列的一些其他方法：

offer：增加一个元素并返回true （当队列满时返回false）

add：增加一个元素 （当队列满时会抛出IIIegaISlabEepeplian异常）

poll：移出一个元素并返回移出的元素 （官方说返回的是队列的头部元素，可能指的是移出操作之前的队列 当队列为空则返回null）

remove：同poll （当队列为空时抛出NoSuchElementException异常）

peek：返回队列的头部元素 （当队列为空时，返回null）

element：返回队列的头部元素（当队列为空时抛出NoSuchElementException异常）

此外还有2个方法是针对阻塞队列的：put（添加元素，队列满时阻塞）和take（移出元素，队列为空时阻塞）

延伸

说完队列,我们再了解下栈的概念，可以把栈想象成一个单向管道，从一头进，又从该头出

代码示例

public classStatckDemo{

public static voidmain(String[]args) {

//1.初始化一组数据

int[] start={1,2,3,4,5,6,7,8,9};

//2.初始化空栈

Stackstack= newStack();

//3.入栈 后入的永远在栈顶

for(inti=;i

stack.push(start[i]);

}

//判断栈是否为空

System.out.println("栈是否为空:"+stack.empty());

//返回栈顶对象 不删除

System.out.println(stack.peek());

System.out.println(JSON.toJSONString(stack));

//出栈 删除栈顶对象,并返回删除的栈顶对象

System.out.println(stack.pop());

System.out.println(JSON.toJSONString(stack));

//返回对象在栈中的位置,相对于栈顶的位置,

// 如果对象不存在则返回-1

System.out.println(stack.search(7));

}

}

结果:栈是否为空:false

9

[1,2,3,4,5,6,7,8,9]

9

[1,2,3,4,5,6,7,8]

2

分析

栈与队列不同，可以直接创建使用，继承自Vector类，通过上述例子，我们能总结出栈的一些基本特征：

两大基本组成元素：一维数组块，指向栈顶的变量top值

数据为线性结构

后进先出原则（LIFO）

两大基本操作：入栈（只允许向栈顶添加元素），出栈（只允许从栈顶移出元素）

栈的一些基本方法：

empty：判断栈是否为空，返回Boolean值

peek：返回栈顶部的元素，不删除该元素

pop：删除栈顶元素，并返回该元素（出栈）

push：将元素压入栈顶部（入栈）

search：返回元素在栈中的位置，以栈顶top为基准，当要返回的值在栈中不存在时，返回-1

至此，我们就将队列和栈做了个简单的介绍，也不深入解析，后期我们再深入探讨这两种数据结构的一些细节和延伸方面的知识。