题目

目标：

• 掌握栈和队列的基本存储结构
• 熟练掌握栈和队列的基本使用
• 熟悉栈和队列的一些典型应用

任务：

1. 使用顺序存储结构来实现栈的基本操作（自行完成）。
   PTA函数题：另类堆栈、在一个数组中实现两个堆栈(考研题)

2. 学会使用STL中的stack、queue与string见参考资料Stack与Queue代码。
   完成实验任务书中的题目1—C++中的stack和queue(课上必选)。

3. 栈的应用
   使用stack编写数制转换函数(十进制转二进制=>十进制转十六进制)。
   void convertDecToBin(int x);//对十进制整数x输出其二进制值
   void convertDecToHex(int x); //对十进制整数x输出其十六进制值）。
   需考虑0、负数，请写出测试代码（课上必选）
   PTA：符号配对(考核)、表达式转换(中缀转后缀，考核) PTA(实验任务书)：字符串是否对称(回文)

4. 递归（自行完成，实验课考核加分）

   • 4.1 递归程序编写
     题目：已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：
     • 求链表中的最大整数；
     • 求链表的结点个数；
     • 求链表中所有节点数据的平均值。
     • 注意：
       1.适用于包含头结点的链表；
       2.要考虑空链表、只包含1个节点的链表的情况。
   • 4.2 使用stack将以下递归程序转化为非递归程序

     void test(int &sum)
     { 
     	int x; 
     	cin>>x; 
     	if (x==0) 
     		sum = 0;  
     	else 
     	{
     		test(sum);
     		sum+=x;
     	} 
     	cout<<sum; 
     }
     

5. 队列的应用(课上任选一)

   • PTA:银行业务队列简单模拟、舞伴问题

6. 可选

   • 实验任务书：使用队列对扑克牌排序、走迷宫。
   • PTA题目：另类循环队列(函数)

7. 特别加分

   • 使用递归或者队列实现对指定目录名及文件名进行文件查找（可使用C、C++、python实现），并在实验报告中描述该问题解决过程。

提交要求：

1. 对于要求课上完成的题目，请在实验课结束前提交代码至课堂派，并在课后完成实验报告，在实验报告中描述算法流程；
2. 对于不要求课上完成的题目，请在实验课结束后提交代码至课堂派，同时完成实验报告（描述算法流程）；
3. PTA上的题目，只需要提交测试通过即可；
4. 提交时，每道题目单独一个文件（代码），实验报告为一个word、ppt或pdf文档。

参考资料：

1. C++ STL 库快速上手
2. Python3不完全入门指南
3. Python文件系统功能
4. 递归就这么简单

实验报告

队列

建立一个队列, 入队10个任意数, 连续出队5个元素并依次输出 输出队头元素、输出队尾元素、队列中元素个数 当队列不为空时，将队列中所有元素输出 输出队列中元素个数

queue s; 

 for (int i = 0; i < 10; i++) 
     int t; cin >> t; s.push(t); 

cout << s.front() << " ";
cout << s.back() << " "; 
cout << s.size() << " "; 
cout << endl;

 for (i = 0; i < s.size(); i++) 
 {
     int front = s.front(); 
     cout << front<<" "; 
     s.pop(); 
     s.push(front); 
 } 
cout << endl; 

 cout << s.size(); 

样例输入：

1 2 3 4 5 6 7 8 9 10 

样例输出：

1 2 3 4 5 6 10 5 6 7 8 9 10 5 

小综合

输入一个字符串line，输入一个字符x。 将line中的字符依次入栈，然后输出栈中元素个数与栈顶元素。 然后将栈中元素依次出栈并输出，出栈时将不等于x的字符依次入队列。 输出队列元素个数，队头与队尾 然后输出队列中所有元素。

stack<char>s;
queue<char>q;
string line;
char x;

cin >> line;
cin >> x;

int i, n = line.size();
for (i = 0; i < n; i++)
    s.push(line[i]);
cout << s.size() << " " << s.top() << endl;

while (s.size())
{
    char top = s.top();
    s.pop();
    printf("%c", top);
    if (top != x)
        q.push(top);
}
cout << endl;

cout << q.size();
cout << q.front();
cout << q.back();
cout << endl;

for (i = 0; i < q.size(); i++)
{
    char t = q.front();
    q.pop();
    cout << t;
    q.push(t);
}
cout << endl;

样例输入：

ThisIsATest s

样例输出：

ll t 
tseTAsIsihT
8tT
teTAIihT

栈

使用stack编写数制转换函数(十进制转二进制=>十进制转十六进制)。

void convertDecToBin(int x);//对十进制整数x输出其二进制值 void convertDecToHex(int x); //对十进制整数x输出其十六进制值）。 需考虑0、负数，请写出测试代码

int num1, num2;

cin >> num1 >> num2;

convertDecToBin(num1);
convertDecToHex(num2);

void convertDecToBin(int x)
{
    stack<int>s;
    for (int i = 0; i < 32; i++)
    {
        s.push(x & 1);
        x >>= 1;
    }
    int flag = 0;
    while (s.size())
    {
        flag = 1;
        int t = s.top();
        printf("%d", s.top());
        s.pop();
    }
    if (flag == 0)
        printf("0");
    cout << endl;
}

void convertDecToHex(int x)
{
	stack<int>s;
	for (int I = 0; I < 8; i++)
	{
		s.push(x & 15);
		x >>= 4;
	}
	int flag = 0;
	while (s.size())
	{
		flag = 1;
		char ans = s.top() > 9 ? (s.top() – 10 + ‘A’) : (s.top() + ‘0’);
		cout << ans;
		s.pop();
	}
	if (flag == 0)
		printf(“0”);
}

样例输入：

1223
1212

样例输出： 

00000000000000000000010011000111
000004BC

样例输入：

0
0

样例输出：

00000000000000000000000000000000
00000000

样例输入：

-1111
-250

样例输出：

11111111111111111111101110101001
FFFFFF06

代码

queue

#include<bits/stdc++.h>
using namespace std;
int main()
{
	queue<int> s;
	int i = 0;
	for (i = 0; i < 10; i++)
	{
		int t;
		cin >> t;
		s.push(t);
	}
	cout << endl;
	for (i = 0; i < 5; i++)
	{
		int front = s.front();
		s.pop();
		cout<<front;
	}
	cout << endl << s.front() << s.back() << s.size();
	for (i = 0; i < s.size(); i++)
	{
		int front = s.front();
		cout<<front;
		s.pop();
		s.push(front);
	}
	cout << endl << s.size() << endl;
}

小综合

#include<bits/stdc++.h>
using namespace std;
int main()
{
	stack<char>s;
	queue<char>q;
	string line;
	char x;
	
	cin >> line >> x;
	int i, n = line.size();
	for (i = 0; i < n; i++)
		s.push(line[i]);
	cout << s.size() << s.top() << endl;
	while (s.size())
	{
		char top = s.top();
		s.pop();
		printf("%c", top);
		if (top != x)
			q.push(top);
	}
	cout << q.size() << q.front() << q.back();
	for (i = 0; i < q.size(); i++)
	{
		char t = q.front();
		q.pop();
		cout << t;
		q.push(t);
	}

}

进制转换

#include<bits/stdc++.h>
using namespace std;
void convertDecToBin(int x);
void convertDecToHex(int x);
int main()
{
	int num1, num2;
	cin >> num1 >> num2;
	convertDecToBin(num1);
	convertDecToHex(num2);
}

void convertDecToBin(int x)
{
	stack<int>s;
	for(int i=0;i<32;i++)
	{
		s.push(x & 1);
		x >>= 1;
	}
	int flag = 0;
	while (s.size())
	{
		flag = 1;
		int t = s.top();
		printf("%d ", s.top());
		s.pop();
	}
	if (flag == 0)
		printf("0");
	cout << endl;
}
void convertDecToHex(int x)
{
	stack<int>s;
	for (int i = 0; i < 8; i++)
	{
		s.push(x & 15);
		x >>= 4;
	}
	int flag = 0;
	while (s.size())
	{
		flag = 1;
		char ans = s.top() > 9 ? (s.top() - 10 + 'A') : (s.top() + '0');
		cout << ans;
		s.pop();
	}
	if (flag == 0)
		printf("0");
}