数据结构——队列

1 队列是一种只允许在表的一端插入元素，在另一端删除元素的特殊的线性表。允许插入的一端成为队尾（rear），允许删除的一端成为队头（front）。当队列中没有任何元素时成为空队列。队列是一种先进先出的线性表，简称FIFO表。

2 与栈类似，队列也是一种操作受限的特殊的线性表，同样可以采用顺序存储结构和链式存储结构来表示队列。

3 队列的顺序存储表示——循环队列

队列的顺序存储表示同样是利用一维数组来实现。为了解决“假溢出”问题，可以将队列的数组看成是头尾相接的环状空间，当队尾元素放到数组的最后一个位置时，如需入队就把新元素接着存放在数组的0下表位置，这样的队列成为循环队列。循环队列的基本操作的实现如下：

#ifndef _SQQUEUE_
#define _SQQUEUE_
template<class T>
class SqQueue
{
public:
	SqQueue(int m = 100);
	~SqQueue();
	void Clear();
	bool Empty() const;
	int Length() const;
	T& GetHead() const;
	T& GetLast() const;
	void Append(const T&);
	void Remove();
private:
	T* m_base;
	int m_front;
	int m_rear;
	int m_size;
};

template<class T> SqQueue<T>::SqQueue(int m)
{
	m_front = m_rear = 0;
	m_size = m;
	m_base = new T[m];
}

template<class T> SqQueue<T>::~SqQueue()
{
	delete [] m_base;
}

template<class T> void SqQueue<T>::Clear()
{
	m_front = m_rear = 0;
}

template<class T> bool SqQueue<T>::Empty() const
{
	return m_front == m_rear;
}

template<class T> int SqQueue<T>::Length() const
{
	return (m_rear - m_front + m_size) % m_size;
}

template<class T> T& SqQueue<T>::GetHead() const
{
	if (!Empty())
	{
		return m_base[m_front];
	}
}

template<class T> T& SqQueue<T>::GetLast() const
{
	if (!Empty())
	{
		return m_base[(m_rear - 1 + m_size) % m_size];
	}
}

template<class T> void SqQueue<T>::Append(const T& e)
{
	int i,j;
	if (m_front == (m_rear + 1) % m_size)
	{
		T* newbase = new T[m_size + 10];
		for (i = m_front,j = 0; i < m_rear; i = (i + 1) % m_size, j++)
		{
			newbase[j] = m_base[i];
		}
		delete [] m_base;
		m_base = newbase;
		m_front = 0;
		m_rear = j;
		m_size += 10;
	}
	m_base[m_rear] = e;
	m_rear = (m_rear + 1) % m_size;
}

template<class T> void SqQueue<T>::Remove()
{
	if (!Empty())
	{
		m_front = (m_front + 1) % m_size;
	}
}
#endif

在循环队列中，上述基本操作的时间复杂度均为O(1)。

4 队列的链式存储表示——链队列

#ifndef _LINKQUEUE_
#define _LINKQUEUE_
template<class T>
class LinkQueue
{
public:
	LinkQueue();
	~LinkQueue();
	void Clear();
	bool Empty() const;
	int Length() const;
	T* GetHead() const;
	T* GetLast() const;
	void Append(const T&);
	void Remove();
private:
	LinkNode<T>* m_front;
	LinkNode<T>* m_rear;
};

template<class T> LinkQueue<T>::LinkQueue()
{
	m_front = m_rear = new LinkNode<T>;
	m_front->next = NULL;
}

template<class T> LinkQueue<T>::~LinkQueue()
{
	Clear();
	delete m_front;
}

template<class T> void LinkQueue<T>::Clear()
{
	LinkNode<T>* p;
	while (m_front->next != NULL)
	{
		p = m_front->next;
		m_front->next = p->next;
		delete p;
	}
	m_rear = m_front;
}

template<class T> bool LinkQueue<T>::Empty() const
{
	return m_front == m_rear;
}

template<class T> int LinkQueue<T>::Length() const
{
	int i = 0;
	LinkNode<T>* p = m_front;
	while (p->next != NULL)
	{
		i++;
		p = p->next;
	}
	return i;
}

template<class T> T& LinkQueue<T>::GetHead() const
{
	while(!Empty())
	{
		return m_front->next->data;
	}
}

template<class T> T& LinkQueue<T>::GetLast() const
{
	while(!Empty())
	{
		return m_rear->data;
	}
}

template<class T> void LinkQueue<T>::Append(const T& e)
{
	LinkNode<T>* p = new LinkNode<T>;
	p->data = e;
	p->next = NULL;
	m_rear->next = p;
	m_rear = p;
}

template<class T> void LinkQueue<T>::Remove()
{
	LinkNode<T>* p;
	if (!Empty())
	{
		p = m_front->next;
		m_front->next = p->next;
		if (p == m_rear)
		{
			m_rear = m_front;
		}
		delete p;
	}
}
#endif
链队列的队空条件为front = rear,或者front->next = NULL，而队满只在内不能无可用空间时才发生，所以链队列特别适合于队列元素个数变化比较大的情况。
在链队列的操作中，队列的销毁、清空和求长度操作的时间复杂度为O(n)，因为需要对链表的每个结点进行处理。队列的其余操作的时间复杂度为O(1)。
5 队列的应用
5.1 舞伴问题
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。
#include <iostream>
#include <fstream>
#include "SqQueue.h"
using namespace std;

struct Dancer
{
	char name[20];
	char sex;
};

void main(int argc, char* argv[])
{
	ifstream input("input.txt");
	SqQueue<Dancer> M(50), F(50);
	Dancer d;
	input>>d.name>>d.sex;
	while (d.sex != '#')
	{
		if (d.sex == 'M' || d.sex == 'm')
		{
			M.Append(d);
		}
		else if (d.sex == 'F' || d.sex == 'f')
		{
			F.Append(d);
		}
		input>>d.name>>d.sex;
	}

	while (!M.Empty() && !F.Empty())
	{
		Dancer d = M.GetHead();
		M.Remove();
		cout<<d.name<<" ";
		Dancer d2 = F.GetHead();
		F.Remove();
		cout<<d2.name<<endl;
	}

	if (!M.Empty())
	{
		cout<<"依然还有"<<M.Length()<<"男舞者在等待"<<endl;
		cout<<M.GetHead().name<<"最先获得舞伴"<<endl;
	}
	else if (!F.Empty())
	{
		cout<<"依然还有"<<F.Length()<<"女舞者在等待"<<endl;
		cout<<F.GetHead().name<<"最先获得舞伴"<<endl;
	}
	else
	{
		cout<<"没有等待的舞者！"<<endl;
	}
	system("pause");
}

5.2 火车车厢重排问题
一列货运列车共有 n 节车厢，每节车厢将停放在不同的车站。假定 n 个车站的编号分别为 1 ~ n ，即货运列车按照第 n 站至第 1 站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只需卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列他们。
车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和 k 个缓冲轨，缓冲轨位于入轨和出轨之间。假定 缓冲轨按先进先出的方式运作，设计算法解决火车车厢重排问题。
TrackStation.h

#include "SqQueue.h"
#pragma once
class CTrackStation
{
public:
	CTrackStation(int trackCount);
	~CTrackStation(void);
	bool Realign(int* A, int n);
private:
	bool HoldIn(int car);
	bool HoldOut(int car);

	SqQueue<int>* m_pTracks;
	int m_trackCount;
};


TrackStation.cpp<pre name="code" class="cpp">#include "TrackStation.h"
#include <iostream>

CTrackStation::CTrackStation(int trackCount):m_trackCount(trackCount)
{
	m_pTracks = new SqQueue<int>[m_trackCount];
}

CTrackStation::~CTrackStation(void)
{
	delete [] m_pTracks;
}

bool CTrackStation::HoldIn(int car)
{
	int bestTrack = -1;
	int bestLast = -1;
	int i;
	for (i = 0; i < m_trackCount; i++)
	{
		if (!m_pTracks[i].Empty())
		{
			int last = m_pTracks[i].GetLast();
			if (car > last && last > bestLast)
			{
				bestTrack = i;
				bestLast = last;
			}
		}
	}

	if (bestTrack == -1)
	{
		for (i = 0; i < m_trackCount; i++)
		{
			if (m_pTracks[i].Empty())
			{
				bestTrack = i;
				break;
			}
		}
	}

	if (bestTrack == -1)
	{
		return false;
	}
	m_pTracks[bestTrack].Append(car);
	std::cout<<car<<"号车厢进入"<<bestTrack<<"号缓冲轨"<<std::endl;
	return true;
}

bool CTrackStation::HoldOut(int car)
{
	for (int i = 0; i < m_trackCount; i++)
	{
		if (!m_pTracks[i].Empty())
		{
			int headCar = m_pTracks[i].GetHead();
			if (headCar == car)
			{
				headCar =m_pTracks[i].GetHead();
				m_pTracks[i].Remove();
				std::cout<<headCar<<"号车厢从"<<i<<"号缓冲轨出站"<<std::endl;
				return true;
			}
		}
	}
	return false;
}

bool CTrackStation::Realign(int* A, int n)
{
	int nowOut = 1, i = 0;
	while (nowOut <= n)
	{
		if (HoldOut(nowOut))
		{
			nowOut++;
			continue;
		}
		if (i >= n || !HoldIn(A[i]))
		{
			return false;
		}
		i++;
	}
	return true;
}




Main.cpp<pre name="code" class="cpp">#include <iostream>
#include <fstream>
#include "TrackStation.h"
using namespace std;

void main(int argc, char* argv[])
{
	int k;
	cout<<"请输入缓冲轨数目：";
	ifstream input("input.txt");
	input>>k;
	CTrackStation trackStation(k);
	cout<<"请依次输入入轨的车厢次序，以0结束：";
	int car, n = 0, A[100];
	input>>car;
	while(car > 0 && n < 100)
	{
		A[n++] = car;
		input>>car;
	}
	if (!trackStation.Realign(A,n))
	{
		cout<<"车厢无法重排!"<<endl;
	}
	system("pause");
}


转载：http://blog.csdn.net/foreverling/article/details/43153389
				


				
时间： 2024-12-31 11:35:31

		
		


		


	

	
	

		


		
数据结构——队列的相关文章


						

		

			

                PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例
			

		

		

									

				  这篇文章主要介绍了PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例,需要的朋友可以参考下 队列这种数据结构更简单,就像我们生活中排队一样,它的特性是先进先出(FIFO). PHP SPL中SplQueue类就是实现队列操作,和栈一样,它也可以继承双链表(SplDoublyLinkedList)轻松实现. SplQueue类摘要如下: SplQueue简单使用如下: 代码如下: $queue = new SplQueue(); /** * 可见			

		

	

				

		

			

                链表-关于数据结构队列问题
			

		

		

									

				问题描述 关于数据结构队列问题 2C 用队列做一个模拟抢红包的小程序,但现在还没有思路,望前辈不吝啬赐教之,谢谢. 解决方案 数据结构之队列数据结构--队列实现舞伴配对问题数据结构-栈和队列			

		

	

				

		

			

                PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例_php实例
			

		

		

									

				队列这种数据结构更简单,就像我们生活中排队一样,它的特性是先进先出(FIFO). PHP SPL中SplQueue类就是实现队列操作,和栈一样,它也可以继承双链表(SplDoublyLinkedList)轻松实现. SplQueue类摘要如下: SplQueue简单使用如下: 复制代码 代码如下: $queue = new SplQueue();   /**  * 可见队列和双链表的区别就是IteratorMode改变了而已,栈的IteratorMode只能为:  * (1)SplDoublyL			

		

	

				

		

			

                &lt;数据结构&gt; 队列[转]
			

		

		

									

				队列(queue)是一个简单而常见的数据结构.队列也是有序的元素集合.队列最大的特征是First In, First Out (FIFO,先进先出),即先进入队列的元素,先被取出.这一点与栈(stack)形成有趣的对比.队列在生活中很常见,排队买票.排队等车-- 先到的人先得到服务并离开队列,后来的人加入到队列的最后.队列是比较公平的分配有限资源的方式,可以让队列的人以相似的等待时间获得服务.   队列支持两个操作,队首的元素离开队列(dequeue),和新元素加入队尾(enqueue). 队列			

		

	

				

		

			

                [数据结构] 队列
			

		

		

									

				队列 队列是一种操作受限制的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作.进行插入操作的端称为队尾,进行删除操作的端称为队头.  队列中没有元素时,称为空队列.在队列这种数据结构中,最先插入的元素将是最先被删除的元素:反之最后插入的元素将是最后被删除的元素,因此队列又称为"先进先出"(FIFO-first in first out)的线性表. 队列空的条件:front=rear 队列满的条件: rear = MAXSIZE 顺序队列 建立顺			

		

	

						

		

			

                JAVA数据结构--队列及优先队伍
			

		

		

									

				注意优先队列在插入时已排序.故在删除,不是以原始插入数据为顺序的. 还要了解两种队列的优点缺少,适合应用的场合... 1 class Queue 2 { 3 private int maxSize; 4 private long[] queArray; 5 private int front; 6 private int rear; 7 private int nItems; 8 9 public Queue(int s) 10 { 11 maxSize = s; 12 queArray = n			

		

	

				

		

			

                数据结构---队列C语言实现
			

		

		

									

				#include <stdio.h> #include <stdlib.h> //队列大小 #define SIZE 1024 static int queue[SIZE] = {0}; static int head , tail ; //0 1 int Is_Empty(void) { //判断队列是否为空,如果头是尾,就证明为空 return head == tail ; } //0 1 int Is_Full(void) { //判断队列是否已经满了 return (hea			

		

	

				

		

			

                浅谈算法和数据结构 一 栈和队列
			

		

		

									

				最近晚上在家里看Algorithems,4th Edition,我买的英文版,觉得这本书写的比较浅显易懂,而且"图码并茂",趁着这次机会打算好好学习做做笔记,这样也会印象深刻,这也是写这一系列文章的原因.另外普林斯顿大学在Coursera 上也有这本书同步的公开课,还有另外一门算法分析课,这门课程的作者也是这本书的作者,两门课都挺不错的. 计算机程序离不开算法和数据结构,本文简单介绍栈(Stack)和队列(Queue)的实现,.NET中与之相关的数据结构,典型应用等,希望能加深自己对这			

		

	

				

		

			

                Python实现的数据结构与算法之队列详解_python
			

		

		

									

				本文实例讲述了Python实现的数据结构与算法之队列.分享给大家供大家参考.具体分析如下: 一.概述 队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行. 二.ADT 队列ADT(抽象数据类型)一般提供以下接口: ① Queue() 创建队列 ② enqueue(item) 向队尾插入项 ③ dequeue() 返回队首的项,并从队列中删除该项 ④ empty() 判断队列是否为空 ⑤ size() 返回队列中项的个数 队