一、 栈
1、概念
栈是一种特殊的线性表，它只能在栈顶(top)进行插入(push)和删除(pop)操作。
栈的常用操作：
入栈(push)：向栈顶插入元素
出栈(pop):从栈顶删除元素
访问栈顶元素(peek)：访问栈顶元素
2、 栈的顺序结构的实现
1 public class SequenceStack<T> { 2 3 private Object[] elementData; //数组用于承装元素 4 private int DEFAULT_SIZE = 20; //初始数组默认大小 5 private int capacity; 6 private int capacityIncrement = 5; 7 private int size = 0; //栈中当前容量 8 public SequenceStack(){ 9 capacity = DEFAULT_SIZE; 10 elementData = new Object[capacity]; 11 } 12 public SequenceStack(T element){ 13 this(); 14 elementData[0] = element; 15 size++; 16 } 17 //返回栈的长度 18 public int length(){ 19 return this.size; 20 } 21 22 //入栈操作 23 public void push(T element){ 24 this.ensureCapacity(); 25 elementData[size] = element; 26 size++; 27 } 28 29 //出栈操作 30 public T pop(){ 31 T popElement = (T)elementData[size-1]; 32 size--; 33 return popElement; 34 } 35 36 //访问栈顶元素 37 public T peek(){ 38 return (T)elementData[size-1]; 39 } 40 41 //判断是否为空 42 public boolean isEmpty(){ 43 boolean b = false; 44 if(size == 0){ 45 b = true; 46 } 47 return b; 48 } 49 50 //清空栈 51 public void clear(){ 52 for(Object o:elementData){ 53 o = null; 54 } 55 size = 0; 56 } 57 58 //遍历栈 59 public void view(){ 60 System.out.print("当前栈中元素为："); 61 for(int i = 0;i < size;i++){ 62 System.out.print(elementData[i] + " "); 63 } 64 System.out.println(); 65 } 66 67 //栈容量检测与扩充 68 public void ensureCapacity(){ 69 if(capacityIncrement > 0){ 70 while((size+1) > capacity){ 71 capacity+=capacityIncrement; 72 } 73 } 74 else{ 75 while((size+1) > capacity){ 76 capacity = capacity * 2; 77 } 78 } 79 } 80 81 public static void main(String[] args) { 82 SequenceStack<String> sequenceStack = new SequenceStack<> (); 83 sequenceStack.push("hello"); 84 sequenceStack.push("world"); 85 sequenceStack.push("perfect"); 86 System.out.print("入栈操作后，"); 87 sequenceStack.view(); 88 sequenceStack.pop(); 89 System.out.print("出栈操作后，"); 90 sequenceStack.view(); 91 System.out.println("当前栈顶元素为：" + sequenceStack.peek()); 92 sequenceStack.clear(); 93 System.out.println("clear之后，栈是否为空：" + sequenceStack.isEmpty()); 94 } 95 }
3、栈的链式结构的实现：
1 public class LinkedStack<T> { 2 3 private class Node{ 4 private T data; 5 private Node next; 6 public Node(){ 7 8 } 9 public Node(T element,Node next){ 10 this.data = element; 11 this.next = next; 12 } 13 } 14 15 private Node top; 16 private int size = 0; 17 18 public LinkedStack(){ 19 20 } 21 22 public LinkedStack(T element){ 23 top = new Node(element,null); 24 size++; 25 } 26 //获取栈大小 27 public int length(){ 28 return size; 29 } 30 //入栈操作 31 public void push(T element){ 32 Node newNode; 33 newNode = new Node(element, top); 34 top = newNode; 35 size++; 36 } 37 //出栈操作 38 public T pop(){ 39 Node oldNode = top; 40 top = top.next; 41 oldNode.next = null; 42 size--; 43 return oldNode.data; 44 } 45 46 //获取栈顶元素 47 public T peek(){ 48 return top.data; 49 } 50 51 //清空栈 52 public void clear(){ 53 top = null; 54 size = 0; 55 } 56 57 public boolean isEmpty(){ 58 if(size == 0){ 59 return true; 60 } 61 return false; 62 } 63 64 //遍历栈中元素 65 public void view(){ 66 Node currentNode = top; 67 System.out.print("栈中元素为："); 68 while(currentNode != null){ 69 System.out.print(currentNode.data + " "); 70 currentNode = currentNode.next; 71 } 72 System.out.println(); 73 } 74 75 public static void main(String[] args) { 76 LinkedStack<String> linkedStack = new LinkedStack<>(); 77 linkedStack.push("hello"); 78 linkedStack.push("world"); 79 linkedStack.push("perfect"); 80 System.out.print("入栈操作后，"); 81 linkedStack.view(); 82 linkedStack.pop(); 83 System.out.print("出栈操作后，"); 84 linkedStack.view(); 85 System.out.println("当前栈顶元素为：" + linkedStack.peek()); 86 linkedStack.clear(); 87 System.out.println("clear之后，栈是否为空：" + linkedStack.isEmpty()); 88 } 89 }
三、 队列
1、概念
队列是一种被限制的线性表，它只允许在表的前端(front，即队尾)进行删除操作，只允许在表的后端(rear，即队头)进行插入操作
常用操作：
加入元素：向队列rear端插入元素
删除元素：从队列的front端删除元素
访问队列front端元素：
2、队列的顺序存储结构及实现
1 public class SequenceQueue<T> { 2 3 private int DEFAULT_SIZE = 20; 4 private int capacity; 5 private int front = 0; 6 private int rear = 0; 7 private Object[] elementData; 8 public SequenceQueue(){ 9 capacity = DEFAULT_SIZE; 10 elementData = new Object[capacity]; 11 } 12 public SequenceQueue(T element){ 13 this(); 14 elementData[0] = element; 15 rear++; 16 } 17 // 获取队列长度 18 public int length(){ 19 return rear-front; 20 } 21 22 //向队列尾添加元素 23 public void add(T element){ 24 if(rear > capacity-1){ 25 throw new IndexOutOfBoundsException("队列已满"); 26 } 27 elementData[rear++] = element; 28 } 29 30 //删除队列头元素 31 public T remove(){ 32 if((rear-front) == 0){ 33 throw new IndexOutOfBoundsException("队列为空，不能删除"); 34 } 35 T remove = (T)elementData[front]; 36 elementData[front++] = null; 37 return remove; 38 } 39 40 //获取队列头部元素 41 public T getElement(){ 42 return (T)elementData[front]; 43 } 44 45 //判断队列是否为空 46 public boolean isEmpty(){ 47 return (rear-front) == 0; 48 } 49 50 //清空队列 51 public void clear(){ 52 Arrays.fill(elementData, null); 53 front = 0; 54 rear = 0; 55 } 56 57 //遍历队列 58 public void view(){ 59 System.out.print("队列中元素为："); 60 for(int i = front;i < rear; i++){ 61 System.out.print(elementData[i] + " "); 62 } 63 System.out.println(); 64 } 65 66 public static void main(String[] args) { 67 SequenceQueue<String> sequenceQueue = new SequenceQueue<> (); 68 sequenceQueue.add("hello"); 69 sequenceQueue.add("world"); 70 sequenceQueue.add("perfect"); 71 sequenceQueue.view(); 72 System.out.println("执行remove删除的元素为：" + sequenceQueue.remove()); 73 System.out.println("队列头部元素为：" + sequenceQueue.getElement()); 74 sequenceQueue.clear(); 75 System.out.println("clear之后队列长度：" + sequenceQueue.length()); 76 77 } 78 79 }
3、顺序存储结构的循环队列
1 public class LoopSequenceQueue<T> { 2 3 private int DEFAULT_SIZE = 5; 4 private int capacity; 5 private int front = 0; 6 private int rear = 0; 7 private Object[] elementData; 8 9 public LoopSequenceQueue(){ 10 capacity = DEFAULT_SIZE; 11 elementData = new Object[capacity]; 12 } 13 14 public LoopSequenceQueue(T element){ 15 this(); 16 elementData[0] = element; 17 rear++; 18 } 19 20 //获取队列长度 21 public int length(){ 22 if(isEmpty()){ 23 return 0; 24 } 25 return rear > front?rear-front:(capacity-(front-rear)); 26 } 27 28 //向队列中插入元素 29 public void add(T element){ 30 if(rear == front && elementData[front] != null){ 31 throw new IndexOutOfBoundsException("队列已满"); 32 } 33 elementData[rear] = element; 34 rear = (rear+1) > (capacity-1)?0:(++rear); 35 } 36 37 //从队列头删除元素 38 public T delete(){ 39 if(isEmpty()){ 40 throw new IndexOutOfBoundsException("队列为空"); 41 } 42 T del = (T)elementData[front]; 43 elementData[front] = null; 44 front = (front+1) > capacity?0:++front; 45 return del; 46 } 47 48 //清空队列 49 public void clear(){ 50 Arrays.fill(elementData, null); 51 front = 0; 52 rear = 0; 53 } 54 55 //遍历队列 56 public void view(){ 57 System.out.print("队列中元素为："); 58 if(front < rear){ 59 for(int i = front;i < rear;i++){ 60 System.out.print(elementData[i] + " "); 61 } 62 } 63 else{ 64 for(int i = front;i < capacity;i++) 65 System.out.print(elementData[i] + " "); 66 for(int i = 0;i < rear;i++) 67 System.out.print(elementData[i] + " "); 68 } 69 } 70 71 //判断队列是否为空 72 public boolean isEmpty(){ 73 if(front == rear && elementData[front] == null){ 74 return true; 75 } 76 return false; 77 } 78 79 public static void main(String[] args) { 80 LoopSequenceQueue<String> loopSequenceQueue = new LoopSequenceQueue<>(); 81 loopSequenceQueue.add("hello"); 82 loopSequenceQueue.add("world"); 83 loopSequenceQueue.add("perfect"); 84 loopSequenceQueue.add("3333333"); 85 loopSequenceQueue.delete(); 86 loopSequenceQueue.add("4444444444"); 87 loopSequenceQueue.add("555555555"); 88 loopSequenceQueue.view(); 89 System.out.println("当前队列长度为：" + loopSequenceQueue.length()); 90 91 92 } 93 94 }
4、队列的链式存储结构
1 public class LinkedQueue<T> { 2 3 private class Node{ 4 private T data; 5 private Node next; 6 public Node(){ 7 8 } 9 10 public Node(T element,Node next){ 11 this.data = element; 12 this.next = next; 13 } 14 } 15 16 private Node front; 17 private Node rear; 18 private int size = 0; 19 public LinkedQueue(){ 20 this.front = null; 21 this.rear = null; 22 } 23 24 public LinkedQueue(T element){ 25 rear = new Node(element,null); 26 front = rear; 27 size++; 28 } 29 //获取队列长度 30 public int length(){ 31 return size; 32 } 33 34 //从队尾插入元素 35 public void add(T element){ 36 Node newNode = new Node(element,null); 37 if(rear == null){ 38 rear = newNode; 39 front = rear; 40 } 41 else{ 42 rear.next = newNode; 43 rear = newNode; 44 } 45 46 size++; 47 } 48 //删除队头元素 49 public T remove(){ 50 if(size == 0){ 51 throw new IndexOutOfBoundsException("队列为空，不能删除"); 52 } 53 Node delNode = front; 54 front = front.next; 55 delNode.next = null; 56 size--; 57 return delNode.data; 58 } 59 60 //清空队列 61 public void clear(){ 62 front = null; 63 rear = null; 64 size = 0; 65 } 66 67 //遍历队列元素 68 public void view(){ 69 System.out.print("队列中元素为："); 70 Node currentNode = front; 71 while(currentNode != null){ 72 System.out.print(currentNode.data + " "); 73 currentNode = currentNode.next; 74 } 75 System.out.println(); 76 } 77 78 79 public static void main(String[] args) { 80 LinkedQueue<String> linkedQueue = new LinkedQueue<> (); 81 linkedQueue.add("hello"); 82 linkedQueue.add("world"); 83 linkedQueue.add("perfect"); 84 linkedQueue.add("3333333"); 85 linkedQueue.remove(); 86 linkedQueue.add("4444444444"); 87 linkedQueue.add("555555555"); 88 linkedQueue.view(); 89 System.out.println("当前队列长度为：" + linkedQueue.length()); 90 91 } 92 93 }
注：本文部分内容参考自《疯狂Java程序员的基本修养》