Datastructures-队列

先进先出的数据结构，很常用

▶

STL queue

#include<iostream>
#include<queue>
using namespace std;
int main(){
	queue<int> Q;
	printf("入队5\n"); 
	Q.push(5);
	printf("入队4\n"); 
	Q.push(4);
	printf("入队3\n"); 
	Q.push(3);
	printf("出队%d\n",Q.front());
	Q.pop();
	printf("出队%d\n",Q.front());
	Q.pop();
	printf("出队%d\n",Q.front());
	Q.pop();
	return 0;
} 

举个栗子：

▶

洛谷P1540

https://www.luogu.com.cn/problem/P1540

#include<bits/stdc++.h>
using namespace std;
int m,n;
int countt = 0;
int que[10000];
int head;
int tail;
map<int,int>mapp;
int main()
{
	cin >> m >> n;
	head = tail = 0;
	for(int i = 1;i <= n;++ i)
	{
		int c;cin >> c ;
		if(mapp.count(c))
		{
			continue;
		}
		if(tail - head + 1 <= m)
		{	
			countt ++ ;
			que[tail] = c;
			tail ++ ;
			mapp[c] = 1;
		}else{
			countt ++ ;
			que[tail] = c;
			tail ++ ;
			mapp[c] = 1;
			mapp.erase(que[head]);
			head ++ ;
		}
	}
	cout << countt << endl;
	
	return 0;
}
//数组模拟队列+map实现哈希表

▶

循环队列的顺序存储实现

#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef int ElementType;
typedef struct QNode *Queue;
struct QNode{
	ElementType Data[MaxSize];
	int front;   // 记录队头 
	int rear;    // 记录队尾 
};

Queue CreateQueue();  // 初始化队列 
void AddQ(Queue Q,ElementType item);  //  入队
int IsFull(Queue Q); // 判断队列是否已满 
ElementType DeleteQ(Queue Q);  // 出队 
int IsEmpty(Queue Q); // 判断队列是否为空 

// 初始化 
Queue CreateQueue(){
	Queue Q;
	Q = (Queue)malloc(sizeof(struct QNode));
	Q->front = -1;
	Q->rear = -1;
	return Q;
} 

// 判断队列是否已满
int IsFull(Queue Q){
 	return ((Q->rear+1) % MaxSize == Q->front);
}

// 入队 
void AddQ(Queue Q,ElementType item){
	if(IsFull(Q)){
		printf("队列满");
		return;
	}else{ 
		Q->rear = (Q->rear+1) % MaxSize;
		Q->Data[Q->rear] = item; 
	}
}

//判断队列是否为空
int IsEmpty(Queue Q){
	return (Q->front == Q->rear);
}
 
// 出队
ElementType DeleteQ(Queue Q){
	if(IsEmpty(Q)){
		printf("队列空");
		return 0;
	}else{
		Q->front = (Q->front+1) % MaxSize;
		return Q->Data[Q->front];
	}
} 

int main(){
	Queue Q;
	Q = CreateQueue();
	AddQ(Q,3);
	printf("3入队\n");
	AddQ(Q,5);
	printf("5入队\n");
	AddQ(Q,11);
	printf("11入队\n");
	printf("%d出队\n",DeleteQ(Q));
	printf("%d出队\n",DeleteQ(Q));
	return 0;
} 

▶

队列的链式存储实现

#include<stdio.h>
#include<malloc.h>
typedef int ElementType;
typedef struct QNode *Queue;
struct Node{
	ElementType Data;
	struct Node *Next;
};
struct QNode{
	struct Node *rear;    // 指向队尾结点 
	struct Node *front;   // 指向队头结点 
};

Queue CreateQueue();  // 初始化队列 
void AddQ(Queue Q,ElementType item);  //  入队
ElementType DeleteQ(Queue Q);  // 出队 
int IsEmpty(Queue Q); // 判断队列是否为空 

// 初始化 
Queue CreateQueue(){
	Queue Q;
	Q = (Queue)malloc(sizeof(struct QNode));
	Q->front = NULL;
	Q->rear = NULL;
	return Q;
}

// 是否为空 
int IsEmpty(Queue Q){
	return (Q->front == NULL);
}

// 入队
void AddQ(Queue Q,ElementType item){
	struct Node *node;
	node = (struct Node *)malloc(sizeof(struct Node));
	node->Data = item;
	node->Next = NULL;
	if(Q->rear==NULL){  //此时队列空 
		Q->rear = node;
		Q->front = node;
	}else{ //不为空 
		Q->rear->Next = node;  // 将结点入队 
		Q->rear = node;   // rear 仍然保持最后 
	}
} 

// 出队
ElementType DeleteQ(Queue Q){
	struct Node *FrontCell;
	ElementType FrontElem;
	if(IsEmpty(Q)){
		printf("队列空");
		return 0;
	}
	FrontCell = Q->front;
	if(Q->front == Q->rear){ // 队列中只有一个元素 
		Q->front = Q->rear = NULL; 
	}else{
		Q->front = Q->front->Next;
	}
	FrontElem = FrontCell->Data;
	free(FrontCell);
	return FrontElem;
}

int main(){
	Queue Q;
	Q = CreateQueue();
	printf("入队5\n"); 
	AddQ(Q,5);
	printf("入队4\n"); 
	AddQ(Q,4);
	printf("入队3\n"); 
	AddQ(Q,3);
	printf("出队%d\n",DeleteQ(Q));
	printf("出队%d\n",DeleteQ(Q));
	printf("出队%d\n",DeleteQ(Q));
	printf("%d\n",DeleteQ(Q));
	return 0;
}