目录
引入
栈和队列
定义
实现
1. 数组实现
1> 栈
2>队列
2. 链表实现
1> 栈
2> 队列
引入
什么是数据结构?
是数据在内存当中的存储形式而定。
大数据的查询-->用数组:数组在内存当中是连续的内存空间。(数组是可以通过下标去获取数据,遍历数据也方便)
增删改:---->用链表方便:链表在内存空间不连续(数组删除数据会导致内存空间的不连续,就算从前往后覆盖也麻烦)
总结:
同样这组数,因为存储形式不同导致的增删改查难易程度不同。
什么是算法?
对数据进行增删改查 等操作就是算法。
栈和队列
定义
什么是栈和队列?
没有确定的数据结构形成的数据结构。
解释:
栈:可以用数组去实现,可以用链表、树、图....
栈:满足让数据先进后出的特点就是栈。
队列:只要满足先进先出的就是队列。
实现
1. 数组实现
1> 栈
入栈:
出栈:
出栈的本质就是i--;
package com.lojarro.栈和队列;public class StackDemo {//首先声明一个数组private int[] arr;private int i=-1;public StackDemo(int size) {arr=new int[size];}//入栈的方法public void add(int value) {//判断数组是否为满if(i==arr.length-1) {System.out.println("栈已满");return ;}i++;arr[i]=value;}//出栈的方法public int get() {if(i==-1) {System.out.println("栈已空");return -1;}int data=arr[i];i--;return data;}
}
2>队列
只要满足先进先出的就是队列。
入队:
出队:
还有一种情况:
边放边出队情况。
判断队列满不满,看两个指标之间相差是不是数组的长度。
判断队列空,看两个指标指向是否相同。
package com.lojarro.栈和队列;import javax.xml.transform.Source;public class QueueDemo {private int arr[];private int c=0;private int r=0;public QueueDemo(int size) {arr=new int[size];}//数据的添加-入队列public void add(int value) {//判断是否已满if(r-c==arr.length) {System.out.println("队列已满");return ;}arr[r%arr.length]=value;r++;}public void get() {if(c==r) {System.out.println("队列空");return ;}System.out.println(arr[c%arr.length]);c++;}
}
2. 链表实现
1> 栈
只要满足先进后出特点就是。
链表的头插法满足这一特点。
public class Node {public int value;public Node next;public Node(int data) {value=data;}
}
public class Link {Node head=null;public void add(int value) {Node node=new Node(value);if(head==null) {head=node;return ;}node.next=head;head=node;}public void get() {if(head==null) {System.out.println("栈已空");return;}System.out.println(head.value);head=head.next;}
2> 队列
public void addQueue(int value) {Node node=new Node(value);if(head==null) {head=node;return ;}Node flag=head;while(flag.next!=null) {flag=flag.next;}flag.next=node;}public void getQueue() {if(head==null) {System.out.println("队列已空");return ;}System.out.println(head.value);head=head.next;}
}