C++学习记录-数据结构-队列与栈

C++学习记录-数据结构-队列与栈

一、队列

队列是一种先进先出的线性结构。在它的头部只允许进行出队（删除）操作，在它的尾部只允许进行入队（插入）操作，即“先进先出”。

具体操作：

1.定义一个数组arr

2.定义一个int head=0，指向数组第一位

3.定义一个int tail=0，指向数组第一位（此时数组为空队列）

4.入队，arr[tail]=x；tail++

5.出队，即head++

当head=tail时，队列为空队列

代码示例：解密QQ号

给一串数字，先将第1个数删除，再将第2个数放到末尾，将第3个数删除，再将第4个数放到末尾…直到最后一个数，将最后一个数删除。最后把删除的数按顺序连在一起即为所求QQ号

分析：删除即为出队操作，放到末尾即为出队后入队操作

#include<iostream>
using namespace std;

char arr[1001];

//再新建一个数组来储存结果
char brr[1001];
int i = 0;

void key(int head, int tail)
{
	if (head == tail)
	{
		return;
	}//如果队列为空，说明解密完成

	//出队操作
    brr[i] = arr[head];
	head++;
	i++;
    
    //出队后入队操作
	arr[tail] = arr[head];
	head++;
	tail++;

    //完成一轮后继续传入新的头尾，这是一个递归过程
	key(head, tail);
}

int main()
{
	//获取数组
    cin.get(arr, 1001);
	int a = strlen(arr);
	
    //开始解谜
	int head = 0;
	int tail = a;//定义头指针和尾指针

	key(head, tail);//开始解密

    //解密完成，输出
	cout << brr;

	return 0;

}

运行结果：

二、栈

栈是一种后进先出的数据结构。如手枪的弹夹，最后装入的子弹是最先发射出去的。栈只需要一个指向栈顶的变量top，出栈入栈都在栈顶进行操作。

**示例：**回文判断：

#include<iostream>
#include<cstring>
using namespace std;

char arr[10001];//待判断字符串

void ish(int mid, int next, int a)
{
	for (int i = mid; i >= 0; i--)
	{
		if (arr[mid] != arr[next])
		{
			cout << "NO" << endl;
			return;
		}
		else {
			mid--;//这是一个出栈操作

			next++;
		}
	}
	cout << "YES" << endl;
}


int main()
{
	//输入待判断字符串
	cin.get(arr, 10001);
	int a = strlen(arr);



	if (a % 2 == 0)
	{
		//前一半
		int mid = a / 2 - 1;

		//后一半
		int next = a / 2;

		//开始判断
		ish(mid, next, a);
	}
	else {
		int mid = a / 2 - 1;
		int next = a / 2 + 1;
		ish(mid, next, a);
	}//奇数同理
}