【数据结构】栈和队列
2023-06-13 09:18:39 时间
✿1.栈(Stack)
✿1.1概念
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出 LIFO(Last In First Out)的原则。 333后进,最先出去。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。 出栈:栈的删除操作叫做出栈。出数据在栈顶。
✿1.2栈的使用
✿1.3栈的模拟实现
顺序栈:(数组实现的栈)
import java.util.Arrays;
public class MyStack {
public int[] elem;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public MyStack(){
this.elem = new int[DEFAULT_SIZE];
}
public int push(int val){
if(isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
this.elem[usedSize] = val;
usedSize++;
return val;
}
public boolean isFull(){
if(usedSize == elem.length){
return true;
}
return false;
}
public int pop(){
if(isEmpty()){
throw new IsEmptyExpection("栈为空!");
}
int ret = elem[usedSize-1];
usedSize--;
return ret;
}
public boolean isEmpty(){
return usedSize == 0;
}
public int peek(){
if(isEmpty()){
throw new IsEmptyExpection("栈为空!");
}
return elem[usedSize-1];
}
public static void main(String[] args) {
MyStack myStack = new MyStack();
myStack.push(11);
myStack.push(22);
myStack.push(33);
myStack.push(44);
System.out.println(myStack.peek());
System.out.println(myStack.pop());
System.out.println(myStack.peek());
}
}
栈的实现可以有多种方式,比如顺序栈,链式栈。双向链表实现的链式栈可以实现多种方向的先进后出。较为方便。
✿1.4概念区分
栈,虚拟机栈,栈帧有什么区别? 栈:是一种先进后出的数据结构。 虚拟机栈:是JVM的一块内存空间。 栈帧:是在调用函数的过程中,在Java虚拟机栈上开辟的一块内存。
✿2.队列(Queue)
✿2.1概念
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(FirstIn First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头(Head/Front)
✿2.2队列的使用
在Java中,Queue是个接口,底层是通过链表实现的。
注意:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。(接口不能被实例化!)
✿2.3队列模拟实现
public class MyQueue {
static class ListNode{
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode tail;
public int usedSize;
public void offer(int val){
//尾插法
ListNode node = new ListNode(val);
if(head == null){
head = node;
tail = node;
}else {
tail.next = node;
tail = tail.next;
}
usedSize ++;
}
public int poll(){
//头删法
if(isEmpty()){
throw new IsEmptyExpection("队列为空!");
}
int ret = head.val;
head = head.next;
if(head == null){
tail = null;
}
usedSize--;
return ret;
}
public boolean isEmpty(){
return usedSize == 0;
}
public int peek(){
if(isEmpty()){
throw new IsEmptyExpection("队列为空!");
}
return head.val;
}
public int getUsedSize(){
return usedSize;
}
public static void main(String[] args) {
MyQueue myQueue = new MyQueue();
myQueue.offer(11);
myQueue.offer(22);
myQueue.offer(33);
myQueue.offer(44);
System.out.println(myQueue.peek());
System.out.println(myQueue.poll());
System.out.println(myQueue.peek());
System.out.println(myQueue.getUsedSize());
}
}
✿2.4循环队列
实际中我们有时还会使用一种队列叫循环队列。环形队列通常使用数组实现。
public class MyCirleQueue {
public int[] elem;
public int front;//队头
public int rear;//队尾
public MyCirleQueue(int k){
this.elem = new int[k];
}
public boolean enQueue(int val){
if(isFull()){
return false;
}
elem[rear] = val;
rear = (rear+1) % elem.length;
return true;
}
public boolean isFull(){
return (rear+1) % elem.length == front;
}
public boolean deQueue(){
if(isEmpty()){
throw new IsEmptyExpection("队列为空!");
}
front = (front+1) % elem.length;
return true;
}
public boolean isEmpty(){
return front == rear;
}
public int Front(){
if(isEmpty()){
throw new IsEmptyExpection("队列为空!");
}
return elem[front];
}
public int Rear(){
if(isEmpty()){
throw new IsEmptyExpection("队列为空!");
}
int index = rear == 0 ? elem.length-1 : rear-1;
return elem[index];
}
}
✿3.双端队列(Deque)
双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。 Deque是一个接口,使用时必须创建LinkedList的对象。
相关文章
- 数据结构与算法 队列_数据结构中的排序算法
- C++数据结构——队列「建议收藏」
- 最详解消息队列以及RabbbitMQ之HelloWorld
- 数据结构–循环队列[通俗易懂]
- 数据结构篇——栈和队列
- 学完数据结构,队列到底有什么用?
- 优先队列的数据结构_低优先级队列一天只能一场
- Go 数据结构和算法篇(三):队列
- 消息队列:第五章:RabbitMQ的使用
- 【数据结构初阶】一文详解顺序栈和链队列的基本操作
- 数据结构实验之栈与队列三:后缀式求值(SDUT 2133)
- 数据结构实验之栈与队列六:下一较大值(二)(SDUT 3333)
- 【Linux 内核】实时调度类 ⑥ ( 实时调度类核心函数源码分析 | 插入进程到执行队列 | 从执行队列中选择优先级最高的进程 )
- 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(下)
- 【数据结构】优先级队列(堆)
- 【数据结构】之队列的java实现(二)详解编程语言
- 【数据结构】之队列的java实现(一)详解编程语言
- 秒杀抢购,极速反应:Redis队列助力(redis秒杀队列)
- Redis队列调控订单库存,实现效率管理(订单库存redis队列)
- Redis队列快速传递,数据瞬间更新(redis 队列速度)
- 基于PHP的Redis队列监控实践(redis队列监控php)
- Redis非阻塞队列加速异步任务调度(redis队列异步非阻塞)
- 机制基于Redis锁的队列机制实现(redis锁的队列)
- 使用Redis实现阻塞队列(redis自带阻塞队列)
- python异步任务队列示例