精华内容
下载资源
问答
  • 在上一次,我们通过取余等...下面,我们使用链式存储结构来实现一个真正首尾相连的循环队列: class Node(object): '定义节点。' def __init__(self): '初始化:数据域与指针域。' self.data = None sel...

    在上一次,我们通过取余等数学方法实现了顺序存储的循环队列。由于我们使用的是Python内置的列表类型作为底层,实际上我们的存储空间并不是首尾相连的。下面,我们使用链式存储结构来实现一个真正首尾相连的循环队列:


    class Node(object):
    	'定义节点。'
    
    	def __init__(self):
    		'初始化:数据域与指针域。'
    
    		self.data = None
    		self.next = None
    
    class Queue(object):
    	'定义循环链表。'
    
    	def __init__(self,MaxSize):
    		'初始化:建立链式存储空间。'
    
    		self.MaxSize = MaxSize
    		self.size = 0
    		self.front = None
    		self.rear = None
    		self.OpenSpace()
    
    	def OpenSpace(self):
    		'方法:用于初始化。'
    
    		node = Node()
    		self.front = node
    		self.rear = node    #创建第一个节点,将队头指针与队尾指针指向它。
    
    		for i in range(self.MaxSize - 1):
    			node = Node()
    			self.front.next = node
    			self.front = node    #通过移动队头指针将剩下的节点依次创建并连接。
    
    		self.front.next = self.rear
    		self.front = self.rear    #利用队头指针与队尾指针将所有节点连接成环。
    
    
    	def IsEmpty(self):
    		'方法:判断是否为空队列。'
    
    		if self.size == 0:
    			return True
    		else:
    			return False
    
    	def IsFull(self):
    		'方法:判断是否为满队列。'
    
    		if self.size == self.MaxSize:
    			return True
    		else:
    			return False
    
    	def GetSize(self):
    		'方法:得到队列长度。'
    
    		return self.size
    
    	def push(self,data):
    		'方法:进队。'
    
    		if self.IsFull():
    			raise IndexError('队列已满,无法入队。')
    		else:
    			self.rear.next.data = data
    			self.rear = self.rear.next
    			self.size += 1
    
    	def pop(self):
    		'方法:出队。'
    
    		if self.IsEmpty():
    			raise IndexError('队列已空,无法出队。')
    		else:
    			self.front.data = None
    			self.front = self.front.next
    			self.size -= 1
    
    	def GetFrontData(self):
    		'方法:得到队首元素。'
    
    		return self.front.data
    
    	def GetRearData(self):
    		'方法:得到队尾元素。'
    
    		return self.rear.data
    

    测试:

    my_queue = Queue(10)
    
    for i in range(5):
    	my_queue.push(i + 1)
    	print('队首元素:{}'.format(my_queue.GetFrontData()))
    	print('队尾元素:{}'.format(my_queue.GetRearData()))
    
    print('\n')
    for i in range(3):
    	my_queue.pop()
    	print('队首元素:{}'.format(my_queue.GetFrontData()))
    	print('队尾元素:{}'.format(my_queue.GetRearData()))
    
    print('\n')
    for i in range(5,5 + 8):
    	my_queue.push(i + 1)
    	print('队首元素:{}'.format(my_queue.GetFrontData()))
    	print('队尾元素:{}'.format(my_queue.GetRearData()))
    
    my_queue.push(0)
    

    结果:

    队首元素:1
    队尾元素:1
    队首元素:1
    队尾元素:2
    队首元素:1
    队尾元素:3
    队首元素:1
    队尾元素:4
    队首元素:1
    队尾元素:5
    
    
    队首元素:2
    队尾元素:5
    队首元素:3
    队尾元素:5
    队首元素:4
    队尾元素:5
    
    
    队首元素:4
    队尾元素:6
    队首元素:4
    队尾元素:7
    队首元素:4
    队尾元素:8
    队首元素:4
    队尾元素:9
    队首元素:4
    队尾元素:10
    队首元素:4
    队尾元素:11
    队首元素:4
    队尾元素:12
    队首元素:4
    队尾元素:13
    Traceback (most recent call last):
      File "带链的队列.py", line 112, in <module>
        my_queue.push(0)
      File "带链的队列.py", line 63, in push
        raise IndexError('队列已满,无法入队。')
    IndexError: 队列已满,无法入队。
    
    
    展开全文
  • 队列链式存储结构

    2019-09-20 02:20:27
    队列链式存储结构实现的关键点让数据从尾进,从头出。 这样插入和删除的时间复杂度都O(1)了。 当然队列链式存储结构还是继承之前的Queue接口,实现LinkedList中的方法 LinkedQueue类代码如下: public ...

    之前写过队列和循环队列,这里就不再做多余的赘述了。
    队列的链式存储结构实现的关键点是让数据从尾进,从头出。
    这样插入和删除的时间复杂度都是O(1)了。

    当然队列的链式存储结构还是继承之前的Queue接口,实现LinkedList中的方法
    LinkedQueue类代码如下:

    public class LinkedQueue<E> implements Queue<E> {
    	
    	private LinkedList<E> list;
    	public LinkedQueue() {
    		list=new LinkedList<E>();
    	}
    	
    	@Override
    	public int getSize() {
    		return list.getSize();
    	}
    
    	@Override
    	public boolean isEmpty() {
    		return list.isEmpty();
    	}
    
    	@Override
    	public void clear() {
    		list.clear();
    	}
    
    	@Override
    	public void enqueue(E e) {
    		list.addLast(e);
    	}
    
    	@Override
    	public E dequeue() {
    		return list.removeFirst();
    	}
    
    	@Override
    	public E getFront() {
    		return list.getFirst();
    	}
    
    	@Override
    	public E getRear() {
    		return list.getLast();
    	}
    	
    }
    

    此时再写一个main函数进行测试即可。
    队列的链式存储结构就到这里,经过不断的学习,我会进行补充。

    展开全文
  • 五、队列的定义定义:队列(queue):队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入操作的一端称为队尾,允许删除操作...
    五、队列的定义
    定义:队列(queue):队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
    队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入操作的一端称为队尾,允许删除操作的一端称为队头。
    队列与现实生活中的排队机制很像,排在队头的出队,而想入队则只能从队尾开始。
    ===============================================================================
    队列:
    顺序存储结构:(循环队列)

    #define N 10
    typedef int data_t;
    typedef struct
    {
    data_t data[N]; //数据存储
    int length; //不能用,注意想想方式
    }Node;

    ===============================================================================
    六、循环队列
    线性表有顺序存储和链式存储两种结构,队列作为特殊的线性表,自然也有顺序队列和链式队列两种形式。
    但是,队列的顺序存储却有很大的缺陷。如果我们要建立元素个数为n的队列,则需要建立一个数组长度不小于n的数组,数组下标为0的为队头,当最大下标的为队尾。若有元素要入队,则只需将其存储在第n+1个位置即可。
    而若想出队,则删除了下标为0的元素后,所有在其后的元素都需要向前移动一格,即保持下标为0的元素为队头。但这样做显然浪费了大量时间。
    解决该问题的方法就是不再限制下标为0的元素为队头,每次出队后,队头自动变成当前数组下标最小的元素即可。这样就无需所有元素向前移动。
    但是,若如此做,则会造成大量的已出队的元素的存储空间浪费。而且,若此时入队元素已经大于n,则我们需要更大的存储空间才行,但队头位置有大量空间未利用,空间浪费严重。
    解决以上问题的方法就是如果后面满了,则我们就从头开始,也就是将队列做成头尾相接的循环。我们把这种头尾相接的顺序存储结构的队列称为循环队列。
    这样,我们就需要两个指示其队头(front)和队尾(rear)的下标变量。
    typedef int data_t;
    typedef struct
    {
    data_t data[MAXSIZE];
    int front; 头位置下标
    int rear; 尾位置下标
    }SqQueue;

    循环队列的操作:
    1、创建空的循环队列(CreateSqQueue)
    2、判断是否为空队列(SqQueueEmpty)
    3、判断是否为满队列(SqQueueFull)
    4、新数据元素入队(EnQueue)
    5、数据元素出去(OutQueue)
    6、求队长(SqQueueLenght)
    7、遍历循环队列(VisitSqQueue)

    当front==rear时,此时队头和队尾重合,则该队列为空队列;当(rear+1)%QueueSize==front时,此时队尾的下个位置就是队头,则该队列为满队列。注意rear的位置不是队尾元素的位置,而是队尾元素的下一个位置,即当队列满时,队列中还有一个空闲存储空间,但我们规定该状态下就是满队列。
    那么,定义好队列的的队头和队尾位置,我们来考虑怎样计算队列长度。
    当rear>front时,表示队尾在队头右边,此时队列长度为rear-front;当rear<front时,表示队尾在队友左边,此时计算队列长度应分成两部分,即rear一部分,QueueSize-front一部分,总体长度为rear-front+QueueSize。
    通用计算队列长度的公式是
    length=(rear-front+QueueSize)%QueueSize
    1、判断队是否为空EmptyQueue
    //代码见附录
    2、判断队是否为满FullQueue
    //代码见附录
    3、入队操作EnQueue
    //代码见附录
    4、出队操作DeQueue
    //代码见附录
    从循环队列的特性我们可以看出,循环队列虽然操作较为简单,但是由于队列定长,因此会出现数据溢出问题。这时我们需要考虑使用队列的链式存储结构。
    ===============================================================================
    七、队列的链式存储结构及实现
    队列的链式存储结构本质上是从单链表演化而来的。将单链表改造成链式队列,如果将头结点做为队头,最后一个节点做为队尾,则该队列的出队操作方便,而入队操作较慢;反之,如果将头结点做为队尾,最后一个节点做为队头,则该队列的入队操作方便,而出队操作较慢。
    那么,能否将单链表稍加改进,使得该链式队列的入队操作和出队操作一样方便呢?
    答案是可以的,只需要改进头结点。将“头结点存储一个next指针”改为“头结点存储两个指针front和rear”,front指针指向队头,rear指针指向队尾。这样我们进行出队/入队操作时,只需要访问这两个指针就能快速地找到队头/队尾。
    1、队列的链式存储结构定义
    将单链表的头结点稍加改造
    typedef int data_t;
    typedef struct node_t//定义单链表
    {
    data_t data;
    struct node_t *next;
    } linknode_t, *linklist_t;
    typedef struct//定义链式队列
    {
    linklist_t front, rear;
    } linkqueue_t;

    链式队列的操作:
    申请的头指针为lq,lq->front == lq->rear
    1、创建空链式队列(CreateLinkQueue)
    2、判断是否为空(LinkQueueEmpty) rear == front != NULL
    3、清空链式队列(ClearLinkQueue)
    4、求链式队列的长度(LinkQueueLength)
    5、新数据元素入队(EnLinkQueue) rear指向最后元素
    6、数据元素出队(DeLinkQueue)
    7、遍历整个链式队列数据元素(PrintLinkQueue)

    2、判定链式队列是否为空
    由于单链表的属性,链式队列几乎不会出现“队列已满”的情况,因此不考虑判定链式队列是否已满的操作。
    判定链式队列是否为空,只需要判定队列的front指针是否为空即可。
    //代码见附录
    3、队列的链式存储结构——入队操作
    入队操作其实就是在链表尾部插入节点。新来的数据节点附在当前rear节点之后,并将rear节点指向该节点即可。
    //代码见附录
    4、队列的链式存储结构——出队操作
    出队操作就是将链表的头结点的后继节点出队,并将其之后的节点设置为头结点的后继节点。若链表除头结点外仅剩一个元素,则需将rear指向头结点。
    //代码见附录

    对于循环队列和链式队列的比较,二者从时间复杂度上来说都是O(1),不过链式队列需要花费额外的申请节点的时间,而且链式队列删除节点也需要一些时间。从空间上来说,循环队列有固定长度,就意味着循环队列有其存储上限,因此也就存在元素溢出以及空间浪费等问题,而链式队列则不存在这些问题。
    总体来说,若可以大致确定元素个数的情况下,推荐使用循环队列;若无法事先预知元素个数,则应使用链式队列。
    ===============================================================================
    ======================================================================
    展开全文
  • 队列链式存储结构,其实就是线性表的单链表,只不过只能尾进头出,简称为链队列。 将头指针指向链队列的头结点 并不front指针直接指向第一个元素。 二.链队列实现 链队列的存储结构,这里申明两个结构体,一个...

    之前使用的顺序存储的队列,但是就是哪怕是循环队列,也可能会遇到数组溢出的问题。这时,使用链式存储会是一个更好的选择。

    一.链队列

    队列的链式存储结构,其实就是线性表的单链表,只不过只能尾进头出,简称为链队列。
    将头指针指向链队列的头结点
    在这里插入图片描述
    并不是front指针直接指向第一个元素。

    二.链队列实现

    链队列的存储结构,这里申明两个结构体,一个是链表的,一个是队列的。

    typedef int QElemtype;
    typedef struct QNode{
    	QElemtype data;
    	struct QNode * next;
    }QNode,*LinkQueuePtr;
    typedef struct{
    	LinkQueuePtr front,rear;
    }LinkQueue;
    

    队列初始化:

    Status LinkQueue_Init(LinkQueue *Q)
    {
    	LinkQueuePtr q = (LinkQueuePtr)malloc(sizeof(QNode));
    	Q->front = Q->rear = q;
    	Q->front->next = NULL;
    	return OK; 
    }
    

    这里一定记得将q赋给Q->front 和Q->rear。不然后面代码运行会错误。深刻体会

    入队操作

    Status EnLinkQueue(LinkQueue *Q,QElemtype e)
    {
    	LinkQueuePtr q = (LinkQueuePtr)malloc(sizeof(QNode));
    	q->data = e;
    	q->next = NULL;
    	Q->rear->next = q;
    	Q->rear = q;
    	return OK;
    }
    

    出队操作:

    Status DeLinkQueue(LinkQueue *Q,QElemtype *e )
    {
    	LinkQueuePtr p;
    	if(Q->front == Q->rear)
    		return ERROR;
    	p = Q->front->next;
    	*e = p->data;
    	Q->front->next = p->next;
    	if(Q->rear == p)
    		Q->front = Q->rear;
    	printf("%d  ",p->data);
    	free(p);
    	return OK;
    }
    
    

    这些操作都和单链表操作类似,就是断链,挂链。然后记得出队是操作front,入队是操作rear。
    实现代码

    #include<stdio.h>
    #include<stdlib.h>
    
    #define OK 1
    #define ERROR 0
    typedef int Status;
    typedef int QElemtype;
    typedef struct QNode{
    	QElemtype data;
    	struct QNode * next;
    }QNode,*LinkQueuePtr;
    typedef struct{
    	LinkQueuePtr front,rear;
    }LinkQueue;
    
    Status LinkQueue_Init(LinkQueue *Q)
    {
    	LinkQueuePtr q = (LinkQueuePtr)malloc(sizeof(QNode));
    	Q->front = Q->rear = q;
    	Q->front->next = NULL;
    	return OK; 
    }
    
    Status EnLinkQueue(LinkQueue *Q,QElemtype e)
    {
    	LinkQueuePtr q = (LinkQueuePtr)malloc(sizeof(QNode));
    	q->data = e;
    	q->next = NULL;
    	Q->rear->next = q;
    	Q->rear = q;
    	return OK;
    }
    
    
    Status DeLinkQueue(LinkQueue *Q,QElemtype *e )
    {
    	LinkQueuePtr p;
    	if(Q->front == Q->rear)
    		return ERROR;
    	p = Q->front->next;
    	*e = p->data;
    	Q->front->next = p->next;
    	if(Q->rear == p)
    		Q->front = Q->rear;
    	printf("%d  ",p->data);
    	free(p);
    	return OK;
    }
    
    int main(void)
    {
    	LinkQueue Q;
    	QElemtype e;
    	LinkQueue_Init(&Q);
    	EnLinkQueue(&Q,1293);
    	EnLinkQueue(&Q,3293);
    	EnLinkQueue(&Q,32293);
    	EnLinkQueue(&Q,12393);
    	DeLinkQueue(&Q,&e);
    	return 0;
    }
    

    三.结束

    链队列的入队和出队在时间复杂度上都是O(1)。但是在申请和释放结点会有一定开销。
    在确定队列长度最大值情况下,选择循环队列。无法确定时,用链队列。

    展开全文
  • 比起循环队列,队列的链式存储结构是非常好理解的。其基本思路与建立链式线性表基本想同,详细资料请参考笔者前文。不同的,链式队列需要一个头指针和尾指针,方便进行压入(push)与弹出(pop)操作。此处设立了...
  •   队列(Queue) 简称队,也一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。向队列中插入元素称为入队或进队。删除元素称为出队或离队。这和我们日常生活中的排队一致的,最早排队的...
  • 本文主要描述如何使用链式存储结构来模拟实现队列(包括循环队列链表)。使用链式存储结构的好处,入队列节点元素不受客观约束限制,只要内存空间足够,就可以无限制的动态申请内存地址空间。但是它也存在缺点,比如...
  • 文章目录1. 概述2. 队列的链式存储2.1 链式队列初始化...本文主要描述如何使用链式存储结构来模拟实现队列(包括循环队列链表)。     使用链式存储结构的好处,入队列节点元素不受客观约束限制,只要内存空间足
  • 1. 链队列的特点: 链队列其实就是单链表,只不过它...2. Java使用数组实现循环队列:  //结点类,包含结点的数据和指向下一个节点的引用 public class Node { private E data; // 数据域 private Node next; /
  • 对于循环队列,也就是队列的顺序存储结构,面临着数组可能溢出的问题,所以还需要研究一下不需要担心队列长度的链式存储结构循环队列的插入和删除时间复杂度都不高都O(1),不需要移动队列里面的元素。 #...
  • 本文主要描述如何使用链式存储结构来模拟实现队列(包括循环队列链表)。使用链式存储结构的好处,入队列节点元素不受客观约束限制,只要内存空间足够,就可以无限制的动态申请内存地址空间。但是它也存在缺点,比如...
  • 本文主要描述如何使用链式存储结构来模拟实现队列(包括循环队列链表)。使用链式存储结构的好处,入队列节点元素不受客观约束限制,只要内存空间足够,就可以无限制的动态申请内存地址空间。但是它也存在缺点,...
  • 单向循环队列是基于链表实现的但是,与链表不同的是,此单向循环队列的头尾相连,即尾指针的后继是头结点。 空表状态 此单向循环队列采用真实头结点,所以此队列为空时head,rear均指向空。 public boolean ...
  • 队列链式存储结构是在线性表链式存储基础上,添加了两个指针:头指针(front)和尾指针(rear)。front指向链表的头结点,而rear指向链表的最后一个节点。当front与rear指针重合时即front = rear时,我们就认为...
  • https://blog.csdn.net/xy010902100449/article/details/46563643 数据结构和算法 ... 【摘要】前一篇博客主要讨论循环队列,但是循环队列事先申请好空间,使用期间不能释放的。但是链队列,每次都可以...
  • 今天来给大家讲解,采用链式存储结构的栈和队列,以及循环链表。 链式栈 对于栈,就是采用先进后出,后进先出的结构,之前已经讲过采用顺序存储结构的栈,本次要说的采用链式存储的栈。 **通过LinkedList来进行进....
  • 链式存储结构中栈、队列循环链表,都在上篇的单链表基础上进行实现的。话不多说先看链式存储的栈。 栈 先看一下的类图: 接下来实现: public class LinkedStack<E> implements Stack<E>{ ...
  • 【摘要】前一篇博客主要讨论循环队列,但是循环队列事先申请好空间,使用期间不能释放的。但是链队列,每次都可以进行申请和释放结点。再无法预估队列长度的时候,我们可以考虑用链队列。 (1)设计队列数据...
  • 对于队列(Queue)什么,再次不再赘述,与链表、栈的实现一样,队列作为一种特殊的线性表,也存在顺序存储以及链式存储两种方式。 顺序存储的队列 采用顺序存储的方式来存储队列,最简单的方式对于n个元素的...
  • 生活中的队列相当于顺序存储队列,在火车站排队买票,前面的人买完票走了,后面的人一个一个往前移一位,这很正常的事情,而计算机中队列队列第一个元素出去了,后面的元素一个一个往前移,这一件很降低效率的...
  • 上一节我们说了关于线性表的链式存储结构的实现,今天的栈也建立在线性表的基础上 栈的特性:先进后出 1.删除时(出栈):我们考虑时间复杂度时发现:删除时的头删的复杂度为O(1),而尾删的时间复杂度为O(n),...
  • 在介绍用顺序表实现栈结构的时候,已经对栈进行了一个完整的介绍,关于用结点去实现一个栈结构在Java基础的文章中也已经介绍过了,请参照文章( https://blog.csdn.net/weixin_45432742/article/details/99850913)...
  • 队列 队列是只能在一端插入,另一端删除元素的线性表。 特性:先进先出 队列术语 队列的基本运算 (1)初始化 :设置队列为空。 (2)判断队列为空: 若为空,则返回TRUE,否则返回FALSE. ...存储结构为两种:顺序+链式
  • 队列是一种先进先出的数据结构,分顺序存储结构和链式存储结构两种。顺序存储结构中广泛使用的是循环队列,也是队列使用中最多的一种。下面将分别实现这两种队列的基本操作。 #include<iostream> using ...
  • 本文主要描述如何使用链式存储结构来模拟实现队列(包括循环队列链表)。使用链式存储结构的好处,入队列节点元素不受客观约束限制,只要内存空间足够,就可以无限制的动态申请内存地址空间。但是它也存在缺点,...
  • 数据结构的C++实现之队列-链式队列 注:本文为清华大学计算机系列教材《数据结构》-殷人昆-第2版的学习笔记队列的概念队列... 链式队列链式队列是队列基于单链表的一种存储表示.在单链表的每一个结点中有两个域:dat...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 462
精华内容 184
关键字:

循环队列是链式存储结构