初识队列和栈
队列
队列，作为一种比较简单的数据结构，其在算法中有着非常多的应用。其类似于一条单行道，先进先出，后进后出，每次需要记录头指针和尾指针。接下来我将从一个简单的例子出发渗透队列的思想。
题目大意
n 个人围成一圈，从第一个人开始报数,数到m的人出列，再由下一个人重新从1开始报数，数到m的人再出圈，依次类推，直到所有的人都出圈，输出依次出圈人的编号。
解题思路
构建一个含有n个元素的队列，进行n次循环，在每次循环中将队列前m-1个元素依次放置队尾，然后将第m个元素出队并输出，这样每次循环之后形成新的队列重复以上操作即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<cstdio>
int a[1000005];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int head=1,tail=0;
for(int i=1;i<=n;i++)
{
a[++tail]=i;
}
while(tail>=head)
{
for(int i=1;i<m;i++)
{
a[++tail]=a[head++];
}
printf("%d ",a[head++]);
}
}
|
栈
栈，原理类似于队列，如同一个死胡同，出口和入口为同一个，先进后出，每次只需记录尾指针即可。话不多说，再看一个小例子来了解栈的应用。
题目大意
判断一个数是否为回文数
解题思路
直接利用栈存储前一半的字符串，然后将后一半字符串与栈中字符对比判断即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<cstdio>
#include<cstring>
char t[10005];
int top=0;
int main()
{
char a[100];
bool dg=0;
gets(a);
int len=strlen(a);
int mid=len/2-1;
for(int i=0;i<=mid;i++)
{
t[++top]=a[i];
}
if(len%2==0)
{
for(int i=mid+1;i<len;i++)
{
if(t[top--]!=a[i])
{
dg=1;break;
}
}
}else
{
for(int i=mid+2;i<len;i++)
{
if(t[top--]!=a[i])
{
dg=1;break;
}
}
}
if(dg) printf("不是回文数");
else printf("是回文数");
return 0;
}
|
混合运用
接下来就轮到队列和栈的混合双打了,没错，就是传说中的经典纸牌游戏
题目大意
双方按照发牌的原本顺序轮流出牌放置桌面，出牌时，若一方打出的牌与桌面上某张牌相同，则可取走这两张牌之间的所有牌（包括这两张）依次放置牌的最后，当一方牌全出完时则失败，
解题思路
开始时双方手中的牌可用队列存储，出牌即使出队，赢牌则是入队。而桌面上的牌则可用栈存储，每打出一张牌即入栈。最后判断队列是否为空即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include <stdio.h>
struct queue
{
int data[1000];
int head;
int tail;
};
struct stack
{
int data[10];
int top;
};
int main() {
struct queue q1, q2;
struct stack s;
int book[10];
int i, t;
q1.head = 1; q1.tail = 1;
q2.head = 1; q2.tail = 1;
s.top = 0;
for (i = 1; i < 9; i++)
{
book[i] = 0;
}
for (i = 1; i <= 6; i++)
{
scanf_s("%d", &q1.data[q1.tail]);
q1.tail++;
}
for (i = 1; i <= 6; i++)
{
scanf_s("%d", &q2.data[q2.tail]);
q2.tail++;
}
while (q1.head < q1.tail && q2.head < q2.tail)
{
t = q1.data[q1.head];
if (book[t] == 0)
{
q1.head++;
s.top++;
s.data[s.top] = t;
book[t] = 1;
}
else
{
q1.head++;
q1.data[q1.tail] = t;
q1.tail++;
while (s.data[s.top] != t)
{
book[s.data[s.top]] = 0;
q1.data[q1.tail] = s.data[s.top];
q1.tail++;
s.top--;
}
book[s.data[s.top]] = 0;
q1.data[q1.tail] = s.data[s.top];
q1.tail++;
s.top--;
}
if (q1.head == q1.tail) break;
t= q2.data[q2.head];
if (book[t] == 0)
{
q2.head++;
s.top++;
s.data[s.top] = t;
book[t] = 1;
}
else
{
q2.head++;
q2.data[q2.tail] = t;
q2.tail++;
while (s.data[s.top] != t)
{
book[s.data[s.top]] = 0;
q2.data[q2.tail] = s.data[s.top];
q2.tail++;
s.top--;
}
book[s.data[s.top]] = 0;
q2.data[q2.tail] = s.data[s.top];
q2.tail++;
s.top--;
}
if (q2.head == q2.tail) break;
}
if (q1.head == q1.tail) printf("B WIN");
else printf("A WIN");
}
|
