【经典算法题】用链表实现栈队列和双端队列

青旅半醒 2024-05-25 17:33 10阅读 0赞

## 前言 ##

> **?：链表作为其它很多数据结构的基础，是面试算法中常考基础知识。面试中的链表题重在考查大家的coding能力，链表难的不是算法，而是难在繁琐的边界处理，一不小心就会报空指针异常。本文是开启链表基础的第一章，通过介绍几种用链表来实现的数据结构来让大家快速了解链表和掌握链表的常用方法。**

--------------------

**目录**

前言

所需前置知识

一:用链表来实现栈

1.1思路

2.2：代码

二：用链表来实现队列

2.1 思路

2.2 代码

三：用链表实现双端队列

3.1 思路

3.2 代码

--------------------

## 所需前置知识 ##

如图所示：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16][]

**温馨提示：建议在看本文之前掌握前置知识，效果会更佳。**

--------------------

## 一:用链表来实现栈 ##

### **1.1思路** ###

> **?：我们知道栈是先加入的元素先弹出，后加入的元素后弹出；先加入的元素在栈的底部，后加入的元素在栈的顶部。**
> 
> **这个我们可以想象成碟盘子和洗盘子，每一个放入的盘子都会叠在新放入的盘子的上方，并先进行洗，原来先加入的盘子最后洗。**
> 
> **?：我们可以用链表的头插入来实现队列。**
> 
> **如下图所示，加入数据的顺序是123,H表示链表的头部，即栈的顶部。**
> 
> **![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 1][]**

### 2.2：代码 ###

public static class Node<V>{
            public V value;
            public Node<V> next;
            public Node(V val){
                this.value=val;
            }
        }
        public static class MyStack<V>{
            private Node<V> head;
            private int size;
            public MyStack(){
                head=null;
                size=0;
            }
    
            //1：判断是否为空
            public boolean isEmpty(){
                return size==0;
            }
            //2:得到栈中元素的个数
            public int size(){
                return size;
            }
            //3:向栈中加入元素
            public void push(V value){
                Node<V> cur=new Node<>(value);
                cur.next=head;
                head=cur;
                size++;
            }
            //4:弹出栈中的元素
            public V pop(){
                V res=null;
                if(head!=null){
                    res=head.value;
                    head=head.next;
                    //JVM会帮我们释放链表的头节点，如果是c/c++需要手动释放
                    size--;
                }
                return res;
            }
            //5:拿到栈顶的元素
            public V peek(){
                V res=null;
                if(head!=null){
                    res=head.value;
                }
                return res;
            }
        }

--------------------

## 二：用链表来实现队列 ##

### 2.1 思路 ###

> **?：我们知道队列是先入队列排在前面，后入队列排在后面；先入队列先弹出处理，后入队列后弹出并处理。**
> 
> **我们可以把队列想象为现实中的排队，先排队的先受到服务，后排队的后受到到服务。**
> 
> **?：我们可以通过链表的尾插来实现队列。**
> 
> **如下图所示 进入队列的数据顺序是1->2->3 H表示链表的头部也是队列的队头**
> 
> **![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 2][]**

### 2.2 代码 ###

public static class Node<V>{
            public V value;
            public Node<V> next;
            public Node(V val){
                this.value=val;
            }
        }
        public static class MyQueue<V>{
            private Node<V> head;
            private Node<V> tail;
            private int size;
            public MyQueue(){
                head=null;
                tail=null;
                size=0;
            }
            //1:判断队列是否为空
            public boolean isEmpty(){
                return size==0;
            }
            //2:拿出队列的大小
            public int size(){
                return size;
            }
            //3:队列中添加元素
            public void offer(V value){
                Node<V> cur=new Node<>(value);
                if(head==null){
                    head=cur;
                    tail=cur;
                }
                else{
                    tail.next=cur;
                    tail=cur;
                }
                size++;
            }
            //4:弹出元素
            public V poll(){
                V res=null;
                if(head!=null){
                    res=head.value;
                    head=head.next;
                    if(head==null){
                        tail=null;
                    }
                    size--;
                }
                return res;
            }
            //5:拿到队头的元素
            public V peek(){
                V res=null;
                if(head!=null){
                    res=head.value;
                }
                return res;
            }
        }

--------------------

## 三：用链表实现双端队列 ##

### 3.1 思路 ###

> **?：首先我们要理解什么叫做双端队列？**
> 
> **双端队列：支持从头部加入元素，从头部弹出元素，从尾部加入元素，从尾部弹出元素。**
> 
> **?：而如何用链表实现双端队列呢？**
> 
> **注意：首先如果我们选择使用单向链表来实现双端队列，将无法完成从尾部删除元素。因此我们要使用双向链表来实现双端队列。**

### 3.2 代码 ###

public static class DoubleNode<V>{
            public V value;
            public DoubleNode<V> next;
            public DoubleNode<V> last;
            public DoubleNode(V value){
                this.value=value;
                next=null;
                last=null;
            }
        }
        //双端队列可以完成，从头部加入元素，从头部删除元素
        //从尾部加入元素，从尾部删除元素
        public static class MyDeque<V>{
            private DoubleNode<V> head;
            private DoubleNode<V> tail;
            private int size;
            public MyDeque(){
                head=null;
                tail=null;
                size=0;
            }
            //1:判断双端队列是否为空
            public boolean isEmpty(){
                return size==0;
            }
            //2:双端队列的大小
            public int size(){
                return this.size;
            }
            //3:从双端队列头部加入元素
            //第一加入元素的时候，头指针和尾指针都要指向这个节点
            //之和每次加入，只需要改变头，不需要改变尾节点，因此要分类讨论
            public void pushHead(V value){
                DoubleNode<V> cur=new DoubleNode<>(value);
                if(head==null){
                    head=cur;
                    tail=cur;
                }
                else{
                    cur.next=head;
                    head.last=cur;
                    head=cur;
                }
                size++;
            }
            //从双端队列的尾部加入元素(相当于链表的尾插)
            //第一次加入的时候，头指针和尾指针均要指向该节点
            //之后的每次加入，只需要改变尾部节点即可
            public void pushTail(V value){
                DoubleNode<V> cur=new DoubleNode<>(value);
                if(head==null){
                    head=cur;
                    tail=cur;
                }
                else{
                    cur.last=tail;
                    tail.next=cur;
                    tail=cur;
                }
                size++;
            }
            //从头部弹出数据
            //如果只有一个节点时，弹出后头指针和尾指针都需要置为null
            //如果不只有1个节点，弹出后只需要改变头节点
            public V pollHead(){
                V res=null;
                //如果链表为空，直接返回
                if(head==null){
                    return res;
                }
                //链表不为空
                res=head.value;
                size--;
                //如果只有一个节点时
                if(head==tail){
                    head=null;
                    tail=null;
                }
                else{//不只有一个节点时
                    head=head.next;
                    head.last=null;
                }
                return res;
            }
            //从尾部弹出数据
            //如果链表为空，直接返回null
            //如果链表只有一个元素，弹出后，头指针和尾指针均置空
            public V pollTail(){
                V res=null;
                //链表为空
                if(head==null){
                    return null;
                }
                //链表不为空
                res=tail.value;
                size--;
                //如果只有一个节点
                if(head==tail){
                    head=null;
                    tail=null;
                }
                else{//链表不只有一个节点
                    tail=tail.last;
                    tail.next=null;
                }
                return res;
            }
        }

--------------------

**警告：本文上述代码均是用Java实现的，在Java中一个对象如果没有任何指针指向它，JVM会自动回收。请C/C++的读者一定要手动释放要删除的节点，以免造成内存泄露。**

--------------------

**由于本人水平十分有限，若有错误请即使告知！如果有帮助别忘了**

**点赞? 收藏✨ 关注✌**

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/89dcc768ca1549669f9266c04b97e12c.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/e3a6ba2c70b0485299d1f81a9d220529.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/a86d7bad42f94aea86c14494cd6bf8d9.png