本地网站后台管理建设,wordpress导入文章,网站和微信订阅号优势,企业seo蜘蛛屯一#xff1a;栈
1.1 栈的概念
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO#xff08;Last In First Out#xff09;的原…一栈
1.1 栈的概念
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。
压栈push栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈pop栈的删除操作叫做出栈。出数据在栈顶。 栈这种结构在现实生活中也很常见
1.2 栈的使用
方法功能Stack()构造一个空的栈E push(E e)将e入栈并返回eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空
下面是这些方法的使用示例
public static void main(String[] args) {StackInteger s new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size()); // 获取栈中有效元素个数--- 4System.out.println(s.peek()); // 获取栈顶元素--- 4s.pop(); // 4出栈栈中剩余1 2 3栈顶元素为3System.out.println(s.pop()); // 3出栈栈中剩余1 2 栈顶元素为3if(s.empty()){System.out.println(栈空);}else{System.out.println(s.size());}}1.3栈的模拟实现 从上图中可以看到Stack继承了VectorVector和ArrayList类似都是动态的顺序表不同的是Vector是线程安全的。
public class MyStack {int[] array; // 数组用于存储栈元素int size; // 记录栈中元素的个数// 构造方法创建一个初始容量为3的数组作为栈的存储空间public MyStack(){array new int[3];}// 入栈操作将元素 e 加入到栈顶并返回入栈的元素public int push(int e){ensureCapacity();// 确保栈的容量足够array[size] e;// 将元素 e 加入到数组中更新 size 的值return e;// 返回入栈的元素}// 出栈操作将栈顶元素移出并返回该元素public int pop(){int e peek(); // 调用 peek 方法获取栈顶元素并记录在变量 e 中size--; // 栈中元素个数减少1return e;// 返回出栈的元素}// 返回栈顶元素的值但不删除栈顶元素public int peek(){if(empty()){ // 如果栈为空则抛出异常throw new RuntimeException(栈为空无法获取栈顶元素);}return array[size-1];// 返回栈顶元素的值}// 返回栈中元素的个数public int size(){return size;}// 判断栈是否为空public boolean empty(){return 0 size;}// 确保栈的容量足够如果栈已满则将栈的容量扩大为原来的2倍private void ensureCapacity(){if(size array.length){array Arrays.copyOf(array, size*2);}}
}
二队列
2.1 队列的概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(FirstIn First Out) 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一端称为队头Head/Front 2.2 队列的使用
在Java中Queue是个接口底层是通过链表实现的。 下面是队列中常用的方法
方法功能boolean offer(E e)入队列E poll()出队列peek()获取队头元素int size()获取队列中有效元素个数boolean isEmpty()检测队列是否为空
注意
Queue是个接口在实例化时必须实例化LinkedList的对象因为LinkedList实现了Queue接口。
下面是这些方法的使用示例
public static void main(String[] args) {QueueInteger q new LinkedList();// 从队尾入队列q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); System.out.println(q.size());// 获取队头元素System.out.println(q.peek()); q.poll();System.out.println(q.poll()); // 从队头出队列并将删除的元素返回if(q.isEmpty()){System.out.println(队列空);}else{System.out.println(q.size());}
}2.3队列的模拟实现
队列中既然可以存储元素那底层肯定要有能够保存元素的空间通过前面线性表的学习了解到常见的空间类型有两种顺序结构 和 链式结构。所以队列的实现也可以采用这两种方式但是具体采用哪种实现方式取决于具体的需求和场景。 顺序结构使用数组或列表等连续的内存空间来存储队列元素。顺序结构实现队列的优点是简单、易于理解和实现并且访问元素的时间复杂度为 O(1)。缺点是在插入和删除操作时可能需要进行元素的搬移这会造成时间复杂度为 O(n)。 链式结构使用链表的形式来存储队列元素。链式结构实现队列的优点是插入和删除操作的时间复杂度为 O(1)无需进行元素的搬移。缺点是需要额外的指针来维护节点之间的连接且节点的分配和释放可能会引起额外的内存开销和碎片问题。
所以说如果你以访问为主那么采用顺序结构如果你以插入和删除为主那么采用链式结构 2.3.1顺序结构实现队列
因为我以及在代码中通过注释进行了详细的解答在此就不过多赘述了。
public class Queue {private int capacity; // 队列的容量private int[] elements; // 存储队列元素的数组private int front; // 队列的头指针private int rear; // 队列的尾指针private int size; // 队列的当前大小// 队列的构造方法public Queue(int capacity) {this.capacity capacity;this.elements new int[capacity];this.front 0;this.rear -1;this.size 0;}// 入队列---向队尾插入新元素public void offer(int element) {// 检查队列是否已满if (size capacity) {throw new IllegalStateException(Queue is full);}// 队尾指针移动到下一个位置rear (rear 1) % capacity;// 将新元素插入队尾elements[rear] element;// 队列大小加1size;}// 出队列---将队头元素删除并返回public int poll() {// 检查队列是否为空if (isEmpty()) {throw new IllegalStateException(Queue is empty);}// 获取队头元素int element elements[front];// 队头指针移动到下一个位置front (front 1) % capacity;// 队列大小减1size--;// 返回队头元素return element;}// 获取队头元素---返回队头元素的值但不删除public int peek() {// 检查队列是否为空if (isEmpty()) {throw new IllegalStateException(Queue is empty);}// 返回队头元素return elements[front];}// 返回队列的大小public int size() {return size;}// 判断队列是否为空public boolean isEmpty() {return size 0;}
}
2.3.2链式结构实现队列
public class Queue {// 双向链表节点public static class ListNode{ListNode next;ListNode prev;int value;// 双向链表节点的构造方法ListNode(int value){this.value value;}}ListNode first; // 队头ListNode last; // 队尾int size 0;// 入队列---向双向链表尾部插入新节点public void offer(int e){ListNode newNode new ListNode(e);if (first null) {// 如果队列为空新节点同时成为队头和队尾first newNode;} else {// 如果队列不为空将新节点插入到队尾last.next newNode;newNode.prev last;}// 更新队尾为新节点last newNode;// 队列大小加1size;}// 出队列---将双向链表第一个节点删除public int poll(){// 队列为空返回nullif (first null) {return null;} else if (first last) {// 队列中只有一个元素将队头和队尾设置为null即可last null;first null;} else {// 队列中有多个元素将第一个节点删除int value first.value;first first.next;// 删除节点的引用关系避免内存泄漏first.prev.next null;first.prev null;return value;}// 队列大小减1--size;// 返回删除的值return value;}// 获取队头元素---获取双向链表的第一个节点的值public int peek(){// 如果队列为空返回nullif (first null) {return null;}// 返回队头的值return first.value;}// 返回队列的大小public int size() {return size;}// 判断队列是否为空public boolean isEmpty(){return first null;}
}
2.4 循环队列
2.4.1索引公式
循环队列的视图如下 我们该如何去实现一个循环队列呢答案是通过 %取模
举个例子
int a b % 7在这个例子中我们不管b取何值a的取值返回是不是始终在0到6之间所以我们通过这个性质就可以很好的把队列的首和尾建立关联即尾向后走一步就到了头因此我们就可以很好的去实现一个循环队列了
在循环队列中(index offset) % array.length 和 (index array.length - offset) % array.length 是我们常用的索引计算方式。其中 index 是当前元素的索引。offset 是偏移量它决定了要添加/访问的元素在当前索引的基础上偏移了多少个位置。array.length 是数组的长度它表示整个循环队列的大小。
下面我们对这两个公式进行解释
(index offset) % array.length 当我们需要向循环队列的下一个位置插入元素时我们使用这种索引计算方式。假设队列在索引5处结束我们需要向后移动1个位置即在索引7处插入元素。使用 (5 1) % 8得到的值是6即有效的索引。 (index array.length - offset) % array.length 当我们需要从循环队列的上一个位置移除元素时我们使用这种索引计算方式。假设队列在索引2处结束我们需要向前移动1个位置即从索引1处移除元素。使用 (2 8 - 1) % 8得到的值是1即有效的索引。 这两种计算方式都确保了索引在循环队列中的有效范围内因为它们会通过取模运算将索引限制在数组长度范围内。这样我们可以在循环队列中正确地插入和移除元素。
2.4.2 队列区分空和满
当我们使用一个固定大小的数组作为队列的底层数据结构。在循环队列中我们使用两个指针一个指向队列的头部即出队列的位置另一个指向队列的尾部即入队列的位置。
当队列为空时这两个指针指向同一个位置即头部与尾部指针相等。而当队列满时尾部指针的下一个位置就是头部指针所在的位置。
那么我们该怎么区分队列是空还是满呢
为了区分队列是空还是满我们可以采用三种常用的方法
使用 size 属性记录:
通过添加一个 size 属性来记录队列中的元素数量可以方便地判断队列是空还是满。当队列为空时size 的值为 0当队列满时size 的值等于队列的容量。
保留一个位置:
在循环队列的实现中可以将一个位置始终空置不用用于区分队列是空还是满。例如当队列为空时头部指针和尾部指针都指向同一个位置当队列满时尾部指针的下一个位置就是头部指针所在的位置。通过查看这个空置位置是否为空可以判断队列是空还是满。
使用标记:
可以在循环队列中使用一个额外的标记来区分队列是空还是满。这个标记可以是一个布尔值或者一个特殊的值用于表示队列的状态。例如当队列为空时可以将标记设置为 true当队列满时可以将标记设置为 false。通过判断标记的值可以确定队列的状态。
这些方法都可以用于区分队列是空还是满具体选择哪种方法取决于个人偏好和实际需求。
2.5 Deque双端队列
双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队也可以从队尾出队和入队。 Deque是一个接口使用时必须创建LinkedList的对象。 在实际工程中使用Deque接口是比较多的栈和队列均可以使用该接口。
DequeInteger stack new ArrayDeque();//双端队列的线性实现
DequeInteger queue new LinkedList();//双端队列的链式实现
