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

    千次阅读 2017-01-14 12:00:33
    请自己用双向链表实现一个队列队列里节点内存的值为int,要求实现入队,出队和查找指定节点的三个功能。 #include using namespace std; typedef struct node { int data; node* prev; node* next; } Node; ...

    请自己用双向链表实现一个队列,队列里节点内存的值为int,要求实现入队,出队和查找指定节点的三个功能。

    #include <iostream>
    using namespace std;
    
    typedef struct node {
    	int data;
    	node* prev;
    	node* next;
    } Node;
    
    typedef struct queue {
    	Node* front;
    	Node* rear;
    } LinkDQueue;
    
    LinkDQueue* Creat_DQueuelist();              //创建双端队列函数
    void En_DQueuelist(LinkDQueue* q, int e);    //入队函数
    int De_DQueuelist(LinkDQueue* q);    //出队函数
    void Print_DQueuelist(LinkDQueue* q);        //打印队列
    int Getlength_DQueuelist(LinkDQueue* q);     //计算双端队列长度函数
    
    int main() {
    	LinkDQueue* queue = Creat_DQueuelist();
    	Print_DQueuelist(queue);
    	cout << "length: " << Getlength_DQueuelist(queue) << endl;
    
    	En_DQueuelist(queue, 4);
    	Print_DQueuelist(queue);
    	cout << "length: " << Getlength_DQueuelist(queue) << endl;
    
    	int data = De_DQueuelist(queue);
    	if (data != INT_MAX) {
    		cout << "删除元素:" << data << endl;
    	}
    	Print_DQueuelist(queue);
    	return 0;
    }
    
    LinkDQueue* Creat_DQueuelist() {
    	LinkDQueue* queue = new LinkDQueue;
    	queue->front = queue->rear = new Node;
    	queue->front->data = 0;
    	queue->front->prev = NULL;
    	queue->front->next = NULL;
    	queue->rear->next = NULL;
    
    	int length = 0;
    	int number = 0;
    	cout << "请输入双端队列长度:";
    	cin >> length;
    	if (!length) {
    		return queue;
    	}
    	cout << "请输入双端队列数据:";
    	for (int i = 0; i < length; i++) //端口2创建双端队列
    			{
    		Node* pnew = new Node;
    		if (!pnew)
    			cout << "内存分配失败!" << endl;
    		cin >> number;
    		pnew->data = number;
    		pnew->next = NULL;
    		queue->rear->next = pnew;
    		pnew->prev = queue->rear;
    		queue->rear = pnew;
    	}
    	return queue;
    }
    
    void En_DQueuelist(LinkDQueue* q, int e) {
    	int n = 0;
    	Node* tmp = new Node;
    	tmp->data = e;
    	cout << "请输入顺序入队端口:";
    	cin >> n;
    	if (q->front == q->rear) {
    		q->rear->next = tmp;
    		tmp->prev = q->rear;
    		tmp->next = NULL;
    		q->rear = tmp;
    		return;
    	}
    	switch (n) {
    	case 1:
    		tmp->next = q->front->next;
    		q->front->next->prev = tmp;
    		q->front->next = tmp;
    		tmp->prev = q->front;
    		break;
    	case 2:
    		tmp->next = NULL;
    		q->rear->next = tmp;
    		tmp->prev = q->rear;
    		q->rear = tmp;
    		break;
    	}
    }
    
    int De_DQueuelist(LinkDQueue* q) {
    	int data = INT_MAX;
    	if (!q || q->front == q->rear) {
    		cout << "队列为空!" << endl;
    		return data;
    	}
    	int n = 0;
    	Node* tmp = NULL;
    	cout << "请输入顺序出队端口:";
    	cin >> n;
    	switch (n) {
    	case 1:
    		tmp = q->front->next;
    		data = tmp->data;
    		q->front->next = tmp->next;
    
    		if (q->rear == tmp) {
    			q->rear = q->front;
    		} else {
    			tmp->next->prev = q->front;
    		}
    		delete tmp;
    		return data;
    	case 2:
    		tmp = q->rear;
    		data = tmp->data;
    		tmp->prev->next = NULL;
    		q->rear = tmp->prev;
    //		tmp->prev = NULL;
    		delete tmp;
    		return data;
    	}
    }
    
    void Print_DQueuelist(LinkDQueue* q) {
    
    	int n = 0;
    	Node * tmp = NULL;
    	cout << "请输入顺序打印端口:";
    	cin >> n;
    	switch (n) {
    	case 1:
    		tmp = q->front->next;
    		while (tmp) {
    			cout << tmp->data << ' ';
    			tmp = tmp->next;
    		}
    		break;
    	case 2:
    		tmp = q->rear;
    		while (tmp != q->front) {
    			cout << tmp->data << ' ';
    			tmp = tmp->prev;
    		}
    		break;
    	}
    }
    
    int Getlength_DQueuelist(LinkDQueue* q) {
    	int length = 0;
    	Node* tmp = q->front->next;
    	while (tmp) {
    		length++;
    		tmp = tmp->next;
    	}
    	return length;
    }
    


    展开全文
  • 使用链表实现队列

    千次阅读 2015-09-28 20:41:22
    使用链表实现队列和堆栈不一样的地方在于: 需要另外的一个指针指向队列尾部。 每次Push()在链表尾部进行。 每次Pop()则在链表头部进行。 同样,在查看队列头尾元素时(Front()、Back()),对队列进行判空操作 ...

    使用链表实现队列和堆栈不一样的地方在于:

    需要另外的一个指针指向队列尾部。

    每次Push()在链表尾部进行。

    每次Pop()则在链表头部进行。

    同样,在查看队列头尾元素时(Front()、Back()),对队列进行判空操作

    由调用者进行。


    源代码

    MyQueue.h

    #include <iostream>
    
    struct ListNode
    {
    	int nData;
    	ListNode* pNext;
    };
    
    class MyQueue
    {
    public:
    	MyQueue() : m_pHead(NULL), m_pTail(NULL) {}
    
    	void Push(int data);
    	void Pop();
    	int Front();
    	int Back();
    	bool Empty();
    
    private:
    	ListNode* m_pHead;
    	ListNode* m_pTail;
    };

    MyQueue.cpp

    #include "MyQueue.h"
    
    // 在链表尾部插入
    void MyQueue::Push(int data)
    {
    	ListNode* pNew = new ListNode;
    	pNew->nData = data;
    	pNew->pNext = NULL;
    
    	// 插入第一个元素时,
    	// 两指针均指向新元素
    	if (NULL == m_pTail)
    	{
    		m_pTail = pNew;
    		m_pHead = pNew;
    	}
    	else
    	{
    		m_pTail->pNext = pNew;
    		m_pTail = pNew;
    	}
    }
    
    int MyQueue::Back()
    {
    	return m_pTail->nData;
    }
    
    // 在链表头部弹出
    void MyQueue::Pop()
    {
    	ListNode* pPop =  m_pHead;
    	m_pHead = m_pHead->pNext;
    	delete pPop;
    
    	// 弹出最后一个元素时,两指针均置空
    	if (NULL == m_pHead)
    		m_pTail = NULL;
    
    }
    
    int MyQueue::Front()
    {
    	return m_pHead->nData;
    }
    
    bool MyQueue::Empty()
    {
    	return NULL == m_pHead || NULL == m_pTail;
    }


    展开全文
  • 使用链表实现队列 对应于数据机构与算法分析(c++版)第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
  • 用双向链表实现一个栈和队列

    千次阅读 2016-06-15 23:43:53
    双向链表实现堆栈 双向链表实现队列

    下面将介绍一下,如何使用双向链表来分别实现“堆栈”和“队列”,其中有的部分是一样,所以就直接调用了。

    堆栈:后进先出,入栈和出栈都是在栈顶进行;

    队列:先进先出,在队列尾插入元素,从队列头删除元素。

    #include<stdio.h>
    #include<stdlib.h>
    #include"stack.h"
    
    // 判断堆栈是否为空  
    // 为空,返回1;不为空,返回0 
    static int StackIsEmpty(List *plist)
    {
    	if(plist->count==0)
    		return 1;
    	else
    		return 0;
    }
    
    // 判断堆栈是否为满  
    // 为满,返回1;不为满,返回0  
    static int StackIsFull(List *plist)
    {
    	if(plist->count==plist->max)
    		return 1;
    	else
    		return 0;
    }
    
    // 堆栈初始化  
    // 建立一个带哨兵的空链表  
    // 失败,返回0;成功:返回1  
    int StackInit(List *plist,int length)
    {
    	struct node* pnew;
    	pnew=(struct node*)malloc(sizeof(struct node));
    	if(pnew==0)
    	{
    		return 0;
    	}
    	pnew->next=pnew;
    	pnew->prev=pnew;
    	plist->head=pnew; //哨兵元素,头指针指向头结点
    	
    	plist->count=0;
    	plist->max=length;
    	
    	return 1;	
    }
    
    //压栈(在双向链表的头部添加一个元素)
    // 将元素添加到链表头(哨兵元素之后)  
    // 成功,返回1;失败,返回0  
    int StackPush(List *plist,Item item)
    {
    	struct node *pnew;
    	if(StackIsFull(plist))//若栈满,返回0
    		return 0;
    	pnew=(struct node*)malloc(sizeof(struct node));
    	if(pnew==0)
    		return 0;
    	
    	pnew->item=item;
    	pnew->prev=plist->head;
    	pnew->next=plist->head->next;
    	plist->head->next->prev=pnew;
    	
    	(plist->count)++;
    	return 1;
    	
    }
    
    //出栈(在双向链表的头部删除一个元素)
    //失败,返回0;成功,返回1
    int StackPop(List *plist,item *pitem)
    {
    	struct node *pde1;
    	if(StackIsEmpty(plist))
    		return 0;
    	
    	pde1=plist->head->next;
    	*pitem=pde1->item;
    	pde1->next->prev=plist->head;// 改变下一个节点的前向指针
    	plist->head->next=pde1->next;
    	free(pde1);//释放内存
    	(plist->count)--;
    	
    	return 1;
    	
    }
    
    //队列初始化(和栈的初始化的一样的)
    int QueueInit(List *plist,int length)
    {
    	return StackInit(plist,length);
    }
    
    //添加元素到队尾
    int EnQueue(List *plist,Item item)  
    {  
        struct node *pdel;
    	if(StackIsFull(plist))//若队列为满,返回0
    		return 0;
    	pde1=(struct node*)malloc(sizeof(struct node));
    	if(pde1==0)
    		return 0;
    	
    	pde1->item=item;//待插入的元素item
    	pde1->next=plist->head;
    	plist->head->prev=pde1;
    	
    	(plist->count)++;
    	return 1;
    }  
      
    // 从队头删除元素  
    int DeQueue(List *plist,Item *pitem)  
    {  
    	return StackPop(plist,pitem);
    }


    展开全文
  • java 使用数组和链表实现队列示例 队列种特殊的线性表它只允许在表的前端 (front) 进行删除操作只允许 在表的后端 rear 进行插入操作 , 下面介绍一下 java 使用数组和链表实现队列 的示例 1) 用数组实现的队列 ...
  • 我们经常会遇到这样的问题:利用一个链表实现一个队列类和栈类,这个无论是在学生时代还是已经步入社会已经是个合格的程序员也会遇到同样的问题,值得收藏和温习一下
  • 第二,大家在很多书上看到的是使用单链表实现队列,我这里将会使用带头结点尾结点的非循环双链表实现,虽然多维护了两节点和指针域,但是在链表头尾进行插入删除的时候不需要遍历链表了,队列操作变得非常
  • 链表实现队列

    2018-09-24 18:15:41
    编译环境为Vs2010,单链表实现队列的出队和入队操作。
  • 队列 使用链表实现创建队列
  • 队列链表实现

    2018-05-11 00:12:29
    链式队列的出现:存储队列元素的数组大小是固定的,另外,队列的数组实现需要用特殊的方式处理数组(保留一个数组元素用于判断数组 是否已满),以及索引front和rear(计算front/rear时用(front/rear + 1 )% ...

    前面我们看了队列的数组实现,本文来看看用链表实现队列的方法。

    链式队列的出现:存储队列元素的数组大小是固定的,另外,队列的数组实现需要用特殊的方式处理数组(保留一个数组元素用
    	于判断数组是否已满),以及索引front和rear(计算front/rear时用(front/rear + 1 )% maxSize 操作)。而队列
    	的链表实现简化了数组实现的许多特殊情况,并且动态分配内存,所以队列永远也不会满。
    


    看以下程序:

    /** 链表类 */
    class Link{
    
    	/** 结点类,用于初始化结点 */
        class Entry{
            int data;
            Entry next;
            public Entry(){
                data = -1;
                next = null;
            }
            public Entry(int data){
                this.data = data;
                next = null;
            }
        }
    
    	/** 定义头尾索引 */
        public Entry front = null;
        public Entry rear = null;
        public int usedSize = 0;
    
    	/** 判断队列是否为空 */
        public boolean isEmpty(){
    	    return usedSize == 0;
        }
    
    	/** 插入元素 */
        public void insetTail(int data) {
    	    // 若此时队列为空,则直接插入,头尾索引指向该结点
            if (isEmpty()) {
                rear = new Entry(data);
                front = rear;
                // 若队列不为空则尾索引后移指向新结点
            } else {
                rear.next = new Entry(data);
                rear = rear.next;
            }
            // 已用长度每次加1
            usedSize++;
        }
    
    	/** 数据出队列操作 */
        public void pop(){
    		// 若队列为空则直接结束该操作
            if(isEmpty()){
                return;
            }
            // 若不为空则头索引指向第二个结点
            Entry cur = front;
            front = front.next;
            // 第一个结点置为null,便于垃圾回收
            cur.next = null;
            // 已用长度每次减1
            usedSize--;
        }
    
    	/** 获取队列头元素操作 */
        public int getTop(){
    	    // 若队列为空则返回-1
            if (isEmpty()){
                return -1;
            }
            // 若不为空则返回头索引对应的结点数据
            return front.data;
        }
    
    	/** 队列元素的遍历输出 */
        public void print(){
            Entry cur = front;
            while (cur != null){
                System.out.print(cur.data + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    }
    

    用一个例子来验证以上程序是否正确:

    public class LinkQueue {
        public static void main(String[] args){
    	    // 动态制作一个链式队列
            Link link = new Link();
            for (int x = 0; x < 5; x++){
            link.insetTail(x);
            }
            
            System.out.print("队列里的元素是:");
            link.print();
            System.out.println("队列头元素是 :"+ link.getTop());
            System.out.println("队列长度是 :" + link.usedSize);
            System.out.println("==================" );
            
            link.pop();
            System.out.print("执行一次出队操作后队列里的元素是:");
            link.print();
            System.out.println("执行一次出队操作后队列头元素是 :"+ link.getTop());
            System.out.println("执行一次出队操作后队列长度是 :" + link.usedSize);
        }
    }
    

    以上程序的输出结果是:

    		队列里的元素是:0 1 2 3 4 
    		队列头元素是 :0
    		队列长度是 :5
    		==================
    		执行一次出队操作后队列里的元素是:1 2 3 4 
    		执行一次出队操作后队列头元素是 :1
    		执行一次出队操作后队列长度是 :4
    
    展开全文
  • 链表队列实现

    2018-10-06 12:09:17
    链表队列实现 链表队列的具体增删改查实现种单链表实现
  • c++链表队列实现

    2008-09-01 11:02:36
    c++链表队列实现,c++链表队列实现,c++链表队列实现,c++链表队列实现,c++链表队列实现,c++链表队列实现
  • java使用链表实现队列

    千次阅读 2017-09-30 12:27:19
    队列使用Java进行链表实现,在网上找到了一张图,很好,借鉴一下 设置两结点node,front指向队首元素,rear指向队尾; 上代码: public class LinkedQueue { Node front;//队头指针,指向队头节点 ...
  • 什么是队列 ...队列最基本的操作也是两个:入队 enqueue(),放一个数据到队列尾部;出队 dequeue(),从队列头部取一个元素。 队列跟栈一样,也是一种操作受限的线性表数据结构。 顺序队列和链...
  • 队列种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作,下面介绍一下java使用数组和链表实现队列的示例
  • Java链表实现队列

    千次阅读 2019-11-17 20:05:20
    Java链表实现队列
  • 双向链表实现队列

    2018-09-17 20:49:52
    双向链表实现队列   public class LinkedListQueue&lt;E&gt; implements Queue&lt;E&gt;{ class Node{ E e; Node next; public Node(E e, Node Next){ ...
  • 按空格即发射子弹 esc则结束程序
  • 链表队列实现

    2014-07-23 10:04:27
    学习数据结构过程中,亲自在VC++上编译通过的链表队列源代码,与大家共享。
  • 1.队列的单向链表的实现方法 return只可以返回一个值,单向循环链表来...链表实现队列思想也是第一个单元作为头结点,不存放数据,rear指针指向的总是尾结点(在循环链表中也就是头结点的上一个结点)。 2.实现方
  • 优先队列链表实现

    千次阅读 2016-10-10 20:48:57
    插入时需要按照优先级从高到低排序,一般操作系统的任务队列调度会用到 /* 优先队列(链表实现) * front 为队头指针(链表头节点) * rear 为队尾指针 */ #include<stdio.h> #include<stdlib.h> typedef struct...
  • Redis有两种方式实现消息队列种是用Redis自带的链表数据结构,另种是用Redis发布/订阅模式实现,这篇文章先介绍链表实现消息队列,有需要的朋友们可以参考借鉴。
  • 数据结构-使用链表实现队列

    万次阅读 2020-01-18 22:13:34
    使用链表实现队列 目录结构 Queue接口 package LinkedListQueue; //队列 public interface Queue<E> { int getSize(); boolean isEmpty(); void enqueue(E e); //向队列中添加元素 E dequeue(); /...
  • tips:前些天学习了链表和栈,今天来看看c语言数据结构之队列实现以及队列的各种操作。 队列的特点是先进先出,后进后出,因此我们很容易就能够想到用单链表的尾插法,和头部删除法去实现队列的入队和出队的操作...
  • [python队列]用链表实现队列

    千次阅读 2019-06-28 10:40:02
    定义一个头结点,左边指向队列的开头,右边指向队列的末尾,这样就可以保证我们插入一个元素和取出一个元素都是O(1)的操作。 方法一,用链表实现程序如下: # 定义一个头结点,左边指向队列的开头, # 右边指向队列...
  • 链表实现队列

    2013-12-05 04:13:24
    这是一个链表实现队列的列子,里面用到了指针的东西, 还有NODE的东西
  • 主要介绍了C语言数据结构链表队列实现的相关资料,需要的朋友可以参考下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 192,127
精华内容 76,850
关键字:

一个队列的链表实现使用了