北京网页网站设计制作,网站团队人员,保定网站建设浩森宇特,生物科技网站建设方案一、栈 Stack#xff08;存取O(1)#xff09;
先进后出#xff0c;进去123#xff0c;出来321。 基于数组#xff1a;最后一位为栈尾#xff0c;用于取操作。 基于链表#xff1a;第一位为栈尾#xff0c;用于取操作。 1.1、数组栈
/*** 基于数组实现的顺序栈#…一、栈 Stack存取O(1)
先进后出进去123出来321。 基于数组最后一位为栈尾用于取操作。 基于链表第一位为栈尾用于取操作。 1.1、数组栈
/*** 基于数组实现的顺序栈 items[0]表头/栈底 items[size-1]表尾/栈顶*/
public class MyArrayStack {// 存储元素的 数组private String items[];// 栈实际大小private int size 0;// 栈的容量private int capacity 0;public MyArrayStack(int capacity) {this.size 0;this.capacity capacity;this.items new String[capacity];}/*** 入栈*/public boolean push(String item) {if(size capacity){throw new IndexOutOfBoundsException(MyArrayStack 栈的内存满了);}items[size] item;size;return true;}/*** 出栈*/public String pop() {if(size0){throw new IndexOutOfBoundsException(MyArrayStack 栈的内存空了);}String item items[size-1];items[size-1] null;size--;return item;}
}
1.2、链表栈
/*** 基于链表实现的链式栈 top: 表尾/栈顶*/
public class MyLinkedStack {// 表尾/栈顶private Node top null;/*** 入栈*/public void push(String value) {Node node new Node(value,null);if(top ! null){node.nextNode top;}top node;}/*** 出栈*/public String pop() {if(topnull){throw new IndexOutOfBoundsException(MyLinkedStack 栈的内存空了);}String retValue top.getValue();top top.nextNode;return retValue;}/*** 节点*/private static class Node{// 存储数据private String value;// 下个节点private Node nextNode;public Node(String value, Node nextNode) {this.value value;this.nextNode nextNode;}public String getValue() {return value;}}
}
二、队列 Queue 存取O(1)
先进先出FIFO的有序列表
2.1、数组单向队列 存取O(1) /*** 基于数组实现的顺序队列*/
public class MyArrayQueue {private String [] items;// 容量private int capacity 0;// 队头下标private int head 0;// 队尾下标private int tail 0;public MyArrayQueue(int capacity) {this.items new String [capacity];this.capacity capacity;}/*** 入队*/public boolean enqueue(String item) {if(capacity tail){throw new IndexOutOfBoundsException(MyArrayQueue 容量满了);}items[tail] item;tail;return true;}/*** 出队*/public String dequeue() {if(headtail){throw new IndexOutOfBoundsException(MyArrayQueue 容量空了);}String retValue items[head];head;return retValue;}
}
2.2、链表单向队列 /*** 基于链表实现的链式队列*/
public class MyLinkedListQueue {// 队头private Node head null;// 队尾private Node tail null;/*** 入队*/public void enqueue(String value) {Node node new Node(value,null);if(tailnull){head node;tail node;}else {tail.nextnode;tailnode;}}/*** 出队*/public String dequeue() {if(headnull){throw new IndexOutOfBoundsException(MyLinkedListQueue 队列空了);}String retValue head.getValue();head head.next;if (head null) {tail null;}return retValue;}private static class Node{private String value;private Node next;public Node(String value, Node next) {this.value value;this.next next;}public String getValue() {return value;}}
}
三、链表 LinkedList
3.1、单向链表 /*** 单向普通链表*/
public class MyLinkedList {// 链表大小private int size;// 表头private Node head;/*** 插入*/public void insert(int index, String value) {if(index0){throw new IndexOutOfBoundsException(MyLinkedList 下标越界了);} else {if(headnull){head new Node(value,null);}else {if(indexsize){index size-1;}Node prev head;for(int i0;iindex;i){prev prev.next;}Node node new Node(value,prev);prev.next node;}size;}}/*** 获取*/public String get(int index){if(size0){throw new IllegalArgumentException(MyLinkedList 空链表);}if(index0 || indexsize) {throw new IllegalArgumentException(MyLinkedList 下标越界了);}Node prev head;for (int i0;iindex;i){prev prev.next;}return prev.getValue();}private class Node{private String value;private Node next;public Node(String value, Node next) {this.value value;this.next next;}public String getValue() {return value;}}
}
3.2、双向链表 public class MyDoubleLinkedList {// 链表大小private int size;// 表头private Node head;// 表尾private Node tail;/*** 插入*/public void insert(int index,String data) {if(index 0) {throw new IndexOutOfBoundsException(MyDoubleLinkedList insert 下标越界);}Node node new Node(data,null,null);if(index 0) {head.next node.next;head node;return;}if(index size) {tail.prev node.prev;tail node;return;}Node cur this.head;while(index ! 0) {cur cur.next;index--;}node.next cur;cur.prev.next node;node.prev cur.prev;cur.prev node;}public String get(int index){if(index0||indexsize){throw new IndexOutOfBoundsException(MyDoubleLinkedList get 下标越界了);}if(index(size/2)){Node cur head;for(int i 0;iindex-1;i){cur head.next;}return cur.getValue();}else {index size-index;Node cur tail;for (int isize;iindex;i--){cur cur.prev;}return cur.getValue();}}private class Node{public String value;public Node prev;public Node next;public Node(String value, Node prev, Node next) {this.value value;this.prev prev;this.next next;}public String getValue() {return value;}}
}
3.3、跳表
