[栈和队列](3)题集_1
栈和队列的结构特性:
栈:可用线性存储结构的顺序存储和链式存储,特点是先进后出,后进先出
队列:可用线性存储结构的顺序存储和链式存储,特点是先进先出,后进后出
基础知识题
1、用栈的存储结构模拟火车进站,如果进站的车厢序列为123,则可能得到的出站车厢序列为多少?如果进站的车厢序列为123456,则能否得到435612和135426的出站序列,并请说明为什么不能得到或者如何得到(即写出以‘S’表示进站,X表示出栈操作序列)
- 由于栈的存储结构为先进后出,则可能得到的车厢序列为123、321、321、213、132
- 可能出现135426,但不可能出现435612,因为4356出栈,说明还有12在栈中,1不可能先于2出栈。
- 这题需要S跟X不间断的操作,画个图然后一个一个配就行,了解栈的先进后出原理就没太大问题
2、简述栈和线性表的差别
栈和线性表的差别主要是在插入和删除操作上,线性表的插入和删除是无限制,根据程序要求进行插入和删除操作,而栈则的插入操作和删除都是位于前端
3、写出下列程序段的输出结果(栈的元素类型为:SElemType为char)
void main()
{
Stack S;
char x, y;
InitStack(S);
x = 'c';
y = 'k';
Push(S, x);
Push(S, 'a');
Push(S, y);
Pop(S, x);
Push(S, 't');
Push(S, x);
Pop(S, x);
Push(S, 's');
whilie(!StackEmpty(S))
{
Pop(S, y);
printf(y);
}
printf(x);
}
程序运行过程如下所示:
- 定义一个S栈
- 定义两个字符类型变量x,y
- 为S栈初始化
- 将x赋值字符c,将y赋值字符k
- 将x进栈,此时S('c');
- 将字符a进栈,此时S('a','c');
- 将y进栈,此时S('k','a','c');
- S进行出栈,传入x内,此时S('a','c'),x=‘k’;
- 将字符t进栈,此时S('t','a','c');
- 将x进栈,此时S('k','t','a','c');
- S进行出栈,传入x内,此时S('t',‘a’,'c');,x='k';
- 将字符s进行进栈,此时S('s','t','a','c');
- 执行循环,不断从栈顶出栈,栈顶元素传入y内,打印y,循环结束够打印x
- 最后输出结果为:stack
4、简述以下算法的功能(栈的元素类型SElemType为int)
一、
Status algol(Stack S)
{
int i, n, A[255];
n = 0;
while (!StackEmpty(S))
{
n++;
Pop(S, A[i]);
};
for (i = 1; i <= n; i++)
{
Push(S, A[i]);
}
}
反转栈内元素,由于栈的特点是先进后出,程序第一个while循环的作用是将栈站内元素不断出栈传入A数组内,我们假设栈内元素为Hello
则A={H,e,l,l,o};
然后第二个循环是将数组元素按从左到右的顺序不断压入栈顶,则进栈顺序为Hello。
栈内元素从上到下来看,此时为:olleH
图解如下:
二、
Status algo2(Stack S, int e)
{
Stack T;
int d;
InitStack(T);
while (!StackEmpty(S))
{
Pop(S, d);
if (d != e)
{
Push(T, D);
}
}
while (!StackEmpty(T))
{
Pop(T, d);
Push(S, d);
}
}
从S栈从删除所有值为e的数。
程序首先给定了一个临时栈T,不断从S栈中取出元素去做判断,如果元素不为e,则压入T栈中,如果为e,则不压入
直到所有元素全部判断完,再将T内元素传入S中,操作结束后,此时S栈内已经没有值为e的元素,注意此算法需要改变S栈内的状态,所以用引用或指针类型。
5、假设以S和X分别表示入栈和出栈操作,则初态和终态均为栈空的入栈和出栈操作序列可以仅由S和X组成的序列,称可以操作的序列为合法序列(例如,SXSX为合法序列,SXXS为非法序列),试给出区分给定序列为合法序列或非法序列的一般准则,并证明:两个不同的合法(栈操作)序列(对同一输出序列)不可能得到相同的输出元素(注意:在此指的是元素实体,而不是值)。
这题别看题目那么长,其实挺简单, 首先题目给定的条件:初始操作为空栈,S表示压入元素到栈顶,X表示从栈顶删除元素。
- S操作前提是栈不满
- X操作前提是栈不空
所以合法表达式的前提就是S<=X,每进行一次X操作都必须建立在S操作后面。由于栈是后进先出的特点,则不同的合法序列对应的输出值不同,可用下列代码证明:
int main()
{
int n = 0, x = 0;
char ch;
InitStack(&S);
ch = getchar();
while (ch != '#')
{
if (ch == 'S')
{
Push(&S,++n);
}
if (ch == 'X')
{
Pop(&S, &x);
}
ch = getchar();
}
int* p = S.base;
while (p < S.top)
{
printf("%d", *p);
p++;
}
system("pause");
return 0;
}
我们测试用例SXSXS和SSXSX两个合法的操作序列,得到的结果为:
6、试证明:若借助栈由输入序列12....n得到的输出序列为p1,p2....pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形,存在着i<j<k使pj<jk<pi
假设我们输入栈中的序列为123,则出栈序列为321,按题目要求,输入栈中的是有序序列,则必然先出来的数值比后出来的数值大,只能存在i<j<k,则pk<pj<pi;
7、按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,仿表达式运算的格式,画出下列算术表达式求值时操作数和栈的运算符栈的变化过程。
碰到操作数,则进操作数栈,碰到运算符,则进算符栈。
8、试推导n阶Hanoi塔执行移动的次数
9、试将下列递推过程改写为递归过程。
void ditui(int n)
{
int i;
i = n;
while (i > 1)
{
printf(i--);
}
}
改写后:
void digui(int n)
{
if (n > 1)
{
printf("%d ", n);
digui(n - 1);
}
}
10、试将下列递归程序改写为非递归过程
void digui(int *sum)
{
int x;
scanf_s("%d", &x);
if (x == 0)
{
*sum = 0;
}
else
{
digui(sum);
*sum += x;
}
printf("%d\n", *sum);
}
非递归:
void ditui(int *sum,SqStack *S)
{
int x;
scanf_s("%d", &x);
while (x != 0)
{
Push(S, x);
scanf_s("%d", &x);
}
int* p = S->top - 1;
while (p >= S->base)
{
*sum += *p;
printf("%d\n", *sum);
p--;
}
}
利用栈的后进先出将x的值压入栈顶,直到x为0结束,然后从栈顶不断访问并与sum相加,达到与递归一样的效果。
递归就是当x不为0的时候,不断保存这个场景,然后继续递,直到x为0的时候,再不断归回来,在归的过程中,sum的值从最后一个场景开始累加。
11、简述队列和栈这两种数据类型的相同点和差异处
队列和栈都是操作受限的线性表,差异处就是队列插入操作都在前端,删除操作在尾端,特点是先进先出,而栈是插入和删除都在前端,特点是后进先出
12、写出以下程序段的输出结果(队列中的元素类型QElemType为char)
void main()
{
Queue Q;
InitQueue(Q);
char x = 'e', y = 'c';
EnQueue(Q, 'h');
EnQueue(Q, 'r');
EnQueue(Q, y);
DeQueue(Q, x);
EnQueue(Q, x);
DeQueue(Q, x);
EnQueue(Q, 'a');
while (!QueueEmpty(Q))
{
DeQueue(Q, y);
printf(y);
}
printf(x);
}
- 将字符h插入队列,此时Q=h
- 将字符r插入队列,此时Q=h,r
- 将y插入队列,此时Q=h,r,c
- 删除操作,将值传入x,此时队列Q=r,c x=h
- 将x插入队列,此时Q=r,c,h
- 删除操作,将值传入x,此时队列Q=c,h x=r
- 将字符a插入队列,此时队列Q=c,h,a
- 循环删除操作,值传入y,打印出来。
- 最后打印x
- 结果为:char
13、简述下列算法的功能(栈和队列的元素类型均为int)
void algo(Queue& Q)
{
Stack S;
int d;
InitStack(S);
while (!QueueEmpty(Q))
{
DeQueue(Q, d);
Push(S, d);
}
while (!StackEmpty(Q))
{
Pop(S, d);
EnQueue(Q, d);
}
}
利用S栈做跳板,反转队列中的元素,例如Q=Hello,则第一个循环后,栈从上到下为:olleH,然后插入队列中为olleH
14、若以1234作为双端队列的输出序列,试分别求出满足以下条件的输出序列:
- 能由输入受限的双端队列得到,但不能由输出首先的双端队列得到的输出序列
- 能由输出受限的双端队列打得到,但不能由输入受限的双端队列得到的输出序列
- 即不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列
我们先看看 上图,可以知道
- 输入受限就是插入受限,只能在一端进行插入,但删除缺两端都行
- 输出受限就是删除受限,只能在一端进行删除,但是输入两端都行
这道题最主要的就是求出在栈形式下不可能输出的序列,然后一个一个去尝试,下列视频详细的解答了这道题,在这我就不放答案了。
算法设计题
15、假设以顺序存储结构实现一个双向栈,即在一维数组的存储空间中存在着两个栈,它们的栈底分别设在数组的两个端点,试编写实现这个双向栈tws的三个操作:初始化initstack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法,其中i为0或1,用以分别指示设在数组两端的两个栈,并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么优缺点、
上图所示是一个双向栈,即在同一顺序存储空间内实现的两个栈。把两个栈的栈底分别设在顺序存储空间(如数组v[n])的两端,每个栈都有各自独立的栈底和栈顶指针。栈底位置不变。入栈时,各自的栈顶向中间伸展,仅当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以做到互补余缺,使得每个栈的可利用空间均有可能超过n/2。这不仅减少了栈溢出的可能性,也增加了空间的利用率。因此,这种方案经常被采用。
设有两个栈S1和S2,按上图的方法共享一个数组的空间。试为此双向栈设计初始化inistack、入栈PUSH和出栈POP的算法,其中i为0或1,用以指示栈号。试写一个算法,完成对任何一个栈(S1或S2)的入栈和出栈操作。
完整算法如下所示:
#define MAX 100
#include<stdio.h>
#include<stdlib.h>
typedef int type;
typedef struct
{
type* Arr;
int top1;
int top2;
int base1;
int base2;
}TwsStack;
TwsStack S;
void InitStack(TwsStack* S)
{
S->Arr = (type*)malloc(sizeof(int) * MAX);
if (S->Arr == NULL)
{
exit(0);
}
S->base1 = 0;
S->top1 = -1;
S->base2 = MAX - 1;
S->top2 = MAX;
}
void Push(TwsStack* S, int i, type x)
{
if (S->top1 >= S->top2)
{
printf("栈满\n");
exit(0);
}
else
{
switch (i)
{
case 0:
S->top1++;
S->Arr[S->top1] = x;
break;
case 1:
S->top2--;
S->Arr[S->top2] = x;
break;
default:
printf("Error: type is 0 or 1");
break;
}
}
}
void Pop(TwsStack* S, int i)
{
switch (i)
{
case 0:
if (S->top1 < S->base1)
{
printf("栈空\n");
exit(0);
}
S->top1--;
break;
case 1:
if (S->top2 > S->base2)
{
printf("栈空\n");
exit(0);
}
S->top2++;
break;
}
}
17、试写一算法,识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’的模式的字符序列,其中序列1和序列2中都不含字符‘&’,且序列2是序列1的逆序列,例如,‘a+b&b+a’是属该模式的序列,而‘1+3&3-1’则不是。
这道题就是依次读入进去,将序列1压入堆栈,遇到&字符的时候,从栈顶取出元素与其做判断,如果判断为假,则不是,如果为真,则是。算法如下:
int NatureType()
{
InitStack(&S);
char ch;
ch = getchar();
while (ch != '@'&&ch!='&')
{
Push(&S, ch);
ch = getchar();
}
if (ch == '&')
{
ch = getchar();
while (ch != '@')
{
char temp;
Pop(&S, &temp);
if (Judge(ch, temp))
{
ch = getchar();
}
else
{
return 0;
}
}
}
else
{
return -1;
}
return 1;
}
运行结果如下所示:
正确
错误
18、试写一个判别表达式中开、闭括号是否配对出现的算法
这道题我们在看教程的时候出现过讲解,假设表达式中允许包括两种括号:圆括号和方括号,其嵌套的顺序随意,即([]())或[([][])]等正确的格式,[(])或([())或(()]均为不正确的格式。
由此,在算法中设置一个栈,每读入一个括号,若是左括号,则作为一个新的元素压入栈顶,若是右括号,则去对栈顶元素做判断,若匹配,则可以抵消,读入下一个字符,或是不合法情况。
注意:开始和结束的时候,栈都应该为空!测试代码如下所示:
int Judge(char a, char b)
{
if ((a == '(' && b == ')') || (a == '[' && b == ']'))
{
return 1;
}
return 0;
}
int NatureType()
{
InitStack(&S);
char ch;
ch = getchar();
if (S.base == S.top)
{
while (ch != '@')
{
if (ch == '(' || ch == '[')
{
Push(&S, ch);
ch = getchar();
}
else if (ch == ')' || ch == ']')
{
int temp;
Pop(&S, &temp);
if (Judge(temp, ch))
{
ch = getchar();
}
else
{
return 0;
}
}
else
{
return -1;
}
}
if (S.base == S.top)
{
return 1;
}
else
{
return 0;
}
}
else
{
return -1;
}
}
int main()
{
switch (NatureType())
{
case -1:
printf("输入出错\n");
system("pause");
break;
case 1:
printf("true\n");
system("pause");
break;
case 0:
printf("false\n");
system("pause");
break;
}
}
19、假设一个算术表达式可以包含三种括号:圆括号“(”和“)”、方括号“[”和“]”和花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用,(如...[...{...}...[...]...]...[...]...(...)...)。编写判别给定表达式这种所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)
这道题和18题的思路一样,我傻逼的把18题中的中开闭理解成两种括号了,这题就是上题的答案加一个花括号的判断
20、假设以二维数组g(1…m, 1…n)表示一个图像区域,g[i,j]表示该区域中点(i,j)所具颜色,其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。
这道题和之前的N皇后问题相似,这道题用DFS反而不好,耗时久,所以用DFS做比较好,可以参考PS等画图软件的染色功能,具体请看补充笔记。