湖南东方红建设集团有限公司网站淮安网站设计

湖南东方红建设集团有限公司网站,淮安网站设计,wordpress 自动加版权,福建省教师空间建设网站本篇来讲解栈与队列~模块一#xff1a;栈#xff08;Stack#xff09;1. 基础知识栈是一种后进先出#xff08;LIFO#xff09; 的数据结构#xff0c;只允许在一端#xff08;称为栈顶#xff09;进行插入和删除操作。核心操作包括#xff1a;压栈#xff08;Push栈Stack1. 基础知识栈是一种后进先出LIFO的数据结构只允许在一端称为栈顶进行插入和删除操作。核心操作包括压栈Push向栈顶添加元素。弹栈Pop从栈顶移除元素。查看栈顶Peek获取栈顶元素但不移除。判空isEmpty检查栈是否为空。容量Size获取栈中元素数量。2. 数组实现栈使用数组实现栈时需维护一个指向栈顶的指针通常用top表示。数组大小固定需处理栈满的情况。代码实现public class ArrayStack { private int maxSize; // 栈的最大容量 private int[] stack; // 存储元素的数组 private int top; // 栈顶指针初始为-1 public ArrayStack(int size) { maxSize size; stack new int[maxSize]; top -1; } // 压栈 public void push(int value) { if (isFull()) { throw new RuntimeException(栈已满); } stack[top] value; } // 弹栈 public int pop() { if (isEmpty()) { throw new RuntimeException(栈为空); } return stack[top--]; } // 查看栈顶 public int peek() { if (isEmpty()) { throw new RuntimeException(栈为空); } return stack[top]; } // 判空 public boolean isEmpty() { return top -1; } // 判满 public boolean isFull() { return top maxSize - 1; } // 获取栈中元素数量 public int size() { return top 1; } }3. 双链表实现栈双链表双向链表每个节点包含前驱和后继指针实现栈时可灵活地在头部插入和删除节点时间复杂度为O(1)。代码实现public class LinkedListStack { private static class Node { int value; Node prev; Node next; Node(int value) { this.value value; } } private Node top; // 栈顶节点 private int size; // 栈中元素数量 public LinkedListStack() { top null; size 0; } // 压栈在链表头部插入 public void push(int value) { Node newNode new Node(value); if (top ! null) { newNode.next top; top.prev newNode; } top newNode; size; } // 弹栈移除链表头部节点 public int pop() { if (isEmpty()) { throw new RuntimeException(栈为空); } int value top.value; top top.next; if (top ! null) { top.prev null; } size--; return value; } // 查看栈顶 public int peek() { if (isEmpty()) { throw new RuntimeException(栈为空); } return top.value; } // 判空 public boolean isEmpty() { return size 0; } // 获取栈中元素数量 public int size() { return size; } }模块二队列Queue1. 基础知识队列是一种先进先出FIFO的数据结构元素从一端队尾插入从另一端队首删除。核心操作包括入队Enqueue向队尾添加元素。出队Dequeue从队首移除元素。查看队首Peek获取队首元素但不移除。判空isEmpty检查队列是否为空。容量Size获取队列中元素数量。队列的典型应用场景包括任务调度如线程池、消息队列、广度优先搜索BFS等。2. 数组实现队列循环队列数组实现队列时需解决假溢出问题即数组前部有空间但尾部已满。通过循环数组head和tail指针循环移动可高效利用空间。代码实现public class CircularQueue { private int maxSize; // 队列最大容量 private int[] queue; // 存储元素的数组 private int head; // 队首指针指向待出队元素 private int tail; // 队尾指针指向待插入位置 public CircularQueue(int size) { maxSize size 1; // 预留一个空位以区分队满和队空 queue new int[maxSize]; head 0; tail 0; } // 入队 public void enqueue(int value) { if (isFull()) { throw new RuntimeException(队列已满); } queue[tail] value; tail (tail 1) % maxSize; // 循环移动 } // 出队 public int dequeue() { if (isEmpty()) { throw new RuntimeException(队列为空); } int value queue[head]; head (head 1) % maxSize; // 循环移动 return value; } // 查看队首 public int peek() { if (isEmpty()) { throw new RuntimeException(队列为空); } return queue[head]; } // 判空head tail public boolean isEmpty() { return head tail; } // 判满(tail 1) % maxSize head public boolean isFull() { return (tail 1) % maxSize head; } // 获取队列中元素数量 public int size() { return (tail - head maxSize) % maxSize; } }3. 双链表实现队列双链表实现队列时在链表尾部插入节点入队在头部删除节点出队时间复杂度均为O(1)。代码实现public class LinkedListQueue { private static class Node { int value; Node prev; Node next; Node(int value) { this.value value; } } private Node head; // 队首节点 private Node tail; // 队尾节点 private int size; // 队列中元素数量 public LinkedListQueue() { head null; tail null; size 0; } // 入队在链表尾部插入 public void enqueue(int value) { Node newNode new Node(value); if (tail null) { head newNode; tail newNode; } else { tail.next newNode; newNode.prev tail; tail newNode; } size; } // 出队移除链表头部节点 public int dequeue() { if (isEmpty()) { throw new RuntimeException(队列为空); } int value head.value; head head.next; if (head ! null) { head.prev null; } else { tail null; // 队列已空 } size--; return value; } // 查看队首 public int peek() { if (isEmpty()) { throw new RuntimeException(队列为空); } return head.value; } // 判空 public boolean isEmpty() { return size 0; } // 获取队列中元素数量 public int size() { return size; } }总结对比实现方式栈时间复杂度队列时间复杂度特点数组所有操作O(1)所有操作O(1)需处理容量限制内存连续双链表所有操作O(1)所有操作O(1)动态扩容内存非连续栈优先使用java.util.Stack或java.util.Deque如ArrayDeque。队列优先使用java.util.Queue的实现类如LinkedList、ArrayDeque。不过都可以使用LinkedList。