家用电脑可以做网站服务器,晋中网站设计,psd免费素材网,百度网站排名抓取规则一、栈 Stack
1.特点
#xff08;1#xff09;栈是一种线性数据结构
#xff08;2#xff09;规定只能从栈顶添加元素#xff0c;从栈顶取出元素
#xff08;3#xff09;是一种先进后出的数据结构#xff08;Last First Out#xff09;LIFO
2.具体实现
Java中可…一、栈 Stack
1.特点
1栈是一种线性数据结构
2规定只能从栈顶添加元素从栈顶取出元素
3是一种先进后出的数据结构Last First OutLIFO
2.具体实现
Java中可以直接调用方法来实现栈 如何自己写代码来实现栈呢
先定义一个接口方便后边进行调用
package com.algo.lesson.lesson02.stack;public interface Stack_IT {//入栈void push(T ele);//出栈T pop();//查看栈顶元素T peek();//判断是否为空boolean isEmpty();//后去栈中元素int getSize();
}接下来来实现栈的方法调用接口完善方法
package com.algo.lesson.lesson02.stack;import com.algo.lesson.lesson01.MyArr;//以数组作为栈顶的底层数据结构
public class ArrStackT implements Stack_IT {private MyArrTdata;int size;public ArrStack() {this.datanew MyArr(100);this.size0;}Overridepublic void push(T ele) {//在数组尾部添加元素this.data.add(ele);this.size;}Overridepublic T pop() {if(isEmpty()){return null;}this.size--;return this.data.removeBFromLast();}Overridepublic T peek() {return this.data.getLastValue();}Overridepublic boolean isEmpty() {return this.size0;}Overridepublic int getSize() {return this.size;}
}以上就是方法的代码接下来写个main函数来调用检查方法是否正确
package com.algo.lesson.lesson02.stack;import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class StackTestT {public void test(Stack_ITstack, ListT list){//开始时间long startTimeSystem.nanoTime();for(int i0;ilist.size();i){stack.push(list.get(i));}System.out.println(stack.getSize());while(!stack.isEmpty()){T elestack.pop();System.out.println(ele );}//结束时间long endTimeSystem.nanoTime();System.out.println(总耗时(endTime-startTime)/100000000.0);}public static void main(String[] args) {StackTestIntegerstackTestnew StackTest();Stack_IIntegerstacknew ArrStack();ListIntegerlistnew ArrayList();Random randomnew Random();for(int i0;i100;i){int val random.nextInt(1000);list.add(val);}stackTest.test(stack,list);}
}注其中long startTimeSystem.nanoTime();方法是获取一个时间单位毫秒
在程序运行前和运行后个添加一个最后将两个时间相减得到程序运行时间。 3.时间复杂度分析 二、队列
1.特点
1队列也是一种线性数据结构
2只能从一端添加元素另一端取出元素
3是一种先进先出的数据结构FIFO——fist in fist out
2.具体实现
Java中也可以直接调用队列的方法 自己的实现
接口
package com.algo.lesson.lesson02.queue;public interface Queue_IT {void offer(T ele);//入队T poll();//出队T peek();//查找队首元素int getSize();boolean isEmpty();}方法代码
package com.algo.lesson.lesson02.queue;import com.algo.lesson.lesson01.MyArr;public class ArrQueueTimplements Queue_IT {private MyArrTdata;/*private int size;//队列中元素的个数
*/public ArrQueue(){this.datanew MyArr(50);}Overridepublic void offer(T ele) {this.data.add(ele);}Overridepublic T poll() {if(isEmpty()){return null;}return this.data.removeByIndex(0);}Overridepublic T peek() {if(isEmpty()){return null;}return this.data.getValueByIndex(0);}Overridepublic int getSize() {return this.data.getSize();}Overridepublic boolean isEmpty() {return this.data.isEmpty();}
}3.出现的问题
入队列时间复杂度为O(n)因为在出队时元素要前移会出现假溢出的情况。
所以就出现了循环队列来解决这个问题
循环队列
front记录队首tail记录队尾队尾达到容积时返回到队头将空位置补上可以继续存储数据。
package com.algo.lesson.lesson02.queue;import java.util.Random;/*
基于Java中的数组进行二次封装,制作一个可变数组*/
//泛型:就是类型作为参数
public class LoopArrT {private T[] data;//保存数据private int size;//数组中实际存放元素的个数private int front;//队首private int tail;//队尾int capacity;//容积//构造函数public LoopArr(int capacity) {if (capacity 0) {this.capacity 11;} else {this.capacity capacity 1;}this.size 0;this.front this.tail 0;this.data (T[]) (new Object[this.capacity]);}//获取数组中实际存放元素的个数public int getSize() {return this.size;}//获取数组的容积public int getCapacity() {return this.capacity;}//判断数组是否为空public boolean isEmpty() {return this.front this.tail;}//向数组中添加元素(尾部)public void add(T item) {//判断数组是否满if ((this.tail 1) % this.capacity this.front) {//扩容resize((this.capacity-1)*21);}//从index位置开始元素需要进行后移this.data[this.tail] item;this.tail (this.tail 1) % this.capacity;//更新this.sizethis.size;}private void resize(int newCapacity) {System.out.println(resize: newCapacity);T[] newData (T[]) (new Object[newCapacity]);//将原数组驾到新数组里for (int i 0; i this.size; i) {newData[i] this.data[(this.fronti)%this.capacity];}//改变容器this.data newData;this.capacity newCapacity;//将this.front置零this.front0;this.tailthis.size;}//获取指定位置的值public T getValueByIndex() {if(isEmpty()){return null;}return this.data[this.front];}//移除队首元素public T remove() {if (isEmpty()) {return null;}//删除操作的核心/*1.找到删除的位置2.删除位置之后的元素要前移 arr[j-1]arr[j]*/T delValue this.data[this.front];this.front (this.front 1) % this.capacity;this.size--;//判断是否缩容if (this.size this.capacity / 4 this.capacity / 2 0) {resize((this.capacity-1) / 2 1);}return delValue;}Overridepublic String toString() {StringBuilder sb new StringBuilder([);for (int i 0; i this.size; i) {sb.append(this.data[i]);if (i ! this.size - 1) {sb.append(,);}}sb.append(]);return sb.toString();}
}
package com.algo.lesson.lesson02.queue;public class LoopQueueT implements Queue_IT{private LoopArrTdata;//容器public LoopQueue(){this.datanew LoopArr(100);}Overridepublic void offer(T ele) {this.data.add(ele);}Overridepublic T poll() {return this.data.remove();}Overridepublic T peek() {return this.data.getValueByIndex();}Overridepublic int getSize() {return this.data.getSize();}Overridepublic boolean isEmpty() {return this.data.isEmpty();}
}4.循环队列的复杂度分析 三、栈和队列的互相实现
既然我们了解了栈和队列知道了这两种数据结构十分相似也就可以大胆假设以下可不可以相互实现不是用上面所写的以数组为底层而是相互为底层存储。
1.用栈来实现队列
import java.util.Stack;class MyQueue {private StackInteger A;private StackInteger B;public MyQueue() {A new Stack();B new Stack();}public void push(int x) {while (!B.isEmpty()) {A.push(B.pop());}A.push(x);while (!A.isEmpty()) {B.push(A.pop());}}public int pop() {return B.pop();}public int peek() {return B.peek();}public boolean empty() {return B.isEmpty();}
}2.用队列实现栈
import java.util.LinkedList;
import java.util.Queue;class MyStack {private QueueInteger queue1;private QueueInteger queue2;public MyStack() {queue1 new LinkedList();queue2 new LinkedList();}public void push(int x) {queue2.add(x);while (!queue1.isEmpty()) {queue2.add(queue1.remove());}QueueInteger temp queue1;queue1 queue2;queue2 temp;}public int pop() {return queue1.remove();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}这就是这两种数据结构相互实现的代码
在LeetCode中也有相对应的题目
力扣LeetCode官网 - 全球极客挚爱的技术成长平台栈实现队列
力扣LeetCode官网 - 全球极客挚爱的技术成长平台队列实现栈
