数据结构之队列

数据结构之队列

先进先出  FIFO : first in first out
队列形式分:普通队列、环形队列
队列用途:自动排号机
环形队列实现
/*
 * MyQueue.h
 *      Author: libo
 */

#ifndef MYQUEUE_H_
#define MYQUEUE_H_

class MyQueue {
public:
	// C++
	MyQueue(int queueCapacity);	// 创建队列
	virtual ~MyQueue();			// 销毁队列
	void ClearQueue();			// 清空队列
	bool QueueEmpty() const;	// 判断是否为空队列
	bool QueueFull() const;		// 判断队列是否满了
	int QueueLength() const;	// 队列长度
	bool EnQueue(int element);	// 新元素入队
	bool DeQueue(int &element); // 首元素出队
	void QueueTraverse();		// 遍历队列

private:
	int *m_pQueue;	// 队列数组指针
	int m_iQueueLen; // 队列元素个数
	int m_iQueueCapacity; // 队列数组容量
	int m_iHead;	// 队头
	int m_iTail;	// 队尾

};

#endif /* MYQUEUE_H_ */


/*
 * MyQueue.cpp
 *      Author: libo
 */

#include <iostream>
#include "MyQueue.h"
using namespace std;

MyQueue::MyQueue(int queueCapacity) {

	m_iQueueCapacity = queueCapacity;
	m_iHead = 0;
	m_iTail = 0;
	m_iQueueLen = 0;
	m_pQueue = new int[queueCapacity];	// 从堆中申请内存,初始化队列大小


}

MyQueue::~MyQueue() {
	delete []m_pQueue;
	m_pQueue = NULL;
}

// 清空队列
void MyQueue::ClearQueue() {
	m_iHead = 0;
	m_iTail = 0;
	m_iQueueLen = 0;
}

// 判断当前队列是否为空
bool MyQueue::QueueEmpty() const {
	if (m_iQueueLen == 0) {
		return true;
	}
	return false;
}

// 队列长度
int MyQueue::QueueLength() const {
	return m_iQueueLen;
}

// 判断队列是否满了
bool MyQueue::QueueFull() const {
	if (m_iQueueLen == m_iQueueCapacity) {
		return true;
	}
	return false;
}

// 新元素入队
bool MyQueue::EnQueue(int element) {
	// 判断队里是否满了
	if (QueueFull()) {
		return false;
	}

	// 将新元素添加到队尾
	m_pQueue[m_iTail] = element;
	m_iTail++;	// 队尾指针向后移动
	m_iTail = m_iTail % m_iQueueCapacity;


	m_iQueueLen++;
	return true;

}
// 首元素出队
bool MyQueue::DeQueue(int &element) {
	// 判断队列是否为空
	if (QueueEmpty()) {
		return false;
	}


	element = m_pQueue[m_iHead];
	m_iHead++;
	m_iHead = m_iHead % m_iQueueCapacity;
	m_iQueueLen--;
	return true;
}

// 遍历队列
void MyQueue::QueueTraverse() {

	for (int i = m_iHead; i < m_iQueueLen + m_iHead; i++) {

		cout << m_pQueue[i%m_iQueueCapacity] << endl;
	}
}



#include <iostream>
#include <stdlib.h>
#include "MyQueue.h"
using namespace std;

int main(void) {

	MyQueue *p = new MyQueue(4);

	p->EnQueue(10);
	p->EnQueue(12);
	p->EnQueue(16);
	p->EnQueue(18);
	p->EnQueue(20);


	p->QueueTraverse();

	int e = 0;
	p->DeQueue(e);

	cout << endl;
	cout << e << endl; p->DeQueue(e);

	cout << endl;
	cout << e << endl;
	cout << endl; p->QueueTraverse();
	cout << endl; p->ClearQueue();
	cout << endl; p->EnQueue(20);
	p->EnQueue(30);
	p->QueueTraverse();
	cout << endl;

	delete p;
	p = NULL;
	return 0;
}

 

代码:https://github.com/cikewang/DataStructur/tree/master/MyQueue

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注