【数据结构】栈和队列的深度探索,从实现到应用详解

简介: 本文介绍了栈和队列这两种数据结构。栈是一种后进先出(LIFO)的数据结构,元素只能从栈顶进行插入和删除。栈的基本操作包括压栈、出栈、获取栈顶元素、判断是否为空及获取栈的大小。栈可以通过数组或链表实现,并可用于将递归转化为循环。队列则是一种先进先出(FIFO)的数据结构,元素只能从队尾插入,从队首移除。队列的基本操作包括入队、出队、获取队首元素、判断是否为空及获取队列大小。队列可通过双向链表或数组实现。此外,双端队列(Deque)支持两端插入和删除元素,提供了更丰富的操作。

🍁1. 栈的介绍

栈是一种后进先出的数据结构,栈中的元素只能从栈顶进行插入和删除操作,类似于叠盘子,最后放上去的盘子最先拿下来。

🍁2. 栈的基本操作

  • 压栈(Push):将一个元素压入栈顶。
  • 出栈(Pop):移除并返回栈顶元素。
  • 栈顶元素(Peek):返回栈顶元素但不移除。
  • 判空(IsEmpty):检查栈是否为空。
  • 栈的大小(Size):返回栈中的元素个数。

栈的定义方法也是和ArrayList一样的,然后就是使用对象去调用栈的方法

public class Text {
    public static void main(String[] args) {
        Stack<Integer> stack1 = new Stack<>();
        stack1.push(1);
        stack1.push(2);
        stack1.push(3);
        System.out.println(stack1.pop());
        System.out.println(stack1.peek());
        System.out.println(stack1.isEmpty());
        System.out.println(stack1.size());
    }
}

🍁3. 栈的实现

首先,栈是通过数组实现的,就像之前实现的顺序表一样

public class MyStack {
    public int[] elem;
    public int usedSize;
    public MyStack() {
        this.elem = new int[10];
    }
}

接下来实现一些栈的基本操作

🍁3.1 push()

当1 2 3 4依次入栈时,如下图

入栈其实很简单,只需要把元素放进去,接着usedSize++就可以了,但是学习数据结构我们的思维要严谨,如果栈满了怎么办,所以还需要处理栈满的情况,栈满之后就扩容,扩容也是和之前的顺序表一样的,判断是否栈满了也很简单,只需要判断数组的长度和usedSize是否相等就可以了

public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
   }
   public boolean isFull() {
        return usedSize == elem.length;
   }

🍁3.2 pop()

遵循后进先出的原则,第一次出栈取到的元素是4

那怎么去实现这个效果呢

只需要定义一个val,把栈顶的元素取出来,赋值给val,进行返回,同时出栈之后usedSize的值要减1

之后还需要考虑栈为空的情况,如果栈为空,肯定是不能再进行出栈的操作了,此时就需要抛出一个异常

public int pop() {
        if(isEmpty()){
            throw new EmptyStackException();
        }
        int val = elem[usedSize - 1];
        usedSize--;
        return val;
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }

判断栈为空只需要判断usedSize是否为空

🍁3.3 peek()

peek()是获取栈顶元素,但是不删除,这个其实更简单,只需要把下标为usedSize的元素进行返回就可以了,也不需要usedSize--

同时,还是需要处理一下栈为空的情况

public int peek() {
        if(usedSize == 0){
            throw new EmptyStackException();
        }
        return elem[usedSize - 1];
    }

接下来把之前写的方法测试一下:

public class Text {
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.print(stack.pop() + " ");
        System.out.print(stack.pop() + " ");
        System.out.print(stack.peek() + " ");
    }
}

🍁4. 栈的使用场景

🍁4.1 链表实现栈

问题:单链表是否可以实现栈?

单链表其实是可以实现栈的,用链表实现的栈叫做链式栈

入栈:如果采用尾插法入栈,入栈的时间复杂度为O(n),如果给出last节点为O(1),出栈的时间复杂度为O(n),因为需要遍历到末尾才能入栈

如果采用头插法,入栈和出栈的时间复杂度都是O(1)

既然单链表可以实现栈了,那么双向链表肯定也可以实现栈,不论是头插还是尾插,双链表实现的栈出栈和入栈时间复杂度都是O(1)。

而且会发现,LinkedList也定义了栈的一些基本操作,可以当作栈来使用

🍁4.2 将递归转化为循环

一个典型的例子就是逆序打印链表,我们都知道,正常情况下,单链表是不能逆序打印的,递归的调用就类似于栈,最外面的一层先被打印,也就是最末尾元素最先打印,还可以通过栈来模拟递归

//递归方式
    private void printList1(MySingleList.ListNode head){
        if(head!=null){
            printList1(head.next);
            System.out.print(head.value + " ");
        }
    }
    //循环方式
    private void printList2(MySingleList.ListNode head){
        if(head == null) return;
        Stack<MySingleList.ListNode> s = new Stack<>();
        MySingleList.ListNode cur = head;
        //将节点保存在栈中
        while(cur!=null){
            s.push(cur);
            cur = cur.next;
        }
        //打印栈中节点
        while(!s.empty()){
            System.out.print(s.pop().value + " ");
        }
    }

🍁5. 队列的介绍

队列是一种先进先出的数据结构。队列中的元素只能从队尾插入,从队首移除,类似于排队买票,最先排队的人最先买到票。

Java中的Queue是一个接口,Deque叫做双端队列

🍁6. 队列的基本操作


  1. 入队(offer):将一个元素插入队尾。
  2. 出队(poll):移除并返回队首元素。
  3. 队首元素(Peek):返回队首元素但不移除。
  4. 判空(IsEmpty):检查队列是否为空。
  5. 队列的大小(Size):返回队列中的元素个数。

由于Queue是一个接口,不能直接创建对象,所以这里通过LinkedList来创建对象

public class Text {
    public static void main(String[] args) {
        //使用接口的实现类LinkedList创建对象
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        //出队
        System.out.println(q.poll());
        //获取对头元素
        System.out.println(q.peek());
    }
}

🍁7. 队列的实现

🍁7.1 双向链表实现队列

双向链表的话,和栈一样,入队和出队的操作时间复杂度为O(n),因为队列是先进先出的原则,入队就采用尾插的方法,出队也就是头删的方法

public class MyQueue {
    //双向链表
    static class ListNode {
        public int val;
        ListNode pre;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    ListNode first = null;
    ListNode last = null;
    public int usedSize = 0;
    //尾插的方法进行入队
    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (isEmpty()) {
            first = last = node;
        } else {
            last.next = node;
            node.pre = last;
            last = last.next;
        }
        usedSize++;
    }
    //头删的方法进行出队
    public int poll() {
        if (first == null) {
            throw new EmptyQueueException("队列为空");
        }
        int value = first.val;
        first = first.next;
        if(first!=null){
            first.pre = null;
        }
        usedSize--;
        return value;
    }
    //获取队头元素
    public int peek() {
        if (first == null) {
            throw new EmptyQueueException("队列为空");
        }
        return first.val;
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }
}

🍁7.2 数组实现的循环队列

如果采用正常的数组来实现队列的话就会有以下的弊端,

这样出队之后,数组前面的空间就会空出来,造成空间的浪费,那如何把这些空间也利用起来呢

使用这样的循环结构,就可以解决这个问题,也就是循环队列

front和rear在同一个位置时,表示队列为空,那么队列满了也是这样的情况,此时怎么区分呢?

1.定义一个size专门判断

2.添加标记,定义一个boolean类型的flag,表示走过没有

3.空出一个空间,此时rear.next == front就表示队列已满

此时还有一个问题:对于以上的例子,怎么解决下标的问题,例如从7下标是怎么到0下标的

也就是下标最后再往后怎么表示:

公式:(数组下标 - 偏移量) % 数组长度

7 ~ 0  可以通过 (7 + 1)% 8 来表示

还有一种情况:下标最前再往前

例如 2 下标往前走到 7 下标

公式:(数组下标 + 数组长度 - 偏移量) % 数组长度

(2 + 9 - 4)% 9,加上数组长度也就是为了避免负数的情况

622. 设计循环队列

我们通过力扣上的这道题来实现一下:

class MyCircularQueue {
    public int front;
    public int rear;
    public int[] elem;
    public MyCircularQueue(int k) {
        elem = new int[k + 1];//由于有一个位置空出来了,所以要额外再多一个位置
    }
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear + 1) % elem.length;
        return true;
    }
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % elem.length;
        return true;
    }
    public int Front() {
        if (isEmpty()) {
            return -1;
        } else {
            return elem[front];
        }
    }
    public int Rear() {
        if (isEmpty())
            return -1;
        int index = (rear == 0 )? elem.length - 1 : rear - 1;
        return elem[index];
    }
    public boolean isEmpty() {
        return rear == front;
    }
    public boolean isFull() {
        return (rear + 1) % elem.length == front;
    }
}

🍁8. 双端队列

在Java中,Deque(双端队列)是一个接口,它扩展了Queue接口。Deque支持在两端插入和删除元素,提供了比Queue更丰富的操作集合。可以使用Deque作为栈(后进先出)、队列(先进先出)、或者两者兼有。

Java提供了几种Deque的实现,其中最常见的是ArrayDequeLinkedListArrayDeque是基于数组的双端队列,它在大多数操作中都提供了更好的性能。而LinkedList也实现了Deque接口,但由于其基于链表的结构,它在添加和删除元素时可能不如ArrayDeque高效。

public class DequeDemo {
    public static void main(String[] args) {
        //线性实现
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(1);
        deque.add(2);
        deque.add(3);
        for(int i : deque){
            System.out.println(i);
        }
        //链式实现
        Deque<Integer> ldeque = new LinkedList<>();
        ldeque.add(1);
        ldeque.add(1);
        ldeque.add(1);
        for(int i : ldeque){
            System.out.println(i);
        }
    }
}
相关文章
|
5天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
|
6天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
06_用栈来求解汉诺塔问题
06_用栈来求解汉诺塔问题
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
03_如何仅用递归函数和栈操作逆序一个栈
03_如何仅用递归函数和栈操作逆序一个栈
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
6天前
|
测试技术
02_由两个栈组成的队列
02_由两个栈组成的队列
|
9天前
|
存储
|
24天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
26天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表,常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈,顺序栈使用数组存储,链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛,如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成,链栈则基于单链表的头插法实现。
151 3