第8次课队列 A

文章摘要：本文主要介绍了栈和队列的基本概念及其操作。栈是一种遵循“先进后出”原则的数据结构，操作包括入栈、出栈、显示栈顶元素等。通过示例展示了栈的操作过程，并提出了相关问题。队列则是一种“先进先出”的数据结构，操作包括入队、出队、获取队首元素等。文章通过多个编程题目进一步讲解了队列的实现和应用，如模拟舞会配对、破解密码等。最后，文章列出了课后作业题目，供读者进一步练习和巩固所学知识。

mochensage

485人浏览 · 2025-05-18 01:15:55

mochensage · 2025-05-18 01:15:55 发布

课前复习

什么是栈

数据的操作只从一端完成，如存、取等；
数据存放遵循，先进后出，后进先出的原则；

栈的操作

入栈、出栈；
栈顶元素、栈底元素、空栈、满栈：
判断出栈顺序

栈的实现

栈的初始化
入栈函数
出栈函数
显示栈顶元素
清空栈

有一个空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈、进栈、
出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为()
A.f
B.c
C.a
D.b

课堂学习

队列的概念

总结队列特点

1)具有两个端口的容器，一个端口负责进，另一个端口负责出。
2)数据存取特点：先进先出。

队列的操作

练一练

【NOIP2003】已知队列（13,2,11,34,41,77,5,7,18,26,15)，第一个进入队
列的元素是13，则第五个出队列的元素是（)。
A.5
B.41
C.77
D.13

小总结

队列的实现

入队操作

获取队首元素

出队操作

队列的长度


#include<iostream>
using namespace std;
int q[5];
int front, rear;
void push(int x) {  //入队函数
    if (rear < 5) {
        q[rear] = x;
        rear++;
    }
}
void pop() {  //出队函数
    if (front != rear) {
        front++;
    }
}
int getFront() {  //获取队首元素
    return q[front];
}
int size() {  //获取队列中元素个数
    return rear - front;
}
int main() {
    return 0;
}

课堂训练

4144 队列的操作

描述

输入5个整数，将这5个整数进行入队，接下来做三次出队操作，按照出队顺序输出出队元素，以上操作完成后输出此时的队首元素。

输入描述

输入5个整数，用空格隔开。

输出描述

输出2行，第1行输出出队元素，按照出队顺序输出，用空格隔开。
第2行输出完成出队操作后的队首元素。

样例输入 1

4 9 12 6 7

样例输出 1

4 9 12
6

提示

数据范围与提示

1≤整数≤1000

#include<iostream>
using namespace std;
int q[5];//初始化队列
int front=0,rear=0;
void push(int x){//入队函数
	if(rear<5){
		q[rear]=x;
		rear++;
	}
}
void pop(){//出队函数
	if(front != rear){
		front++;
	}
}
int Front(){//获取队首元素
	return q[front];
}
int main(){
	int num;
	for(int i=1;i<=5;i++){
		cin>>num;
		push(num);//num值入队
	}
	//出队并输出出队元素
	for(int i=1;i<=3;i++){
		cout<<Front()<<" ";//输出队首元素
		pop();//出队操作
	}
	cout<<endl<<Front();//输出队首元素
	return 0;
}

2848 密码升级

描述

密码是八位数字，密码由生日作为基数，生成密码的规则如下：
1 将第1个数字删除，第2个数字放到数字末端，再将第3个数字放到数字末端。
2 将第一步一直执行，直到所有数字删除完毕。
3 删除的数字将会组成一串新的数字，这就是密码。

输入描述

一行，一组八位数字。

输出描述

一行，八位数字生成的密码。

样例输入 1

20230206

样例输出 1

23026200

#include<bits/stdc++.h>
using namespace std;
char q[24],a[8];//q:队列 a:生日
int front,rear;
void push(char x){//入队操作
	if(rear<24){
		q[rear]=x;
		rear++;
	}
}
void pop(){//出队操作
	if(front!=rear){
		front++;
	}
}
char getFront(){//获取队首元素
	return q[front];
}
int size(){//队列中元素个数
	return rear-front;
}
int main(){
	cin>>a;//读入生日
	for(int i=0;i<strlen(a);i++){
		push(a[i]);//入队操作
	}
	int k=1;//报数
	while(size()!=0){//队列不为空
		if(k%2!=0){//判断要报数字奇偶
			cout<<getFront();//输出队首元素
			pop();//出队操作
		}else{
			push(getFront());//队首元素进入队尾
			pop();//出队操作
			push(getFront());//队首元素进入队尾
			pop();//出队操作
		}
		k++;//下次要报的数字
	}
	return 0;
}

1628 排队问题

描述

有 n 个人排队，每个人有一个编号 i（ 1 ≤ i ≤ n ）,从左往右“ 1，2，1，2，…”报数，报到“ 1 ”的人出列，数到“ 2 ”的人立即占到队伍的最右端。报数过程反复进行，直到 n 个人都出列为止。已知 n个人原来的顺序，请写出他们的出列顺序。

输入描述

第一行为 n（ n≤100 ），第二行为 n 个编号 i（ 1≤i≤n），且 i 不会重复。

输出描述

一行，为他们的出列编号。

样例输入 1

8
1 2 3 4 5 6 7 8

样例输出 1

1 3 5 7 2 6 4 8

样例输入 2

4
2 5 1 3

样例输出 2

2 1 5 3

#include<iostream>
using namespace std;
int q[200],front,rear;
void push(int x){//入队函数
	if(rear<200){
		q[rear]=x;
		rear++;
	}
}
void pop(){//出队操作
	if(front!=rear){
		front++;		
	}
}
int getFront(){//获取队首元素
	return q[front];
}
int size(){//获取队列中元素个数
	return rear-front;
}
int main(){
	int n,num;//n个人排队 num:编号
	cin>>n;
	for(int i=1;i<=n;i++){//n次入队操作
		cin>>num;
		push(num);//入队操作
	}
	int k=1;//报数
	while(size()!=0){
		if(k%2!=0){//k为奇数
			cout<<getFront()<<' ';//输出队首元素
			pop();//出队操作
		}else{
			push(getFront());//队首元素进入队尾
			pop();//出队操作
		}
		k++;//要报的数字
	}
	return 0;
}

6000 破解密码

描述

密码是八位数字，密码由生日作为基数，生成密码的规则如下：

将第1个数字删除，第2个数字放到数字序列末端。
重复执行第一步，直到所有数字删除完毕。
删除的数字将会组成一串新的数字，这就是密码。

输入描述

一行，一组八位数字。

输出描述

一行，八位数字生成的密码。

样例输入 1

20230206

样例输出 1

22000236

#include<bits/stdc++.h>
using namespace std;
char q[16],a[8];
int front=0,rear=0;
void push(char x){//入队函数
	if(rear<16){
		q[rear]=x;
		rear++;
	}
}
void pop(){//出队操作
	if(front!=rear){
		front++;		
	}
}
char getFront(){//获取队首元素
	return q[front];
}
int size(){//获取队列中元素个数
	return rear-front;
}
int main(){
	cin>>a;
	for(int i=0;i<strlen(a);i++){
		push(a[i]);
	}
	int k=1;
	while(size()!=0){
		if(k%2!=0){
			cout<<getFront();//输出队首元素
			pop();//出队操作
		}else{
			push(getFront());//队首元素进入队尾
			pop();//出队操作
		}
		k++;
	}
	return 0;
}

2849 舞会

描述

学校举办了一场舞会，男生和女生在入场时，各自排成一队。伴奏响起时，依次从男队和女队的队首各出一人配成舞伴。规定每个舞曲只有一对跳舞者，若两队初始人数不同，则较长的那一队中未配对者等待下一轮舞曲。请利用程序模拟这个过程。

输入描述

一行，三个数字x，y和n，分别表示男队人数、女队人数和舞曲数目。（1<x,y,n<1000）

输出描述

n行，每行两个数字，表示第i首舞曲的男女配对编号。（男生编号在前，女生编号在后，用一个空格隔开）

样例输入 1

3 5 9

样例输出 1

样例输入 2

3 2 4

样例输出 2

#include<iostream>
using namespace std;
int boys[2000],girls[2000];//boys:男队 girls:女队
int front1=0,rear1;//男队的队首与队尾
int front2,rear2;//女队的队首与队尾
//男队的入队函数
void push1(int x){
	if(rear1<2000){
		boys[rear1]=x;
		rear1++;
	}
}
//男队的出队函数
void pop1(){
	if(front1!=rear1)
		front1++;
}
//获取男队队首元素
int getFront1(){
	return boys[front1];
}
//女队的入队函数
void push2(int x){
	if(rear2<2000){
		girls[rear2]=x;
		rear2++;
	}
}
//女队的出队函数
void pop2(){
	if(front2!=rear2)
		front2++;
}
//获取女队队首元素
int getFront2(){
	return girls[front2];
}
int main(){
	int x,y,n;//x:男队人数 y:女队人数 n:舞曲数目
	cin>>x>>y>>n;
	for(int i=1;i<=x;i++){//男队编号1~x
		push1(i);//入队函数
	}
	for(int i=1;i<=y;i++){//女队编号1~y
		push2(i);//入队函数
	}
	for(int i=1;i<=n;i++){//循环n次
		cout<<getFront1()<<' '<<getFront2()<<endl;//输出两个队伍的队首元素
		push1(getFront1());//男队的队首元素重新入队
		push2(getFront2());//女队的队首元素重新入队
		pop1();//男队出队操作
		pop2();//女队出队操作
	}
	return 0;
}