免费ppt模板下载大全网站,vs2012网站开发,wordpress调用慢,网站免费正能量直接进入检察官1.栈的概念
1.栈的定义
栈是仅限在表尾进行插入和删除的线性表#xff0c;栈又被称为先进后出的线性表#xff0c;简称“LIFO”
我们这次用数组作为我们栈的底层数据结构#xff0c;代码会放到结尾供大家参考使用
2.栈顶的定义
栈是一个线性表#xff0c;我们允许插入…1.栈的概念
1.栈的定义
栈是仅限在表尾进行插入和删除的线性表栈又被称为先进后出的线性表简称“LIFO”
我们这次用数组作为我们栈的底层数据结构代码会放到结尾供大家参考使用
2.栈顶的定义
栈是一个线性表我们允许插入和删除的一端称为栈顶
3.栈底的定义
和栈顶相对的另一端称为栈底实际上栈底的元素我们不需要关心
4.栈的创建 //数据容器private T[] data;//容积private int capacity;//实际存放的元素个数private int size;
2.入栈
1.入栈的定义
栈元素的插入操作叫做入栈也可以称为进栈、压栈
2.动画演示 图中是以链表为底层数据结构的大家看图了解个大概就可以了具体可以看代码是怎么实现的
3.代码实现 //在末尾添加元素public void addTail(T val) {//this.data[size]val;this.add(this.size, val);}//在中间插入元素public void add(int index, T val) {if (index 0 || index size) {throw new IllegalArgumentException(index is invalid!);}//判断数组是否满if(this.sizethis.capacity){//数组满的话扩容原来数组的两倍int newCapacitythis.capacity*2;T[] newDate(T[]) new Object[newCapacity];//创建一个新的数组//进行数组迁移for (int i 0; i this.size; i) {newDate[i]this.data[i];}this.capacitynewCapacity;this.datanewDate;}
3.出栈
1.出栈的定义
栈元素的删除操作叫做出栈也可称为弹栈
2.动画演示 3.代码演示 //移出末尾public T removeTail() {
// T valthis.data[size-1];
// this.size-1;
// return val;return this.remove(this.size);}//中部移出public T remove(int index) {if (index 0 || index size) {throw new IllegalArgumentException(index is invalid!);}T val this.data[index];for (int i index; i this.size; i) {this.data[i] this.data[i1];}this.size - 1;if(this.sizethis.capacity/4this.capacity/21){int newCapacitythis.capacity/2;T[] newDate(T[])new Object[newCapacity];for (int i 0; i this.size; i) {newDate[i]this.data[i];}this.capacitynewCapacity;this.datanewDate;}
4.查询栈顶
1.获取栈顶的定义
一般我们可以去查看栈顶的元素是什么
2.动画演示 3.代码演示
public T peek(T val) {return data.getEnByIndex(this.size() - 1);}//获得指定索引的元素public T getEnByIndex(int index) {if (index 0 || index size) {throw new IllegalArgumentException(index is invalid!);}return this.data[index];}
基本的栈能用到的就这些基本的方法接下来给大家一个完整的代码供大家学习参考
public class StackDemoT implements StackT {//以我们封装的数组作为栈的底层数据结构private arrSubTdata;public StackDemo() {datanew arrSub();}public StackDemo(int capacity) {datanew arrSub(capacity);}Override//弹栈public T pop() {return data.removeTail();}Override//往栈中添加元素public void push(T val) {data.addTail(val);}Override//查看元素个数public int size() {return data.getSize();//获得数组元素个数}Override//判断是否为空public boolean isEmpty() {return data.isEmpty();}Override//查看栈顶元素public T peek(T val) {return data.getEnByIndex(this.size() - 1);}Overridepublic T peek() {return null;}Overridepublic String toString() {StringBuilder sb new StringBuilder(栈顶[);T[] arr data.getData();for (int i size() - 1; i 0; i--) {sb.append(arr[i]);if (i ! 0) {sb.append(,);}}sb.append(]栈底);return sb.toString();}public static void main(String[] args) {StackString stack new StackDemo(10);String[] fruits {apple, banana, peach, watermelon, strawberry, pear, orange, grape};for (int i 0; i fruits.length; i) {stack.push(fruits[i]);}System.out.println(stack);while (!stack.isEmpty()) {System.out.println(ele-- stack.pop());System.out.println(stack 栈中元素的个数 stack.size());}}
}
public class arrSubT {//数据容器private T[] data;//容积private int capacity;//实际存放的元素个数private int size;public arrSub(int capacity) {this.capacity capacity;this.data (T[]) new Object[this.capacity];this.size 0;}public arrSub() {this.capacity 10;}// 判断数据容器是否为空public boolean isEmpty() {return this.size 0;}public T[] getData(){return this.data;}//获得数组的容积public int getCapacity() {return this.capacity;}//获取元素的个数public int getSize() {return this.size;}//首行添加元素public void addTop(T val) {
// for (int i size-1; i 0 ; i--) {
// this.data[i1]this.data[i];
// }
// this.data[0]val;this.add(0, val);}//在末尾添加元素public void addTail(T val) {//this.data[size]val;this.add(this.size, val);}//在中间插入元素public void add(int index, T val) {if (index 0 || index size) {throw new IllegalArgumentException(index is invalid!);}//判断数组是否满if(this.sizethis.capacity){//数组满的话扩容原来数组的两倍int newCapacitythis.capacity*2;T[] newDate(T[]) new Object[newCapacity];//创建一个新的数组//进行数组迁移for (int i 0; i this.size; i) {newDate[i]this.data[i];}this.capacitynewCapacity;this.datanewDate;}for (int i this.size - 1; i index; i--) {this.data[i 1] this.data[i];}this.data[index] val;this.size 1;}//获得指定索引的元素public T getEnByIndex(int index) {if (index 0 || index size) {throw new IllegalArgumentException(index is invalid!);}return this.data[index];}//获得指定元素的索引public int getEnByVal(int index, T val) {if (index 0 || index size) {throw new IllegalArgumentException(index is invalid!);}for (int i 0; i this.size; i) {if (this.data[i] val) {return i;}}return -1;}//判断是否包含某种布局public boolean contains(T val) {for (int i 0; i this.size; i) {if (this.data[i] val) {return true;}}return false;}//修改指定索引的元素public void upLoad(T var, int index) {if (index 0 || index this.size) {throw new IllegalArgumentException(index is invalid!);}this.data[index] var;}//重写toString的方法Overridepublic String toString() {StringBuilder stringBuilder new StringBuilder(10);for (int i 0; i this.size; i) {stringBuilder.append(this.data[i] ,);}return stringBuilder.substring(0, stringBuilder.lastIndexOf(,) -1 ? 0 : stringBuilder.lastIndexOf(,));}//移出末尾public T removeTail() {
// T valthis.data[size-1];
// this.size-1;
// return val;return this.remove(this.size);}//移出首部public T removeTop() {
// T valthis.data[0];
// for (int i 1; i this.size; i) {
// this.data[i-1]this.data[i];
// }
// this.size-1;
// return val;return this.remove(0);}//中部移出public T remove(int index) {if (index 0 || index size) {throw new IllegalArgumentException(index is invalid!);}T val this.data[index];for (int i index; i this.size; i) {this.data[i] this.data[i1];}this.size - 1;if(this.sizethis.capacity/4this.capacity/21){int newCapacitythis.capacity/2;T[] newDate(T[])new Object[newCapacity];for (int i 0; i this.size; i) {newDate[i]this.data[i];}this.capacitynewCapacity;this.datanewDate;}return val;}public static void main(String[] args) {arrSub myArr new arrSub(50);for (int i 1; i 20; i) {myArr.addTail(i 10);}System.out.println(myArr);
// System.out.println(20? myArr.contains(20));
// System.out.println(50? myArr.contains(50));while (!myArr.isEmpty()) {myArr.removeTail();System.out.println(myArr);}}leetcode题单
从尾到头打印链表 public int[] reversePrint(ListNode head) {LinkedListInteger stack new LinkedListInteger();while(head ! null) {stack.addLast(head.val);head head.next;}int[] res new int[stack.size()];for(int i 0; i res.length; i)res[i] stack.removeLast();return res;}
括号的最大嵌套深度 public int maxDepth(String s) {int ans 0, size 0;for (int i 0; i s.length(); i) {char ch s.charAt(i);if (ch () {size;ans Math.max(ans, size);} else if (ch )) {--size;}}return ans;}
回文链表
public boolean isPalindrome(ListNode head) {if(headnull){return false;}StringBuilder s1new StringBuilder();StringBuilder s2new StringBuilder();while(head!null){s1.append(head.val);s2.append(head.val);headhead.next;}s2.reverse();return s1.toString().equals(s2.toString());}
这里以数组为底层结构的队列代码供大家参考
import java.util.Optional;public class ArrQueueT implements QueueT {// 队列的容器CycleArrayT data;// 构造函数public ArrQueue() {data new CycleArray();}public ArrQueue(int capacity) {this.data new CycleArray(capacity);}Overridepublic void offer(T ele) {data.addTail(ele);}Overridepublic T poll() {return data.removeHead();}Overridepublic int size() {return data.getSize();}Overridepublic boolean isEmpty() {return data.isEmpty();}Overridepublic T peek() {OptionalT optional data.getFront();if (optional.isPresent()) {return optional.get();}return null;}Overridepublic String toString() {return data.toString();}
}import java.util.Optional;/*解决了队列删除时的时间复杂度O(n),循环队列删除时的时间复杂度为O(1)* 假设有两个索引,front--始终指该数组的第一个元素 tail--始终指向元素插入位置* 如果fronttail时,该循环数组为空* 如果(tail1)%capacityfront时,该数组为满状态** */
/*** 循环队列的底层容器*/
public class CycleArrayT {// 数据容器private T[] data;// 容积private int capacity;// 实际存放元素的个数private int size;// 声明两个索引 front--队首 tail--队尾int front 0;int tail 0;// front tail 队列是空的 (tail1)/capacity front 队列是满的public CycleArray() {this(10);}public CycleArray(int capacity) {this.capacity capacity 1;//因为要浪费一个空间,所以在这里要多加一个空间this.data (T[]) new Object[this.capacity];// 浪费一个空间this.size 0;}public T[] getData() {return this.data;}// 1、队列是否为空public boolean isEmpty() {return this.front this.tail;}// 2、获取数组的容积public int getCapacity() {return this.capacity;}//3、获取实际存放元素的个数public int getSize() {return this.size;}// 在队列的尾部添加元素tail指向待插入元素的位置public void addTail(T val) {// 当队列已满要进行扩容if ((this.tail 1) % this.capacity this.front) {// 新的容积int newCapacity 2 * (this.capacity - 1);resize(newCapacity);}// 将val插入到队列的尾部this.data[this.tail] val;// tail向后移动this.tail (this.tail 1) % capacity;// 更新size的值this.size 1;}private void resize(int newCapacity) {T[] newData (T[]) new Object[newCapacity 1];// 迁移数据 this.frontint cur this.front;int index 0;while (cur ! this.tail) {newData[index] this.data[cur];cur (cur 1) % this.capacity;}// 修改属性this.capacity newCapacity 1;this.data newData;this.front 0;this.tail this.size;}Overridepublic String toString() {StringBuilder sb new StringBuilder();int cur this.front;while (cur ! this.tail) {sb.append(this.data[cur]);if ((cur 1) % this.capacity ! this.tail) {sb.append(,);}cur (cur 1) % this.capacity;}sb.append([ this.front -- this.tail ]);return sb.toString();}//从队列中移除元素public T removeHead() {// 1、队列是否为空if (this.front this.tail) {return null;}T val this.data[this.front];this.front (this.front 1) % this.capacity;this.size--;// 缩容if (this.size this.capacity / 4 this.capacity / 2 1) {resize(this.capacity / 2);}return val;}public OptionalT getFront() {if (isEmpty()) {return Optional.empty();}return Optional.of(this.data[this.front]);}// 测试public static void main(String[] args) {CycleArrayInteger myArr new CycleArray(5);for (int i 1; i 15; i) {myArr.addTail(i 25);System.out.println(添加 myArr);if (i % 3 0) {int val myArr.removeHead();System.out.println(删除 Header是 val);}}}
