精华内容
下载资源
问答
  • 双向链表实现队列

    2021-03-27 14:41:26
    //使用双向链表实现队列 public class Code01_DoubleLinkedListToQueue { public static class Node<V>{ public V value; public Node<V> next; public Node<V> last; public Node(V v){ ...
    //使用双向链表实现队列
    public class Code01_DoubleLinkedListToQueue {
        public static class Node<V>{
            public V value;
            public Node<V> next;
            public Node<V> last;
    
            public Node(V v){
                value = v;
                next = null;
                last = null;
            }
        }
    
        public static class MyQueue<V>{
            private Node<V> head;
            private Node<V> tail;
            private int size;
    
    
            public void pusHead(V value){
                Node<V> cur = new Node<V>(value);
                if(head == null){
                    head = cur;
                    tail = cur;
                }else{
                    //新加的next节点指向当前的头部
                    cur.next = head;
                    //当前头部的last节点指向新加的节点
                    head.last = cur;
                    //让头部变成新加节点
                    head = cur;
                }
                size++;
            }
            public void pusTail(V value){
                Node<V> cur = new Node<V>(value);
                if(tail == null){
                    head = cur;
                    tail = cur;
                }else{
                    //新加的节点last指针指向当前的尾部
                    cur.last = tail ;
                    //当前尾部的next节点指向新增的节点
                    tail.next = cur;
                    //让尾部变成新增节点
                    tail = cur;
                }
                size++;
            }
            public V pollHead(){
                V ans = null;
                if(head == null){
                    return ans;
                }
                size -- ;
                ans = head.value;
                if(head == tail ){
                    head = null;
                    tail = null;
                }else{
                    head = head.next;
                    head.last = null;
                }
                return ans;
            }
            public V pollTail(){
                V ans = null;
                if(tail == null){
                    return ans;
                }
                size -- ;
                ans = tail.value;
                if(head == tail ){
                    head = null;
                    tail = null;
                }else{
                    tail = tail.last;
                    tail.next = null;
                }
                return ans;
            }
    
            public V peekHead(){
                V ans = null;
                if(head != null){
                    ans = head.value;
                }
                return ans;
            }
            public V peekTail(){
                V ans = null;
                if(tail != null){
                    ans = tail.value;
                }
                return ans;
            }
            public boolean isEmpty(){
                return size == 0 ? true:false;
            }
    
            public int size(){
                return size;
            }
    
            public MyQueue(){
                size = 0;
                head = null;
                tail = null;
            }
        }
    }
    
    展开全文
  • /* * 作为自定义链表公共类 */ public class Node<T> { T value; Node<T> pre; Node<T> next; public Node(T value){ this.value = value;... * 用双向链表实现队列和栈 */ publi...

    /*
     * 作为自定义链表公共类
     */
    public  class Node<T> {
         T value;
         Node<T> pre;
         Node<T> next;
         public Node(T value){
             this.value = value;
         }
    }

    public class SelfStackAndQueue {
        /*
         * 用双向链表实现队列和栈
         */
        public static void main(String[] args) {
            MyLink<Integer> myLink = new MyLink<>();
            //队列
            myLink.addHead(1);
            myLink.addHead(2);
            System.out.println(myLink.popLast());
            System.out.println(myLink.popLast());
            //栈
            myLink.addHead(1);
            myLink.addHead(2);
            System.out.println(myLink.popHead());
            System.out.println(myLink.popHead());
        }

    }
    //双向链表实现
    class MyLink <T>{
        Node<T> head;
        Node<T> last;
        
        //往头部添加
        public void addHead(T value) {
            Node<T> node = new Node<>(value);
            if(this.head !=null) {
                this.head.pre = node;
                node.next = this.head;
                this.head = node;
            }else {
                this.head = node;
                this.last = node;
            }
        }
        //往尾部添加
        public void addLast(T value) {
            Node<T> node = new Node<>(value);
            if(this.last != null) {
                this.last.next = node;
                node.pre = this.last;
                this.last = node;
            }else {
                this.head = node;
                this.last = node;
            }
            
        }
        //弹出头部
        public T popHead() {
            if(this.head == null) {
                return null;
            }
            T value = head.value;
            Node<T> next = this.head.next;
            if(next == null) {
                this.head = null;
                this.last = null;
            }else {
                next.pre = null;
                this.head = next;
            }
            return value;
        }
        //弹出尾部
        public T popLast() {
            if(this.last == null) {
                return null;
            }
            T value = this.last.value;
            Node<T> pre = this.last.pre;
            if(pre == null) {
                this.head = null;
                this.last = null;
            }else {
                pre.next = null;
                this.last = pre;
            }
            return value;
        }
        
    }

    展开全文
  • 一、双向链表(double linked list)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,除了插入和删除的时候需要更改两个指针变量,需要注意的是修改的顺序很重要,...

    一、双向链表(double linked list)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,除了插入和删除的时候需要更改两个指针变量,需要注意的是修改的顺序很重要,插入如图3-14-5,删除如图3-14-6。

    b9ad5e9a3029b7bc89cc94366d9076f3.png

    0bf5532ec11cb19c3a1b4765bc3dc6a4.png

    由于引入了prev指针,insert和delete函数中都有一些特殊情况需要用特殊的代码处理,不能和一般情况用同样的代码处理,这非常不爽,如果在表头和表尾各添加一个Sentinel节点(这两个节点只用于界定表头和表尾,不保存数据),就可以把这些特殊情况都转化为一般情况了。如图26.6

    dadb9d71319ee7faba78a24fa31a73b1.png

    在《队列的链式存储结构》中我们使用单链表实现队列的尾进头出,下面我们演示使用双向链表实现队列的头进尾出。

    参考:《Linux C编程 一站式学习》

    C++ Code

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    /*************************************************************************

    > File Name: doublylinkedlist.h

    > Author: Simba

    > Mail: dameng34@163.com

    > Created Time: Fri 28 Dec 2012 08:02:35 PM CST

    ************************************************************************/

    #ifndef DOUBLYLINKEDLIST_H

    #define DOUBLYLINKEDLIST_H

    typedef

    struct node

    {

    unsigned

    char item;

    struct node *prev;

    struct node *next;

    } node;

    typedef node *link;

    link make_node(

    unsigned

    char item);

    void free_node(link p);

    link search(

    unsigned

    char key);

    void insert(link p);

    void deletep(link p);

    void traverse(

    void (*visit)(link));

    void destroy(

    void);

    void enqueue(link p);

    link dequeue(

    void);

    #endif

    C++ Code

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    64

    65

    66

    67

    68

    69

    70

    71

    72

    73

    74

    75

    76

    77

    78

    79

    80

    81

    82

    83

    84

    85

    86

    87

    88

    89

    90

    91

    92

    93

    94

    95

    96

    97

    98

    99

    100

    101

    102

    103

    104

    /*************************************************************************

    > File Name: doublylinkedlist.c

    > Author: Simba

    > Mail: dameng34@163.com

    > Created Time: Fri 28 Dec 2012 08:07:21 PM CST

    ************************************************************************/

    #include

    #include

    #include

    "doublylinkedlist.h"

    node tailsentinel;

    node headsentinel = {

    0,

    NULL, &tailsentinel};

    node tailsentinel = {

    0, &headsentinel,

    NULL};

    static link head = &headsentinel;

    static link tail = &tailsentinel;

    link make_node(

    unsigned

    char item)

    {

    link p =  malloc(

    sizeof(node));

    p->item = item;

    p->prev = p->next =

    NULL;

    printf(

    "make node from Item %d\n", item);

    return p;

    }

    void free_node(link p)

    {

    printf(

    "free node ...\n");

    free(p);

    }

    link search(

    unsigned

    char key)

    {

    link p;

    printf(

    "search by key %d\n", key);

    for (p = head->next; p != tail; p = p->next)

    if (p->item == key)

    return p;

    return

    NULL;

    }

    void insert(link p)

    {

    printf(

    "insert node from head ...\n");

    p->next = head->next;

    head->next->prev = p;

    head->next = p;

    p->prev = head;

    }

    void deletep(link p)

    {

    printf(

    "delete node from ptr ...\n");

    p->prev->next = p->next;

    p->next->prev = p->prev;

    }

    void traverse(

    void (*visit)(link))

    {

    link p;

    printf(

    "doublylinkedlist traverse ...\n");

    for (p = head->next; p != tail; p = p->next)

    visit(p);

    printf(

    "\n");

    }

    void destroy(

    void)

    {

    link q, p = head->next;

    printf(

    "destory doublylinkedlist ...\n");

    head->next = tail;

    tail->prev = head;

    while (p != tail)

    {

    q = p;

    p = p->next;

    free_node(q);

    }

    }

    void enqueue(link p)

    {

    printf(

    "enqueue from head ...\n");

    insert(p);

    }

    link dequeue(

    void)

    {

    if (tail->prev == head)

    return

    NULL;

    else

    {

    link p = tail->prev;

    printf(

    "dequeue from tail ...\n");

    deletep(p);

    return p;

    }

    }

    C++ Code

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    /*************************************************************************

    > File Name: main2.c

    > Author: Simba

    > Mail: dameng34@163.com

    > Created Time: Fri 28 Dec 2012 08:18:57 PM CST

    ************************************************************************/

    #include

    #include

    "doublylinkedlist.h"

    void print_item(link p)

    {

    printf(

    "print item %d \n", p->item);

    }

    int main(

    void)

    {

    link p = make_node(

    10);

    insert(p);

    p = make_node(

    5);

    insert(p);

    p = make_node(

    90);

    insert(p);

    p = search(

    5);

    deletep(p);

    free_node(p);

    traverse(print_item);

    destroy();

    printf(

    "..................\n");

    p = make_node(

    100);

    enqueue(p);

    p = make_node(

    200);

    enqueue(p);

    p = make_node(

    250);

    enqueue(p);

    while ((p = dequeue()))

    {

    print_item(p);

    free_node(p);

    }

    return

    0;

    }

    输出为:

    48fa802e97c39bfe605deee7b856acd3.png

    解决的error:

    关于错误 error C2275: “XXX”: 将此类型用作表达式非法

    在移植c++代码到c的时候,经常会出现一个奇怪的错误, error C2275: “XXX”: 将此类型用作表达式非法,这个错误是由于c的编译器要求将变量的定义放在所有函数调用语句之前,而c++没有这样的要求造成的。解决的办法就是把变量的定义全部放在变量的生存块的开始。

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

    二、将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表就称为单循环链表,简称循环链表(circular linked list)。如下图所示。

    d0c0007c4392fd388533384ee0567959.png

    其实循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断p->next是否为空,现在则是p->next不等于头结点,则循环未结束。

    我们在《队列的顺序存储结构(循环队列)》中使用数组实现了环形队列,我们还要“假想”它是首尾相接的,而如果基于链表实现环形队列,我们本来就可以用指针串成首尾相接的。把上面的程序改成双向环形链表也非常简单,只需要将

    把doublylinkedlist.c中的

    node tailsentinel;

    node headsentinel = {0, NULL, &tailsentinel};

    node tailsentinel = {0, &headsentinel, NULL};

    static link head = &headsentinel;

    static link tail = &tailsentinel;

    改成:

    node sentinel = {0, &sentinel, &sentinel};

    static link head = &sentinel;

    再把doublylinkedlist.c中所有的tail替换成head即可,相当于把head和tail合二为一了。如图26.7:

    a5e08c7c1578c37fb94f15557bb1caea.png

    展开全文
  • 利用双向链表实现队列和栈 public class BlinkConversion<T> { public Node<T> head; public Node<T> tail; //从头部加节点 public void addFromHead(T value){ Node<T> cur = new ...

    利用双向链表实现队列和栈

    public class BlinkConversion<T> {
        public Node<T> head;
        public Node<T> tail;
        //从头部加节点
        public void addFromHead(T value){
            Node<T> cur = new Node<>(value);
            if(head==null){
                head =cur;
                tail =cur;
            }else{
                cur.next = head;
                head.pre = cur;
                head = cur;
            }
        }
        //从尾部加节点
        public void addFromTail(T value){
            Node<T> cur = new Node<>(value);
            if(head == null){
                head = cur;
                tail = cur;
            }else{
                tail.next = cur;
                cur.pre = tail;
                tail = cur;
            }
        }
        //从头部弹出
        public T popFromHead(){
            if(head == null){
                return null;
            }
            Node<T> cur = head;
            if(head == tail){
                head = null;
                tail = null;
            }else{
                head = head.next;
                head.pre = null;
                cur.next = null;
            }
            return cur.value;
        }
        //从尾部取出节点
        public T popFromTail(){
            if(head == null){
                return null;
            }
            Node<T> cur = tail;
            if(head == tail){
                head = null;
                tail = null;
            }else{
                tail = tail.pre;
                tail.next = null;
                cur.pre = null;
            }
            return cur.value;
        }
        public boolean isEmpty(){
            return head == null;
        }
    
        public class Node<T>{
            public T value;
            public Node pre;
            public Node next;
            public Node(T data){
                value = data;
            }
        }
    }

     

    展开全文
  • 我们使用一种比较特殊的链表——非循环双向链表实现队列。首先这里的说明的是构建的是普通的队列,而不是循环队列。当我们使用数组的时候创建循环队列是为了节省存储空间,而来到链表中时,每一个节点都是动态申请...
  • 本文使用双向链表实现队列,具体代码如下: 1 #include<stdlib.h> #inlcude<stdio.h> 2 #define new(type) (type*)malloc(sizeof(type)) 3 typedef struct ListNode{ 4 int data...
  • 1.双向链表实现队列LinkedQueue实现 /** * 双向链表实现队列 * @author Administrator */ public class LinkedQueue implements Queue { /** * 链表的结点个数 */ private int size; /** * 首结点 */ ...
  • 队列queue底层通过无头双向链表实现,下面让我们实现一下queue常用的操作方法 class ListNode{ ListNode next; //指针后继域 ListNode prev; //指针前驱域 int val; //指针数值域 public ListNode(int val) { ...
  • 一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,除了插入和删除的时候需要更改两个指针变量,需要注意的是修改的...
  • 使用双向链表实现队列和栈

    千次阅读 2013-04-26 07:59:49
    下面是使用双向链表实现队列的进出和栈的push和pop操作 首先是依然是给出双向链表节点NodeType public class NodeType { public NodeType llink; public int data; public NodeType rlink; public ...
  •  用双向链表实现队列:  队列描述了这样一种数据结构:对数据元素而言,是先进先出的。而双向链表则是链表的一种变种,每个节点具有两个指针:rlink和llink,显然双向链表对于“表头”和“表尾”的操作比链...
  • 一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,除了插入和删除的时候需要更改两个指针变量,需要注意的是修改的...
  • 一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,除了插入和删除的时候需要更改两个指针变量,需要注意的是修改的...
  • 思路:使用双向链表(LinkedList,LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用)。双向链表的大小就是窗口的个数,每次向窗口中增加一个元素时,如果比窗口中最后一个大,就删除...
  • typedef int DItemType; typedef struct SDoubleList { DItemType iValue; SDoubleList *prev; SDoubleList *next; ...} DLinkedList,*pDLinkedList;.../* 创建双链表 */ DLinkedList *InitDoubleList() { DLinkedList
  • 双向链表实现队列: struct listNode { int data ; listNode * next; listNode * prev; listNode(int x) { data = x; next = NULL ; prev = NULL ; } }; class myqueue { public : ...
  • 双向链表: 就是有双向指针 即 双向的链域 链结点的结构: ┌────┬────┬────────┐ │data│next│previous│ └────┴────┴────────┘ 双向链表不必是双端链表(持有对最后一个...
  • 双向链表实现栈和队列

    万次阅读 2021-02-05 14:31:34
    双向链表实现栈和队列前言1. 双向链表2. 栈 --》 双向链表 首部加 首部出 O(1)3. 队列 --》 双向链表 首部加 尾部出 O(1) 前言 栈 --》 双向链表 首部加 首部出 O(1) 队列 --》 双向链表 首部加 尾部出 O(1) 1. ...
  • 双向链表实现一个栈和队列

    千次阅读 2016-06-15 23:43:53
    双向链表实现堆栈 双向链表实现队列
  • 实现队列,需要的是生产者和消费者的模型。其本质是执行进队和出队操作。 代码源于https://github.com/takumiCX/beautiful-concurrent。 那么怎样才能实现一个并发无锁的队列呢?首先需要考虑队列是基于链表的,...
  • 通过链表实现队列功能通过链表实现队列功能单向链表实现队列功能双向链表实现队列功能 通过链表实现队列功能 Array 功能 返回 push 底部插入 数组长度 unshift 顶部插入 数组长度 pop 底部删除 删除的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,146
精华内容 858
关键字:

双向链表实现队列