[栈和队列](3)题集_1

15
[ 数据结构 ] [ 栈和队列 ]

栈和队列的结构特性：

栈：可用线性存储结构的顺序存储和链式存储，特点是先进后出，后进先出

队列：可用线性存储结构的顺序存储和链式存储，特点是先进先出，后进后出

基础知识题

1、用栈的存储结构模拟火车进站，如果进站的车厢序列为123，则可能得到的出站车厢序列为多少？如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到(即写出以‘S’表示进站，X表示出栈操作序列)

  1. 由于栈的存储结构为先进后出，则可能得到的车厢序列为123、321、321、213、132
  2. 可能出现135426，但不可能出现435612，因为4356出栈，说明还有12在栈中，1不可能先于2出栈。
  3. 这题需要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

图解如下：

img

二、

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两个合法的操作序列，得到的结果为：

img

img

6、试证明：若借助栈由输入序列12....n得到的输出序列为p1，p2....pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形，存在着i<j<k使pj<jk<pi

假设我们输入栈中的序列为123，则出栈序列为321,按题目要求，输入栈中的是有序序列，则必然先出来的数值比后出来的数值大，只能存在i<j<k，则pk<pj<pi；

7、按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，仿表达式运算的格式，画出下列算术表达式求值时操作数和栈的运算符栈的变化过程。

碰到操作数，则进操作数栈，碰到运算符，则进算符栈。

img

8、试推导n阶Hanoi塔执行移动的次数

img

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作为双端队列的输出序列，试分别求出满足以下条件的输出序列：

  • 能由输入受限的双端队列得到，但不能由输出首先的双端队列得到的输出序列
  • 能由输出受限的双端队列打得到，但不能由输入受限的双端队列得到的输出序列
  • 即不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列

img

我们先看看 上图，可以知道

  • 输入受限就是插入受限，只能在一端进行插入，但删除缺两端都行
  • 输出受限就是删除受限，只能在一端进行删除，但是输入两端都行

这道题最主要的就是求出在栈形式下不可能输出的序列，然后一个一个去尝试，下列视频详细的解答了这道题，在这我就不放答案了。

详细解答视频

算法设计题

15、假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点，试编写实现这个双向栈tws的三个操作:初始化initstack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么优缺点、

img

上图所示是一个双向栈，即在同一顺序存储空间内实现的两个栈。把两个栈的栈底分别设在顺序存储空间（如数组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;
}

运行结果如下所示：

img正确

img错误

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等画图软件的染色功能，具体请看补充笔记。

补充笔记

本文链接：

https://nullcode.fun/24.html
1 + 8 =
快来做第一个评论的人吧~