1.栈
栈实现的是一种后进先出(last-in,first-out,LIFO)策略，栈上的insert操作称为压入（push),而无元素参数的delete操作称为弹出（pop）
实现栈的方式可以用数组和链表的方式来实现，一般默认为数组的方式来实现的
对于栈，由其FILO的特性，需要一个top标志，用来表示栈的最上面的元素，针对栈的操作也只有入栈push和出栈pop
在实现栈的时候需要考虑
- 在push操作考虑
栈上溢,栈上溢就是top标记超过了栈的大小。- 在pop操作考虑
栈下溢，栈下溢就是top对于一个空栈进行弹出操作
2.栈的数组方式实现
在这里栈默认是有大小的，但是栈一般都是动态的集合，这里展示简单演示栈，具体的可以参考jdk中的Stack中类
/**
* @Project: 10.dataStructure
* @description: 简单实现栈
* @author: sunkang
* @create: 2018-08-26 12:15
* @ModificationHistory who when What
**/
public class Stack<E> {
//指向最新插入的元素的位置
private int top ;
//记录栈的位置，这里这是简单实现，jdk中的栈为动态集合，这里写成固定的集合
private int size;
private Object[] stacks;
//构造栈的大小
public Stack(int size) {
this.size = size;
top = -1;
stacks = new Object[size];
}
public boolean isEmpty(){
if(top == -1){
return true;
}
return false;
}
/**
* 入栈 考虑栈的上届
* @param x
*/
public void push(E x) {
if( top >= size-1 ){
throw new ArrayIndexOutOfBoundsException("栈的上届溢出");
}
stacks[++top] = x;
}
/**
* 出栈 考虑下界
* @return
*/
public E pop() {
if( isEmpty() ){
throw new ArrayIndexOutOfBoundsException("栈的下界溢出");
}
return (E) stacks[top--];
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>(3);
stack.push(12);
stack.push(13);
System.out.println(stack.pop());
System.out.println(stack.pop());
// System.out.println(stack.pop());
}
3.队列
队列实现的是一种先进先出(firs-in,first-out,FIFO)的策略，队列上的insert操作称为入队（enqueue）,delete操作称为出队（dequeue）
对于队列，则需要一个head标志表示队列头，tail标志表示队列尾。最基本的操作也是有两个，插入队列和从队列中移除，队列的空间也是有限的，其状态同样需要进行判断。
head 表示指向队列头元素，而属性tail表示指向下一新元素将要插入的位置,
队列的中元素的存放在位置Q.head,Q.head+1,....Q.tail-1,并在最后的位置进行环绕
队列的实现需要考虑
入队的时候需要考虑队列是否已经满了
出队的时候需要考虑队列是否为null
3.队列的java代码的数组实现方式
- 普通数组队列：
尾部入队，头部出队
/**
* @Project: 10.dataStructure
* @description: 通过数组的方式实现队列
* @author: sunkang
* @create: 2018-08-26 12:36
* @ModificationHistory who when What
**/
public class QueueByArray<E> {
//指向下一个元素即将要插入的位置
private int tail ;
//指向队头的元素
private int head ;
//指向队列的大小
private int size;
//表示队列的数组
private Object[] queues;
public QueueByArray(int size) {
this.size = size;
tail = 0 ;
//-1标记没有头元素，也就是数组没有元素
head = -1;
queues = new Object[size];
}
/**
* 入队 ，从队尾部添加
* @param x
*/
public void enqueue(E x){
//1. 考虑队列已经满了
if(head == tail){
throw new ArrayIndexOutOfBoundsException("队列已经满了");
}
queues[tail] = x;
//2. 考虑队列头刚开始加入
if(head == -1){
head = tail;
}
//3.考虑队列到头了
if(tail == size-1){
tail = 0 ;
}else{
tail ++;
}
}
/**
* 出队 ，默认从头部出
*/
public E denqueue(){
//1. 考虑队列已经为空的情况
if(head == -1){
throw new ArrayIndexOutOfBoundsException("队列已经空了");
}
// 2. 出队
E x = (E) queues[head];
//3 考虑上届的临界的情况
if(head == size-1){
head = 0 ;
}else{
head++;
}
// 4.考虑队列已经空的情况
if(head ==tail) {
head = -1;
}
return x;
}
public static void main(String[] args) {
QueueByArray<Integer> queue = new QueueByArray<>(3);
queue.enqueue(12);
queue.enqueue(13);
queue.enqueue(14);
// queue.enqueue(125);
System.out.println(queue.denqueue());
System.out.println(queue.denqueue());
System.out.println(queue.denqueue());
// queue.denqueue();
queue.enqueue(15);
System.out.println(queue.denqueue());
}
}
- 双端队列：
出队和入队都可以在两端进行
/**
* @Project: 10.dataStructure
* @description: 双端队列 通过数组的方式
* @author: sunkang
* @create: 2018-08-26 16:00
* @ModificationHistory who when What
**/
public class DqueueByArray<E> {
//指向下一个元素即将要插入的位置
private int tail ;
//指向队头的元素
private int head ;
//指向队列的大小
private int size;
//表示队列的数组
private Object[] queues;
public DqueueByArray(int size) {
this.size = size;
tail = 0 ;
//-1标记没有头元素，也就是数组没有元素
head = -1;
queues = new Object[size];
}
/**
* 入队 ，从队尾部添加
* @param x
*/
public void push(E x){
//1. 考虑队列已经满了
if(head == tail){
throw new ArrayIndexOutOfBoundsException("队列已经满了");
}
queues[tail] = x;
//2. 考虑队列头刚开始加入
if(head == -1){
head = tail;
}
//3.考虑队列到头了
if(tail == size-1){
tail = 0 ;
}else{
tail ++;
}
}
/**
* 从头部增加元素
*/
public void unshift(E x){
//1.考虑满的情况
if(head == tail){
throw new ArrayIndexOutOfBoundsException("队列已经满了");
}
//2.考虑插入一个新的元素
if(head == -1){
head =tail;
}
//3 注意插入元素的下界问题
if(head == 0 ){
head = size -1;
}else{
head--;
}
queues[head] =x;
}
/**
* 从头部出队 ，默认从头部出
*/
public E shift(){
//1. 考虑队列已经为空的情况
if(head == -1){
throw new ArrayIndexOutOfBoundsException("队列已经空了");
}
// 2. 出队
E x = (E) queues[head];
//3 考虑上届的临界的情况
if(head == size-1){
head = 0 ;
}else{
head++;
}
// 4.考虑队列已经空的情况
if(head ==tail) {
head = -1;
}
return x;
}
/**
* 从尾部部出队
* @return
*/
public E pop(){
//1. 队列为空
if(head == -1){
throw new ArrayIndexOutOfBoundsException("队列已经空了");
}
//2 考虑插入元素的下界的情况
if(tail == 0){
tail = size-1;
}else{
tail --;
}
//3.队列为空的，设置head头的标记为-1
if(tail == head){
head = -1;
}
return (E) queues[tail];
}
public void display(){
if(head>tail) {
for (int i = head; i < size; i++) {
System.out.print(queues[i] + ",");
}
for (int j = 0; j < tail; j++) {
System.out.print(queues[j] + ",");
}
System.out.println();
}else {
for(int i = head;i<tail;i++){
System.out.print(queues[i] + ",");
}
System.out.println();
}
}
public static void main(String[] args) {
DqueueByArray<Integer> queue = new DqueueByArray<>(6);
queue.push(14);
queue.push(15);
queue.unshift(12);
queue.unshift(13);
queue.display();
//头部出去一个
queue.shift();
queue.display();
//尾部出去一个
queue.pop();
queue.display();
}
}
4.链表
链表（linked first）是这样的数字结构，其中的各个对象按线性顺序排列，链表的顺序是有各个对象的指针决定的
链表的结构如图所示：
链表.png
链表分类：
单向链表和双向链表和循环链表
双向链表：每一个元素都是对象，每个对象有一个关键字key和两个指针：next和prev单链表：每个节点，省略了prev指针循环链表:就是表头元素prev指针指向尾元素，而表尾元素next指向表头元素。
链表的头： 链表的第一个元素
链表的尾： 链表的最后一个元素
链表的优缺点
- 优点：
链表在内存中存储并不是连续的，可以很方便的进行插入和删除操作。- 缺点：由于链表的不连续存储特性，导致
索引操作不能使用下标进行，因此对链表进行搜索操作时间复杂度是O(n)级别的。
5.链表的具体实现
链表的插入操作需要考虑
- 1.头标记为null （第一次插入）
- 2.插入节点的上一个节点为null(头部插入)
- 3.插入节点上一个节点不为null(中间插入)
- 4.插入节点的下一个节点为null(尾部插入)
- 5.插入节点的下一个节点都不为null(中间插入)
链表的删除操作需要考虑
- 1.删除节点为null
- 2.删除节点的上一个节点不为空（中间删除）
- 3.删除节点的上一个节点为空(头部删除)
- 4.删除节点的下一个节点不为空（中间删除）
- 5.删除节点的下一个节点为空（尾部删除）
更加具体的代码可以参考jdk中的linkedList ,如果有机会后面的源码分析课程会将这个
具体的代码如下：
/**
* @Project: 10.dataStructure
* @description: 双向链表
* @author: sunkang
* @create: 2018-08-26 16:58
* @ModificationHistory who when What
**/
public class LinkedList<E> {
//链表的头标记指向
private Node<E> first;
//链表的尾部标记指向
private Node<E> last;
class Node<E>{
public Node<E> next;
public Node<E> prev;
public E key;
public Node(E key) {
this.key = key;
}
}
/**
* 查找一个元素
* @param key
* @return
*/
public Node<E> search(E key){
Node<E> next = first;
while(next != null && !next.key.equals( key) ){
next = next.next;
}
return next;
}
/**
* 队列前面插入
* 有下面的情况 1和 2
*
*一般来说，对于任何一个节点的普通插入来说分为下面的几种情况
* 1. 头标记为null （第一次插入）
* 2.插入节点的上一个节点为null(头部插入)
* 3.插入节点的下一个节点为null(尾部插入)
* 4.插入节点上一个节点和下一个节点都不为null(中间插入)
*
* @param key
* @return
*/
public void insertFirst(E key){
Node node = new Node(key);
//1.队列为空的情况
if(first == null){
first = node;
last = node;
}else{ // 队列不为null的情况
Node next = first;
//更新当前的节点与下一个节点的连接
next.prev = node;
node.next = next;
//更新头标记
first = node;
}
}
/**
* 插入尾部
* @param key
*/
public void insertLast(E key){
Node node = new Node(key);
//1.队列为空的情况
if(last == null){
first = node;
last = node;
}else{
//更新当前的节点与下一个节点的连接
last.next =node ;
node.prev = last;
//更新头标记
last = node;
}
}
/**
* 头部节点的删除
*
* 1.头节点为null
* 2.头节点为null,头节点的下一个不为null
* 3.头节点为null,头节点的下一个节点为null
*/
public E removeFirst(){
//情况1. 头节点为null
if(first == null){
return null;
}
E item = first.key;
Node next = first.next;
//2.头节点不为null,头节点下一个节点不为null
if(next != null ){
next.prev = null;
}else{//3. 头部节点的下一个节点不为null
last =null;
}
first.next = null;
//更新头节点的标记
first = next;
return item;
}
public E removeLast(){
//case 1
if(last == null){
return null;
}
E item = last.key;
Node prev = last.prev;
if(prev != null){ //case 2
prev.next = null;
}else{//case 3
first = null;
}
last.prev = null;
//更新尾部的标记
last = prev;
return item;
}
/**
*删除指定的节点
*包含着五种情况 （删除基本离不开这5中情况）
* 1.删除节点为null
* 2.删除节点的前面不为空
* 3.删除节点的前置节点为空说明为删除节点为头结点，需要更新头节点的标记
* 4.删除节点的后面不为空
* 5.删除节点下一个为空说明为删除节点为尾结点，需要更新头尾部的标记
* @return
*/
public E remove(E key){
Node<E> remove = search(key);
//1. 如果删除元素不存在
if(remove == null){
return null;
}else{
//2.删除节点的前面不为空
if(remove.prev != null){
remove.prev.next = remove.next;
}else{ // 3.删除节点的前置节点为空说明为删除节点为头结点，需要更新头节点的标记
first = remove.next;
}
//4.删除节点的后面不为空
if(remove.next !=null){
remove.next.prev = remove.prev;
}else{//5.删除节点下一个为空说明为删除节点为尾结点，需要更新头尾部的标记
last = remove.prev;
}
//清空删除节点自身的信息,help GC
remove.next = null;
remove.prev = null;
}
return remove.key;
}
public void display(){
for( Node<E> next = first;next != null;next=next.next){
System.out.print(next.key+",");
}
System.out.println();
}
/**
* 详细的代码还是参考jdk linkedList ，这里也是一个双链表的结构
* @param args
*/
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<Integer>() ;
linkedList.insertFirst(123);
linkedList.insertFirst(456);
linkedList.insertFirst(789);
linkedList.display();
linkedList.removeFirst();
linkedList.display();
linkedList.removeLast();
linkedList.display();
linkedList.remove(456);
linkedList.display();
linkedList.insertLast(123);
linkedList.insertLast(456);
linkedList.display();
}
}
