队列实现原理和应用

循环数组实现队列:

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
template<class T>
class LoopQueue
{
public:
	LoopQueue(int c );
	~LoopQueue();
public:
	bool isEmpty();
	int size();
	bool push(T t);
	bool pop();
	T front();
private:
	int capacity;
	int begin;
	int end;
	T* queue;
};
template<typename T>
LoopQueue<T>::LoopQueue(int c ) :capacity(c), begin(0), end(0), queue(nullptr)
{
	queue = new T[capacity];
}
template<typename T>
LoopQueue<T>::~LoopQueue()
{
	delete[]queue;
}
template<typename T>
bool LoopQueue<T>::isEmpty()
{
	if (begin == end)
	{
		return true;
	}
	return false;
}
template<typename T>
int LoopQueue<T>::size()
{
	return (end - begin + capacity) % capacity;
}
template<typename T>
bool LoopQueue<T>::push(T t)
{
	if ((end + 1) % capacity == begin)
	{
		return false;
	}
	queue[end] = t;
	end = (end + 1) % capacity;
	return true;
}
template<typename T>
bool LoopQueue<T>::pop()
{
	if (end == begin)
	{
		return false;
	}
	begin = (begin + 1) % capacity;
	return true;
}
template<typename T>
T LoopQueue<T>::front()
{
	if (end == begin)
	{
		exit(0);
	}
	else
	{
		return queue[begin];
	}
}
int main()
{
	LoopQueue<string>queue(6);
	queue.push("one");
	queue.push("two");
	queue.push("three");
	queue.push("four");
	queue.push("five");
	queue.push("six");
	cout << "队列长度 " << queue.size() << endl;
	while (!queue.isEmpty())
	{
		cout << queue.front()<< endl;
		queue.pop();
	}
	getchar();
	return 0;
}

队列实现:

#include<iostream>
#include<cstring>
#include<queue>
#include<assert.h>
using namespace std;
template <class T>
class Node
{
public:
	Node<T>* next;
	T val;
	Node(T x):val(x),next(NULL){}
};
template<class T>
class Queue
{
public:
	Queue():front(NULL),rear(NULL),size(0){}
	bool empty() { return front == NULL; }
	void push(T x)
	{
		if (empty())
		{
			front = rear = new Node<T>(x);
			++size;
			return;
		}
		rear->next = new Node<T>(x);
		rear = rear->next;
		++size;
	}
	void pop()
	{
		assert(!empty());
		Node<T>* temp;
		temp = front;//删除节点 
		front= front->next;
		delete temp;
		--size;
	}
	T _front()
	{
		assert(NULL != front);
		return front->val;
	}
	int Size()
	{
		return size;
	}
private:
	Node<T>* front;
	Node<T>* rear;
	int size;
};
int main()
{
	Queue<string>q;
	q.push("我好爱编程");
	q.push("编程使我快乐");
	q.push("进入腾讯 改变命运");
	cout << q.Size() << endl;
	while (!q.empty())
	{
		cout << q._front() << endl;
		q.pop();
	}
}

应用:

题目:https://codeforces.com/contest/1399/problem/D

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int N = 2e5 + 10;
int note[N];
char s[N];
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int ans = 0;
		queue<int>q[2];
		int n;
		scanf("%d", &n);
		scanf("%s", s+1);
		for (int i = 1; i <=n; ++i)
		{
			int m = s[i] - '0';
			if (!q[m].empty())
			{
				int temp = q[m].front();
				q[m].pop();//将0或1提取出来 加入相反的数中
				note[i] = temp;
				q[m ^ 1].push(temp);
			}
			else
			{
				++ans;//如果此时不存 则新建一个序列
				q[m ^ 1].push(ans);
				note[i]=ans;
			}
		}
		printf("%d\n", ans);
		for (int i = 1; i <=n; ++i)
		{
			printf("%d%c", note[i], i == n? '\n' : ' ');
		}
	}
}