AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构与算法（三）：栈与队列

2023-05-16 87
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 上一篇《 数据结构与算法（二）：线性表》中介绍了数据结构中线性表的两种不同实现——顺序表与链表。这一篇主要介绍线性表中比较特殊的两种数据结构——栈与队列。首先必须明确一点，栈和队列都是线性表，它们中的元素都具有线性关系，即前驱后继关系。

一、栈

1、基本概念

栈（也称下压栈，堆栈）是仅允许在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）。栈是一种后进先出（Last In First Out）的线性表，简称（LIFO)结构。栈的一个典型应用是在集合中保存元素的同时颠倒元素的相对顺序。


抽象数据类型：


栈同线性表一样，一般包括插入、删除等基本操作。其基于泛型的API接口代码如下：

public interface Stack<E> {
    //栈是否为空
    boolean isEmpty();
    //栈的大小
    int size();
    //入栈
    void push(E element);
    //出栈
    E pop();
    //返回栈顶元素
    E peek();
}

栈的实现通常有两种方式：

  • 基于数组的实现（顺序存储）
  • 基于链表的实现（链式存储）

2、栈的顺序存储结构

栈的顺序存储结构其实是线性表顺序存储结构的简化，我们可以简称它为「顺序栈」。其存储结构如下图：

22.png实现代码如下：

import java.util.Iterator;
/**
 * 能动态调整数组大小的栈
 */
public class ArrayStack<E> implements Iterable<E>, Stack<E> {
    private E[] elements;
    private int size=0;
    @SuppressWarnings("unchecked")
    public ArrayStack() {
        elements = (E[])new Object[1]; //注意：java不允许创建泛型数组
    }
    @Override public int size() {return size;}
    @Override public boolean isEmpty() {return size == 0;}
    //返回栈顶元素
    @Override public E peek() {return elements[size-1];}
    //调整数组大小
    public void resizingArray(int num) {
        @SuppressWarnings("unchecked")
        E[] temp = (E[])new Object[num];
        for(int i=0;i<size;i++) {
            temp[i] = elements[i];
        }
        elements = temp;
    }
    //入栈
    @Override public void push(E element) {
        if(size == elements.length) {
            resizingArray(2*size);//若数组已满将长度加倍
        }
        elements[size++] = element;
    }
    //出栈
    @Override public E pop() {
        E element = elements[--size];
        elements[size] = null;     //注意：避免对象游离
        if(size > 0 && size == elements.length/4) {
            resizingArray(elements.length/2);//小于数组1/4,将数组减半
        }
        return element;
    }
    //实现迭代器, Iterable接口在java.lang中，但Iterator在java.util中
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private int num = size;
            public boolean hasNext() {
                return num > 0;
            }
            public E next() {
                return elements[--num];
            }
        };
    }
    //测试
    public static void main(String[] args) {
        int[] a = {1,2,3,4,new Integer(5),6};//测试数组
        ArrayStack<Integer> stack = new ArrayStack<Integer>();
        System.out.print("入栈顺序：");
        for(int i=0;i<a.length;i++) {
            System.out.print(a[i]+" ");
            stack.push(a[i]);
        }
        System.out.println();
        System.out.print("出栈顺序数组实现：");
        //迭代
        for (Integer s : stack) {
            System.out.print(s+" ");
        }
    }
}

优点：

  • 每项操作的用时都与集合大小无关
  • 空间需求总是不超过集合大小乘以一个常数

缺点：

  • push()和pop()操作有时会调整数组大小，这项操作的耗时和栈的大小成正比


3、两栈共享空间

用一个数组来存储两个栈，让一个栈的栈底为数组的始端，即下标为0，另一个栈的栈底为数组的末端，即下标为 n-1。两个栈若增加元素，栈顶都向中间延伸。其结构如下：


23.png


这种结构适合两个栈有相同的数据类型并且空间需求具有相反的关系的情况，即一个栈增长时另一个栈缩短。如，买股票，有人买入，就一定有人卖出。

代码：

public class SqDoubleStack<E> {
    private static final int MAXSIZE = 20;
    private E[] elements;
    private int leftSize=0;
    private int rightSize= MAXSIZE - 1;
    //标记是哪个栈
    enum EnumStack {LEFT, RIGHT}
    @SuppressWarnings("unchecked")
    public SqDoubleStack() {
        elements = (E[])new Object[MAXSIZE]; //注意：java不允许创建泛型数组
    }
    //入栈
    public void push(E element, EnumStack es) {
        if(leftSize - 1 == rightSize)
            throw new RuntimeException("栈已满，无法添加"); 
        if(es == EnumStack.LEFT) {
            elements[leftSize++] = element;
        } else {
            elements[rightSize--] = element;
        }
    }
    //出栈
    public E pop(EnumStack es ) {
        if(es == EnumStack.LEFT) {
            if(leftSize <= 0)
                throw new RuntimeException("栈为空，无法删除"); 
            E element = elements[--leftSize];
            elements[leftSize] = null;     //注意：避免对象游离
            return element;
        } else {
            if(rightSize >= MAXSIZE - 1)
                throw new RuntimeException("栈为空，无法删除"); 
            E element = elements[++rightSize];
            elements[rightSize] = null;     //注意：避免对象游离
            return element;
        }
    }
    //测试
    public static void main(String[] args) {
        int[] a = {1,2,3,4,new Integer(5),6};//测试数组
        SqDoubleStack<Integer> stack = new SqDoubleStack<Integer>();
        System.out.print("入栈顺序：");
        for(int i=0;i<a.length;i++) {
            System.out.print(a[i]+" ");
            stack.push(a[i], EnumStack.RIGHT);
        }
        System.out.println();
        System.out.print("出栈顺序数组实现：");
        //迭代
        for(int i=0;i<a.length;i++) {
            System.out.print(stack.pop(EnumStack.RIGHT)+" ");
        }
    }
}

4、栈的链式存储结构

栈的链式存储结构，简称链栈。为了操作方便，一般将栈顶放在单链表的头部。通常对于链栈来说，不需要头结点。

其存储结构如下图：


24.png

代码实现如下：

import java.util.Iterator;
public class LinkedStack<E> implements Stack<E>, Iterable<E> {
    private int size = 0;
    private Node head = null;//栈顶
    private class Node {
        E element;
        Node next;
        Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }
    }
    @Override public int size() {return size;}
    @Override public boolean isEmpty() {return size == 0;}
    @Override public E peek() {return head.element;}
    @Override public void push(E element) {
        Node node = new Node(element, head);
        head = node;
        size++;
    }
    @Override public E pop() {
        E element = head.element;
        head = head.next;
        size--;
        return element;
    }
    //迭代器
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private Node current = head;
        public boolean hasNext() {
                return current != null;
            }
            public E next() {
                E element = current.element;
                current = current.next;
                return element;
            }
        };
    }
    public static void main(String[] args) {
        int[] a = {1,2,3,4,new Integer(5),6};//测试数组
        LinkedStack<Integer> stack = new LinkedStack<Integer>();
        System.out.print("入栈顺序：");
        for(int i=0;i<a.length;i++) {
            System.out.print(a[i]+" ");
            stack.push(a[i]);
        }
        System.out.println();
        System.out.print("出栈顺序链表实现：");
        for (Integer s : stack) {
            System.out.print(s+" ");
        }
    }
}

注意：私有嵌套类（内部类Node）的一个特点是只有包含他的类能够直接访问他的实例变量，无需将他的实例变量（element）声明为public或private。即使将变量element声明为private，外部类依然可以通过Node.element的形式调用。


优点：


所需空间和集合的大小成正比

操作时间和集合的大小无关

链栈的push和pop操作的时间复杂度都为 O(1)。

缺点：


每个元素都有指针域，增加了内存的开销。

顺序栈与链栈的选择和线性表一样，若栈的元素变化不可预料，有时很大，有时很小，那最好使用链栈。反之，若它的变化在可控范围内，使用顺序栈会好一些。


5、栈的应用——递归

栈的一个最重要的应用就是递归。那么什么是递归呢？借用《哥德尔、艾舍尔、巴赫——集异璧之大成》中的话：


递归从狭义上来讲，指的是计算机科学中（也就是像各位程序猿都熟悉的那样），一个模块的程序在其内部调用自身的技巧。如果我们把这个效果视觉化就成为了「德罗斯特效应」，即图片的一部分包涵了图片本身。


如下面这张图，「先有书还是先有封面 ？」


25.png


我们把一个直接调用自身或通过一系列语句间接调用自身的函数，称为递归函数。每个递归函数必须至少有一个结束条件，即不在引用自身而是返回值退出。否则程序将陷入无穷递归中。

一个递归的例子：斐波那契数列（Fibonacci）


26.png

递归实现：

public int fibonacci(int num) {
    if(num < 2)
        return num == 0 ? 0 : 1;
    return fibonacci(num - 1) + fibonacci(num - 2);
}

迭代实现：

public int fibonacci(int num) {
    if(num < 2)
        return num == 0 ? 0 : 1;
    int temp1 = 0;
    int temp2 = 1;
    int result = 0;
    for(int i=2; i < num; i++) {
        result = temp1 + temp2;
        temp1 = temp2;
        temp2 = result;
    }
    return result;
}

迭代与递归的区别：


迭代使用的是循环结构，递归使用的是选择结构。

递归能使程序的结构更清晰、简洁，更容易使人理解。但是大量的递归将消耗大量的内存和时间。

编译器使用栈来实现递归。在前行阶段，每一次递归，函数的局部变量、参数值及返回地址都被压入栈中；退回阶段，这些元素被弹出，以恢复调用的状态。


二、队列

1、基本概念

队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。它是一种基于先进先出（First In First Out，简称FIFO）策略的集合类型。允许插入的一端称为队尾，允许删除的一端称为队头。


抽象数据类型：


队列作为一种特殊的线性表，它一样包括插入、删除等基本操作。其基于泛型的API接口代码如下：

public interface Queue<E> {
    //队列是否为空
    boolean isEmpty();
    //队列的大小
    int size();
    //入队
    void enQueue(E element);
    //出队
    E deQueue();
}

同样的，队列具有两种存储方式：顺序存储和链式存储。

2、队列的顺序存储结构

其存储结构如下图：


27.png


与栈不同的是，队列元素的出列是在队头，即下表为0的位置。为保证队头不为空，每次出队后队列中的所有元素都得向前移动，此时时间复杂度为 O(n)。此时队列的实现和线性表的顺序存储结构完全相同，不在详述。


若不限制队列的元素必须存储在数组的前n个单元，出队的性能就能大大提高。但这种结构可能产生「假溢出」现象，即数组末尾元素已被占用，如果继续向后就会产生下标越界，而前面为空。如下图：


28.png


28.png

解决「假溢出」的办法就是若数组未满，但后面满了，就从头开始入队。我们把这种逻辑上首尾相连的顺序存储结构称为循环队列。

数组实现队列的过程：


30.png



假设开始时数组长度为5，如图，当f入队时，此时数组末尾元素已被占用，如果继续向后就会产生下标越界，但此时数组未满，将从头开始入队。当数组满（h入队）时，将数组的长度加倍。

代码如下：


import java.util.Iterator;
/**
 * 能动态调整数组大小的循环队列
 */
public class CycleArrayQueue<E> implements Queue<E>, Iterable<E> {
    private int size; //记录队列大小
    private int first; //first表示头元素的索引
    private int last; //last表示尾元素后一个的索引
    private E[] elements;
    @SuppressWarnings("unchecked")
    public CycleArrayQueue() {
        elements = (E[])new Object[1];
    }
    @Override public int size() {return size;}
    @Override public boolean isEmpty(){return size == 0;}
    //调整数组大小
    public void resizingArray(int num) {
        @SuppressWarnings("unchecked")
        E[] temp = (E[])new Object[num];
        for(int i=0; i<size; i++) {
            temp[i] = elements[(first+i) % elements.length];
        }
        elements = temp;
        first = 0;//数组调整后first，last位置
        last =  size;
    }
    @Override public void enQueue(E element){
        //当队列满时，数组长度加倍
        if(size == elements.length) 
            resizingArray(2*size);
        elements[last] = element;
        last = (last+1) % elements.length;//【关键】
        size++;
    }
    @Override public E deQueue() {
        if(isEmpty()) 
            return null;
        E element = elements[first];
        first = (first+1) % elements.length;//【关键】
        size--;
        //当队列长度小于数组1/4时，数组长度减半
        if(size > 0 && size < elements.length/4) 
            resizingArray(2*size);
        return element;
    }
    //实现迭代器
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private int num = size;
            private int current = first;
            public boolean hasNext() {
                return num > 0;
            }
            public E next() {
                E element = elements[current++];
                num--;
                return element;
            }                
        };
    }
    public static void main(String[] args) {
        int[] a = {1,2,4,6,new Integer(10),5};
        CycleArrayQueue<Integer> queue = new CycleArrayQueue<Integer>();
        for(int i=0;i<a.length;i++) {
            queue.enQueue(a[i]);
            System.out.print(a[i]+" ");
        }    
        System.out.println("入队");
        for (Integer s : queue) {
            System.out.print(s+" ");
        }
        System.out.println("出队");
    }
}

3、队列的链式存储结构

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们简称为「链队列」。

存储结构如下图：

32.png


代码如下：

import java.util.Iterator;
/**
 * 队列的链式存储结构，不带头结点的实现
 */
public class LinkedQueue<E> implements Queue<E>, Iterable<E> {
    private Node first; //头结点
    private Node last; //尾结点
    private int size = 0;
    private class Node {
        E element;
        Node next;
        Node(E element) {
            this.element = element;
        }
    }
    @Override public int size() {return size;}
    @Override public boolean isEmpty(){return size == 0;}
    //入队
    @Override public void enQueue(E element) {
        Node oldLast = last;
        last = new Node(element);
        if(isEmpty()) {
            first = last;//【要点】
        }else {
            oldLast.next = last;
        }
        size++;
    }
    //出队
    @Override public E deQueue() {
        E element = first.element;
        first = first.next;
        size--;
        if(isEmpty()) 
            last = null;//【要点】
        return element;
    }
    //实现迭代器
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private Node current = first;
            public boolean hasNext() {
                return current != null;
            }
            public E next(){
                E element = current.element;
                current = current.next;
                return element;
            }
        };
    }
    public static void main(String[] args) {
        int[] a = {1,2,4,6,new Integer(10),5};
        LinkedQueue<Integer> queue = new LinkedQueue<Integer>();
        for(int i=0;i<a.length;i++) {
            queue.enQueue(a[i]);
            System.out.print(a[i]+" ");
        }    
        System.out.println("入队");
        for (Integer s : queue) {
            System.out.print(s+" ");
        }
        System.out.println("出队");
    }
}

循环队列与链队列，它们的基本操作的时间复杂度都为 O(1)。和线性表相同，在可以确定队列长度的情况下，建议使用循环队列；无法确定队列长度时使用链队列。


三、总结

栈与队列，它们都是特殊的线性表，只是对插入和删除操作做了限制。栈限定仅能在栈顶进行插入和删除操作，而队列限定只能在队尾插入，在队头删除。它们都可以使用顺序存储结构和链式存储结构两种方式来实现。


对于栈来说，若两个栈数据类型相同，空间需求相反，则可以使用共享数组空间的方法来实现，以提高空间利用率。对于队列来说，为避免插入删除操作时数据的移动，同时避免「假溢出」现象，引入了循环队列，使得队列的基本操作的时间复杂度降为 O(1)。


文章标签：
程序员
API
算法
存储
编译器
关键词：
数据结构栈队列
数据结构栈
数据结构队列
算法队列
数据结构与算法队列
鹤冲天Pro
目录
相关文章
ephemerals__
|
5天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
64 9
html的七十二变
|
2天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
12 2
dufadayang
|
4天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
26 4
肾透侧视攻城狮
|
8天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
13 1
星霜旅人
|
21天前
数据结构（栈与列队）
数据结构（栈与列队）
星霜旅人
16 1
白子寰
|
22天前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
白子寰
13 0
java冯坚持
|
24天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
61 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
java冯坚持
|
27天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十：排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法，以及常见的时间复杂度级别，并简单提及了空间复杂度。
java冯坚持
20 1
数据结构与算法学习十：排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
java冯坚持
|
27天前
|
搜索推荐 算法
数据结构与算法学习十四：常用排序算法总结和对比
关于常用排序算法的总结和对比，包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
java冯坚持
17 0
数据结构与算法学习十四：常用排序算法总结和对比
java冯坚持
|
27天前
|
存储 缓存 分布式计算
数据结构与算法学习一：学习前的准备，数据结构的分类，数据结构与算法的关系，实际编程中遇到的问题，几个经典算法问题
这篇文章是关于数据结构与算法的学习指南，涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
java冯坚持
27 0
数据结构与算法学习一：学习前的准备，数据结构的分类，数据结构与算法的关系，实际编程中遇到的问题，几个经典算法问题

热门文章

最新文章

  • 1
    SEO深度解读之HITS链接分析算法
  • 2
    算法训练 筛选号码
  • 3
    秒懂算法 | 最大网络流的增广路算法
  • 4
    算法学习之C语言基础
  • 5
    泛型KMP算法
  • 6
    [干货]基础机器学习算法
  • 7
    18 回归算法 - Softmax回归 - 信贷审批案例
  • 8
    【算法】算法之美—Fire Net
  • 9
    A* + 弗洛伊德 算法 打造 360 向寻路 - [ActionScript3.0]
  • 10
    MapReduce的模式，算法以及用例
  • 1
    数据结构与算法 动态规划(启发式搜索、遗传算法、强化学习待完善)
    87
  • 2
    数据结构与算法 回溯
    32
  • 3
    数据结构与算法 分治
    35
  • 4
    数据结构与算法 搜索（下）
    36
  • 5
    数据结构与算法 搜索（上）
    32
  • 6
    数据结构与算法 搜索
    43
  • 7
    数据结构与算法 排序（下）
    44
  • 8
    数据结构与算法 排序（上）
    50
  • 9
    数据结构与算法 图
    28
  • 10
    数据结构与算法 树（B树，B+树，红黑树待完善）
    56

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • “大数据+算法”助力B2B未来商业
  • 数据+算法定义新世界
  • Apache Flink 流式应用中状态的数据结构定义升级

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks智能数据建模全面公测开始啦！