data structure and algorithm
我希望每个人对算法和数据结构是什么有一个深刻的认识，所以我们会在每一篇的文章的开始给你灌输下面的这些知识点：
1、数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构，学好数据结构可以让你写出更漂亮更高效的代码（时间复杂度和空间复杂度）；
2、算法其实就是解决我们生活中遇到的问题的计算方法；
3、程序=数据结构+算法；要学好数据结构和算法就要在日常生活中把遇到的问题尝试用程序去解决
4、数据结构是实现一个算法的基础，所以想要学好算法，需要把数据结构学到位；
5、数据结构分为线性结构和非线性结构；线性结构的特点是数据元素之间存在一对一的线性关系；
6、线性结构又有顺序存储结构和链式存储结构两种的存储结构，顺序存储结构中存储元素是连续的，而链式存储结构中存储元素不一定是连续的；
队列
队列是一个先入先出(FIFO)的有序列表，它是线性结构的，先存入队列的数据，要先取出，后存入的要后取出;
队列的底层存储结构可以是顺序存储结构实现，也可以通过链式存储结构实现，下面我们将进行两种方式的代码实现来让大家更好理解FIFO这种机制的底层实现：
通过数组实现队列：
public class ArrayQueue {
int[] ins;
int front;
int ref;
int max;
public ArrayQueue(int n) {
max=n;
ins=new int[n];
front=-1;
ref=-1;
}
public boolean isFull(){
if(ref==-1 && front==max-1){
return true;
}
return (front+1)%max==ref;
}
public boolean isEnpty(){
if(ref==-1 && front==-1){
return true;
}
return front==ref;
}
public void show(){
if(isEnpty())
throw new RuntimeException("队列为空-----");
for(int i=ref+1;i<ref+1+size();i++){
System.out.println(ins[i%max]);
}
}
public int size(){
return (front+max-(ref+1))%max+1;
}
public void offer(int num){
if (isFull()){
System.out.println("队列已满-------");
return;
}
front=(front+1)%max;
ins[front]=num;
}
public int poll(){
if (isEnpty())
throw new RuntimeException("队列为空-----");
ref=(ref+1)%max;
return ins[ref];
}
public int peek(){
if (isEnpty())
throw new RuntimeException("队列为空-----");
return ins[(ref+1)%max];
}
}
通过链表实现队列：
public class LinkedQueue {
DoubleLinkedList doubleLinkedList;
public LinkedQueue(int count) {
this.doubleLinkedList = new DoubleLinkedList(count);
}
public boolean isEnpty(){
return doubleLinkedList.isEnpty();
}
public boolean isFull(){
return doubleLinkedList.isFull();
}
public void show(){
doubleLinkedList.show();
}
public void push(int val){
doubleLinkedList.push(val);
}
public int pop(){
return doubleLinkedList.pop();
}
public int peek(){
return doubleLinkedList.peek();
}
}
public class DoubleLinkedList {
DoubleNode cur=null;
DoubleNode front=null;
int count;
int num=0;
int val;
public DoubleLinkedList(int count) {
this.count = count;
}
public boolean isEnpty(){
return num==0;
}
public boolean isFull(){
return num ==count;
}
public int peek(){//返回栈顶元素
if(isEnpty()){
throw new RuntimeException("队列为空-----");
}
return cur.val;
}
public int pop(){//出栈
if(isEnpty()){
throw new RuntimeException("队列为空-----");
}
val=cur.val;
cur=cur.getNext();
cur.pre=null;
num--;
return val;
}
public void push(int val){//入栈
if(isFull()){
System.out.println("队列已满-------");
return;
}
DoubleNode node=new DoubleNode(val);
if(cur==null){
cur=node;
front=node;
num++;
}else{
front.next=node;
node.pre=front;
front=node;
num++;
}
}
public void show(){
if(isEnpty()){
throw new RuntimeException("队列为空-----");
}
while(cur!=null){
System.out.println(cur.val);
cur=cur.getNext();
}
}
}
class DoubleNode{
int val;
DoubleNode pre;
DoubleNode next;
public DoubleNode(int val) {
this.val = val;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public DoubleNode getPre() {
return pre;
}
public void setPre(DoubleNode pre) {
this.pre = pre;
}
public DoubleNode getNext() {
return next;
}
public void setNext(DoubleNode next) {
this.next = next;
}
@Override
public String toString() {
return "DoubleLinkedList{" +
"val=" + val +
", pre=" + pre +
", next=" + next +
'}';
}
}