精华内容
下载资源
问答
  • 判断一个栈为满的条件
    万次阅读
    2016-06-28 10:24:15

    数组栈
    完成int IsEmpty(Stack S)函数,该函数判断栈是否已空,如果空返回1,否则返回0。
    完成int IsFull(Stack S)函数,该函数判断栈是否已满,如果满返回1,否则返回0。

    typedef int ElemType;
    struct StackRecord;
    typedef struct StackRecord *Stack;
    struct StackRecord
    {
        int Capacity; //栈容量
        int Top; //栈顶,初始为1
        ElemType *Array;
    };
    
    int IsEmpty(Stack S)
    {
        if(S‐>Top==‐1)
        {
            return 1;
        } 
        else
        {
            return 0;
        }
    }
    int IsFull(Stack S)
    {
        if(S‐>Top==S‐>Capacity‐1)
        {
            return 1;
        } 
        else
        {
            return 0;
        }
    }

    链栈
    完成int IsEmpty(Stack S);函数,该函数判断栈S是否为空,空栈返回1,否则返回0,已知S是带头结点的链栈。

    typedef int ElemType;
    struct Node;
    typedef struct Node * PtrToNode;
    typedef PtrToNode Stack;
    struct Node
    {
        ElemType data;
        PtrToNode next;
    };
    
    int IsEmpty(Stack S)
    {
        return S‐>next==NULL?1:0;
    }

    数组队列
    完成int IsEmpty(Queue Q);函数,该函数判断队列Q是否已空,如果已空返回1,否则返回0,其中Q是基于数组的非循环队列。
    完成int IsFull(Queue Q)函数,该函数判断队列Q是否已满,如果已满返回1,否则返回0,其中Q是基于数组的非循环队列。

    typedef int ElemType;
    struct QueueRecord;
    typedef struct QueueRecord * Queue;
    struct QueueRecord
    {
        int Capacity; //队列总容量
        int Front; //队首 初始值为0
        int Rear; //队尾,初始值为1
        int Size; //队列中数据数,初始值为0
        ElemType *Array;
    };
    
    int IsEmpty(Queue Q)
    {
        return Q‐>Size==0;
    }
    int IsFull(Queue Q)
    {
        return Q‐>Rear==Q‐>Capacity‐1?1:0;
    }

    链队列
    完成int IsEmpty(Queue q)函数,该函数判定基于链表的队列q是否为空,空队列返回1,非空队列返回0,其中q是不带头节点的链表队列。

    typedef int ElemType;
    struct node;
    typedef struct node Node;
    struct queue;
    typedef struct queue * Queue;
    struct node
    {
        ElemType data;
        Node * next;
    };
    struct queue
    {
        Node * front; //队首
        Node * rear; //队尾
        int size; //队列中数据数int IsEmpty(Queue q)
    {
        return q‐>size==0?1:0;
    }
    更多相关内容
  • 文档之顺序

    2022-04-22 23:31:44
    采用顺序存储的称为顺序,它采用一组地址连续的存储单元存放自底到栈顶的数据元素,同时设定一个指针(top)指向当前栈顶元素的位置。通常采用数组来实现。

    顺序栈

    定义

    概念

    采用顺序存储的栈称为顺序栈,它采用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时设定一个指针(top)指向当前栈顶元素的位置。通常采用数组来实现。

    在这里插入图片描述

    结构体

    /**
     * 顺序栈结构体定义
     */
    typedef struct {
        /**
         * 数据域,数组,用来存储栈中元素
         */
        int data[MAXSIZE];
        /**
         * 指针域,表示栈顶指针,实际上就是数组下标
         */
        int top;
    } SeqStack;
    

    特点

    注意:

    • 栈的判空条件和判满条件可能会跟实际设置不一样,下面是设置 top=-1 为初始化条件,所以判空条件是 top==-1。但有些资料中是将 top=0 作为初始条件,因此判空条件又不一样。
    • 由于顺序栈的入栈操作受数组上界的约束,当栈的使用空间不够时,可能发生栈上溢,此时应该报出错误信息。
    • 所谓的栈上溢就是当栈满后,再继续入栈就会发生上溢。
    • 所谓的栈下溢就是当栈空后,再继续出栈就会发生下溢。
    • 因为规定了 top==-1 表示栈空,所以元素进栈操作必须是先移动指针,再进入元素,因为数组下标不存在 -1。但有可能初始规定 top=0,那么就要元素先入栈,再将栈顶指针加一。其实本质都是一样的,根据实际情况来即可。
    • 进栈操作次序决定了出栈操作次序,由于本文中进栈操作是先变动栈顶指针再存入元素,因此出栈操作必须是先取出元素,再变动指针。如果出栈打算先变动指针再取出元素,则会造成栈顶元素丢失,因为取出的是栈顶下边的元素。
    • top 表示栈顶指针,实际上就是数组下标。初始时(即初始化操作中,也就是空栈)设置 top=-1;而 stack.data[stack.top] 表示获取栈顶元素。
    • 进栈操作,如果栈不满才能进栈,先将栈顶指针加一,再将值填充到栈顶的位置中。
    • 出栈操作,如果栈不为空才能出栈,先取栈顶元素值,再将栈顶指针减一。
    • 栈空条件:stack.top==-1。因为初始条件是 top=-1,并且 top 表示数组下标,不能为 -1,所以如果为 -1 了那么就表示是空栈。
    • 栈满条件:stack.top=MAXSIZE-1。其中 MAXSIZE 是栈能存储的最大元素的个数,则 MAXSIZE-1 为栈满时栈顶元素在数组中的下标位置,因为数组下标是从 0 开始的。
    • 栈长:stack.top+1。因为 top 表示数组下标,所以数组元素实际个数是下标加一。

    基本操作

    注,完整代码请参考:

    概述

    顺序栈的常见操作如下:

    • void init(SeqStack *stack):初始化顺序栈,即将栈顶指针置为 -1 表示是空栈。其中 stack 表示未初始化的顺序栈。
    • int isEmpty(SeqStack stack):判断顺序栈是否为空,如果为空则返回 1,否则返回 0。其中 stack 表示顺序栈。如果顺序栈为空则返回 1,否则返回 0。
    • int push(SeqStack *stack, int ele):将元素进栈。其中 stack 表示顺序栈;ele 表示新元素。如果新元素入栈成功则返回 1,如果顺序栈已满则返回 0。
    • int pop(SeqStack *stack, int *ele):将元素出栈。其中 stack 表示顺序栈;ele 用来保存出栈的元素。如果顺序栈为空则返回 0,如果顺序栈出栈元素成功则返回 1。
    • int getTop(SeqStack stack, int *ele):获取栈顶元素,但不会将元素出栈。其中 stack 表示顺序栈;ele 用来存放栈顶元素。如果顺序栈为空则返回 0,如果得到顺序栈的栈顶元素则返回 1。
    • int size(SeqStack stack):获取顺序栈中元素个数。其中 stack 表示顺序栈。
    • void print(SeqStack stack):打印顺序栈中所有元素。其中 stack 表示顺序栈。
    • void clear(SeqStack *stack):清空顺序栈中所有元素。

    init

    初始化栈,只需要将栈顶指针置为 -1 即可。

    在这里插入图片描述
    实现步骤:

    • 将栈顶指针 top 置为 -1 即可。

    实现代码如下:

    /**
     * 初始化顺序栈,即将栈顶指针指向 -1 表示空栈
     * @param stack 顺序栈
     */
    void init(SeqStack *stack) {
        // 设定让栈顶指针指向 -1 表示为栈空
        stack->top = -1;
    }
    

    isEmpty

    判断顺序栈是否为空,如果栈顶指针 top==-1 则表示栈空,否则非空。

    在这里插入图片描述

    实现步骤:

    • 即判断栈顶指针 top 是否等于 -1 即可。如果等于 -1 则表示空栈,否则不是。

    实现代码如下:

    /**
     * 判断顺序栈是否为空
     * @param stack 顺序栈
     * @return 如果顺序栈为空则返回 1,否则返回 0
     */
    int isEmpty(SeqStack stack) {
        // 只需要判断栈顶指针是否等于 -1 即可,如果是空栈则返回 1,不是空栈则返回 0
        if (stack.top == -1) {
            return 1;
        } else {
            return 0;
        }
    }
    

    push

    将元素入栈。如果栈满则不能入栈则返回 0 表示入栈失败;否则将元素入栈,并返回 1 表示入栈成功。以 stack=[11, 22, 33]; ele=44 为例如图:

    在这里插入图片描述

    实现步骤:

    • 参数校验,判断是否栈满,如果栈满则不能入栈,返回 0 表示入栈失败。
    • 先修改栈顶指针,将其加一。
    • 再将新元素填充入栈顶指针所表示的位置中。
    • 返回 1 表示入栈成功。

    实现代码如下:

    /**
     * 将元素入栈
     * @param stack 顺序栈
     * @param ele 元素值 
     * @return 如果栈满则返回 0 表示入栈失败;如果插入成功则返回 1
     */
    int push(SeqStack *stack, int ele) {
        // 1.参数校验,如果栈满则不能入栈元素
        if (stack->top == MAXSIZE - 1) {
            // 如果栈满,则返回 0,表示不能入栈
            return 0;
        }
        // 2.先将栈顶指针加一,指向新空数组位置
        stack->top++;
        // 3.将新元素值填充到新位置中
        stack->data[stack->top] = ele;
        return 1;
    }
    

    pop

    将栈顶元素出栈,用 ele 保存出栈元素的值。以 stack=[11, 22, 33, 44] 为例如图所示:

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果栈空则不能出栈,否则产生下溢。
    • ele 保存栈顶元素。
    • 将栈顶指针减去一,表示删除掉栈顶元素。

    实现代码如下:

    /**
     * 将元素出栈
     * @param stack 顺序栈
     * @param ele 用来保存出栈的元素
     * @return 如果栈空则返回 0 表示出栈失败;否则返回 1 表示出栈成功
     */
    int pop(SeqStack *stack, int *ele) {
        // 1.参数校验,栈空不能出栈
        if (stack->top == -1) {
            // 栈空,没有元素可出栈
            return 0;
        }
        // 2.用 ele 来保存顺序栈栈顶元素
        *ele = stack->data[stack->top];
        // 3.然后栈顶指针减一,表示出栈一个元素
        stack->top--;
        return 1;
    }
    

    getTop

    取出栈顶元素,但并不出栈。以 stack=[11, 22, 33, 44] 为例如图:

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果栈空则不能出栈。
    • 直接取出栈顶元素,用 ele 保存。

    实现代码如下:

    /**
     * 获取栈顶元素,但不出栈
     * @param stack 顺序栈
     * @param ele 用来保存出栈元素
     * @return 如果栈空则返回 0 表示出栈失败;否则返回 1 表示出栈成功
     */
    int getTop(SeqStack stack, int *ele) {
        // 1.参数校验,如果栈空则不能出栈
        if (stack.top == -1) {
            // 栈空,没有元素可出栈
            return 0;
        }
        // 2.保存栈顶元素返回
        *ele = stack.data[stack.top];
        return 1;
    }
    

    size

    获取栈中元素个数。

    在这里插入图片描述

    实现步骤:

    • 返回栈顶指针加一即可,即使是空栈。

    实现代码如下:

    /**
     * 获取顺序栈中元素个数
     * @param stack 顺序栈
     * @return 顺序栈中元素个数
     */
    int size(SeqStack stack) {
        // top 表示栈顶指针,实际上就是数组 data 的下标,所以实际元素个数就是下标加一
        // 即使是空栈 top=-1,那么最后也会返回 0 表示元素个数为零个
        return stack.top + 1;
    }
    

    print

    从栈顶到栈底打印顺序中所有元素。

    在这里插入图片描述

    实现步骤:

    • 从栈顶扫描到栈底所有元素。

    实现代码如下:

    /**
     * 打印顺序栈中所有元素
     * @param stack 顺序栈
     */
    void print(SeqStack stack) {
        printf("[");
        for (int i = stack.top; i >= 0; i--) {
            if (i != stack.top) {
                printf(", ");
            }
            printf("%d", stack.data[i]);
        }
        printf("]\n");
    }
    

    clear

    清空顺序栈。

    实现步骤:

    • 将栈顶指针指向 -1 即可。

    实现代码如下:

    /**
     * 清空顺序栈中所有元素
     * @param stack 顺序栈
     */
    void clear(SeqStack *stack) {
        // 将栈顶指针指向 -1 即可,不需要重置一遍栈中元素
        stack->top = -1;
    }
    

    练习题

    以下是一些顺序栈的练习题:

    展开全文
  • 和对列是两种操作特殊的线性表,在实际中应用相当广泛。本实验的目的在于使学生 深入理解的特性,熟悉的基本操作,以便在实际问题背景下灵活运用它们,同时巩固对 这种结构的构造方法和掌握其运行过程,了解较...
  • 数据结构复习(和队列)

    千次阅读 2021-06-01 22:36:55
    数据结构复习题(3)和队列选择题填空题判断题 ...2、判断一个循环队列Q(最多n个元素)为条件是( )。 A. Q->rear==Q->front B. Q->rear==Q->front+1 C. Q->front==

    数据结构复习题(栈和队列)

    栈和队列

    选择题

    1、一个栈的输入序列为:a,b,c,d,e,则栈的不可能输出的序列是( )。
    A. a,b,c,d,e
    B. d,e,c,b,a
    C. d,c,e,a,b
    D. e,d,c,b,a

    2、判断一个循环队列Q(最多n个元素)为满的条件是( )。
    A. Q->rear==Q->front
    B. Q->rear==Q->front+1
    C. Q->front==(Q->rear+1)%n
    D. Q->front==(Q->rear-1)%n

    设数组Data[n]作为循环队列Q的存储空间,front为队头指针,rear为队尾指针,则执行入队操作的语句为( )。
    A Q->rear=(Q->rear+1)%(n+1)
    B Q->front=(Q->front+1)%n
    C Q->rear=(Q->rear+1)%n
    D Q->front=(Q->front+1)%(n+1)

    3、设计一个判别表达式中括号是否配对的算法,采用( )数据结构最佳。
    A. 顺序表
    B. 链表
    C. 队列
    D. 栈

    4、带头结点的单链表head为空的判定条件是( )。
    A. head==NULL 
    B. head->next==NULL
    C. head->next!=NULL
    D. head!=NULL

    5、一个栈的输入序列为:1,2,3,4,则栈的不可能输出的序列是( )。
    A. 1243
    B. 2134
    C. 1432
    D. 4312
    E. 3214

    6、若用一个大小为6的数组来实现循环队列,且当rear和front的值分别为0,3。当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。
    A. 1和5
    B. 2和4
    C. 4和2
    D. 5和1

    7、队列的插入操作是在( )。
    A. 队尾
    B. 队头
    C. 队列任意位置
    D. 队头元素后

    8、循环队列的队头和队尾指针分别为front和rear,则判断循环队列为空的条件是( )。
    A. front==rear
    B. front==0
    C. rear==0
    D. front=rear+1

    9、一个顺序栈S,其栈顶指针为top,则将元素e入栈的操作是( )。
    A. *S->top=e;S->top++;
    B. S->top++;*S->top=e;
    C. *S->top=e
    D. S->top=e;

    10、表达式a*(b+c)-d的后缀表达式是( )。
    A. abcd± 
    B. abc+d-
    C. abc
    +d-
    D. -+*abcd

    11、将递归算法转换成对应的非递归算法时,通常需要使用( )来保存中间结果。
    A. 队列
    B. 栈
    C. 链表
    D. 树

    12、栈的插入和删除操作在( )。
    A. 栈底
    B. 栈顶
    C. 任意位置
    D. 指定位置

    13、五节车厢以编号1,2,3,4,5顺序进入铁路调度站(栈),可以得到( )的编组。
    A. 3,4,5,1,2
    B. 2,4,1,3,5
    C. 3,5,4,2,1
    D. 1,3,5,2,4

    14、判定一个顺序栈S(栈空间大小为n)为空的条件是( )。
    A. S->top==0
    B. S->top!=0
    C. S->top==n
    D. S->top!=n

    15、在一个链队列中,front和rear分别为头指针和尾指针,则插入一个结点s的操作为( )。
    A. front=front->next
    B. s->next=rear;rear=s
    C. rear->next=s;rear=s;
    D. s->next=front;front=s;

    16、一个队列的入队序列是1,2,3,4,则队列的出队序列是( )。
    A. 1,2,3,4 
    B. 4,3,2,1
    C. 1,4,3,2
    D. 3,4,1,2

    17、依次在初始为空的队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时的队头元素是( )。
    A. a
    B. b
    C. c
    D. d

    18、正常情况下,删除非空的顺序存储结构的堆栈的栈顶元素,栈顶指针top的变化是( )。
    A. top不变
    B. top=0
    C. top=top+1
    D. top=top-1

    19、判断一个循环队列Q(空间大小为M)为空的条件是( )。
    A. Q->front==Q->rear
    B. Q->rear-Q->front-1==M
    C. Q->front+1=Q->rear
    D. Q->rear+1=Q->front

    20、设计一个判别表达式中左右括号是否配对出现的算法,采用( )数据结构最佳。
    A. 线性表的顺序存储结构
    B. 队列
    C. 栈
    D. 线性表的链式存储结构

    21、当用大小为N的数组存储顺序循环队列时,该队列的最大长度为( )。
    A. N 
    B. N+1
    C. N-1
    D. N-2

    22、队列的删除操作是在( )。
    A. 队首 
    B. 队尾
    C. 队前
    D. 队后

    23、若让元素1,2,3依次进栈,则出栈次序不可能是( )。
    A. 3,2,1 
    B. 2,1,3
    C. 3,1,2
    D. 1,3,2

    24、循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是( )。
    A. (rear-front+m)%m
    B. rear-front+1
    C. rear-front-1
    D. rear-front

    循环队列是空队列的条件是( )。
    A Q->rear= =Q->front
    B (Q->rear+1)%maxsize= =Q->front
    C Q->rear= =0
    D Q->front= =0

    25、在解决计算机主机和打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个( )结构。
    A. 堆栈
    B. 队列
    C. 数组
    D. 线性表

    26、栈和队列都是( )。
    A. 链式存储的线性结构
    B. 链式存储的非线性结构
    C. 限制存取点的线性结构
    D. 限制存取点的非线性结构

    27、在一个链队列中,假定front和rear分别为队头指针和队尾指针,删除一个结点的操作是( )。
    A. front=front->next
    B. rear= rear->next
    C. rear->next=front
    D. front->next=rear

    28、队和栈的主要区别是( )。
    A. 逻辑结构不同
    B. 存储结构不同
    C. 所包含的运算个数不同
    D. 限定插入和删除的位置不同

    在作退栈运算时应先判别栈是否( )。
    A
    B 满
    C 上溢
    D 下溢

    在作进栈运算时,应先判别栈是否( )。
    A 空
    B
    C 上溢
    D 下溢

    若栈采用顺序存储方式存储,现两栈共享空间V[1…m],top[1]、top[2]分别代表第1和第2个栈的栈顶,栈1的底在V[1],栈2的底在V[m],则栈满的条件是( )。
    A |top[2]-top[1]|=0
    B top[1]+1=top[2]
    C top[1]+top[2]=m
    D top[1]=top[2]

    一个队列的入列序列是1234,则队列的输出序列是( )。
    A 4321
    B 1234
    C.1432
    D 3241

    以数组Q[0,…,m-1]存放循环队列中的元素,变量rear和qulen分别指示循环队列中队尾的实际位置和当前队列中元素的个数,队列第一个元素的实际位置是( )。
    A rear-qulen
    B rear-qulen+m
    C m-qulen
    D 1+(rear+m-qulen)%m

    已知队列(4,41,5,7,18,26,15),第一个进入队列的元素是4,则第5个出队列的元素是( )。
    A 5
    B 41
    C 18
    D 7

    栈结构通常采用的两种存储结构是( )
    A 顺序存储结构和链式存储结构
    B 散列方式和索引方式
    C 链表存储结构和数组
    D 线性存储结构和非线性存储结构

    设长度为n的链队列单循环链表表示,若只设头指针,则入队操作的时间复杂度为( )
    A O(1)
    B O(log2n)
    C O(n)
    D O(n2)

    在栈中,存取数据的原则是( )
    A 先进先出
    B 先进后出
    C 后进后出
    D 随意进出

    在栈中,出栈操作的时间复杂度是( )
    A O(1)
    B O(log2n)
    C O(n)
    D O(n2)

    在顺序栈中删除一个元素,至少要移动( )元素。
    A 0
    B 1
    C n/2
    D n

    插入和删除只能在一端进行的线性表,称为( )
    A 队列
    B 循环队列
    C
    D 循环栈

    表示一个栈ST(最多元素为m0)为栈空的条件是( )。
    A ST->top!=0
    B ST->top==0

    C ST->top!=m0
    D ST->top==m0

    最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是( )
    A (rear+1)%n==front
    B rear==front
    C rear+1==front
    D (rear-l)%n==front

    链栈与顺序栈相比,比较明显的优点是( )。
    A 插入操作更加方便
    B 删除操作更加方便
    C 不会出现下溢的情况
    D 不会出现上溢的情况

    在作退栈运算时应先判别栈是否( )。
    A
    B 满
    C 上溢
    D 下溢

    若栈顶指针指向栈顶元素,当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )
    A n-1
    B n
    C n+1
    D n/2

    以下( )不是队列的基本运算
    A 从队尾插入一个新元素
    B 从队列中删除第i个元素
    C 判断一个队列是否为空
    D 读取队头元素的值

    填空题

    向量、栈和队列都是 线性 结构,可以在向量的 ==任何 == 位置插入和删除元素;对于栈只能在 栈顶 == 插入和删除元素;对于队列只能在 == 队尾 == 插入和 == 队首 删除元素。
    一个顺序栈一旦被声明,其占用空间的大小( )。
    答案:已固定

    链栈和顺序栈相比,有一个比较明显的缺点,即( )。
    答案:通常不会出现栈满的情况

    用单链表表示的链式队列的队头在链表的( )位置。
    答案:链头

    在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入缓冲区中,而打印机则从缓冲区中取出数据打印,该缓冲区应该是
    一个( )结构。
    答案:队列

    循环队列 A[m] 存放其元素,用 front 和 rear 分别表示队头及队尾,则循环队列满的条件是( )。
    答案:(rear+1)%m=front

    在一个栈顶指针为 top 的链栈中,将一个 p 指针所指的结点入栈,应执行( )。
    答案:p->next=top; top=p;

    在一个栈顶指针为 top 的链栈中删除一个结点时,用 x 保存被删结点的值,则执行( )。
    答案:x=top->data; top=top->next;

    在一个链队中,设 front 和 rear 分别为队首和队尾指针,则插入 p 所指结点时,应执行( )。
    答案:rear->next=p;rear=p;

    在链队列中,f 和 r 分别为队头和队尾指针,要把 s 所指结点入队,应执行( )。
    答案:r->next=s;r=s;

    设 top 是一个链栈的栈顶指针,栈中每个结点由一个数据域 data 和指针域 next 组成,设用 x 接收栈顶元素,则取栈顶元素的操作为( )。
    答案:x=top->data;

    一个队列的入队序列是 2,4,6,8,则队列的输出序列是( )。
    答案:2,4,6,8

    一个栈的进栈序列是 5,6,7,8,则栈的不可能的出栈序列是( )。(进出栈操作可以交替进行)

    5,8,6,7

    栈的插入删除操作在( )进行。
    答案:栈顶

    栈和队列的相同点是( )。

    逻辑结构与线性表相同,都是操作规则受到限制的线性表

    以下说法正确的是( )。

    栈的特点是先进后出,队列的特点是先进先出

    设有一个带头结点的链队列,队列中每个结点由一个数据域 data 和指针域 next 组成,front 和 rear 分别为链队列的头指针和尾指针。设 p 指向要入队的新结点(该结点已被赋值),则入队操作为( )。
    答案:rear->next=p;rear=p;

    设有一个带头结点的链队列,队列中每个结点由一个数据域 data 和指针域 next 组成,front 和 rear 分别为链队列的头指针和尾指针,要执行出队操作,用 x 保存出队元素的值,p 为指向结点类型的指针,可执行如下操作:p=front->next;x=p->data;然后指行( )。
    答案:front->next=p->next;

    以下说法不正确的是( )。

    顺序队列中,当尾指针已经超越队列存储空间的上界,则一定是队列已满

    一个递归算法必须包括( )。

    终止条件和递归部分

    假定一个链式队列的队头和队尾指针分别为 front 和 rear,则判断队空的条件为( )。

    front=rear
    

    向顺序栈中压入新元素时,应当( )。

    应当先移动栈顶指针,再存入元素

    判断一个循环队列 Q(最多元素为 m)为满的条件是( )。

    答案:Q->front==(Q->rear+1)%m

    判断栈满(元素个数最多 n 个)的条件是( )。

    答案:top=n-1

    队列的删除操作是在( )。

    答案:队前

    一个队列的入队序列是 a,b,c,d,按该队列的可能输出序列使各元素依次入栈,该栈的可能输
    出序列是 ( )。(进栈出栈可以交替进行)。

    答案:d,c,b,a

    带表头结点的空循环双向链表的长度等于 0
    在这里插入图片描述

    判断题

    队列是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。( )
    正确的答案是“

    两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片空间的两端。( )
    正确的答案是

    对采用链式存储结构的堆栈进行操作不必判断溢出。( )

    正确

    采用循环链表作为存储结构的队列称为循环队列。( )

    错误

    链接队列不存在溢出问题。( )

    错误

    栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。( )

    正确

    没有元素的堆栈称为空栈,空栈用不着栈顶指针。( )

    错误

    线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。

    错,线性表是逻辑结构概念,可以顺序存储或链式存储,与元素数据类型无关。

    在表结构中最常用的是线性表,栈和队列不太常用。

    错,不一定吧?调用子程序或函数常用,CPU中也用队列。

    栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。

    对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。

    正确,都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。

    栈和链表是两种不同的数据结构。

    错,栈是逻辑结构的概念,是特殊殊线性表,而链表是存储结构概念,二者不是同类项

    栈和队列是一种非线性数据结构。

    错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。

    两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。

    答:对

    简答题

    说明线性表、栈与队的异同点。

    答:相同点:都是线性结构,都是逻辑结构的概念。都可以用顺序存储或链表存储;栈和队列是两种特殊的线性表,即受限的线性表,只是对插入、删除运算加以限制。
    不同点:①运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入、删除运算,因而是后进先出表LIFO;队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO。
    ② 用途不同,堆栈用于子程调用和保护现场,队列用于多道作业处理、指令寄存及其他运算等等。

    设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站的所有可能的顺序。

    答:至少有14种。
    ① 全进之后再出情况,只有1种:4,3,2,1 ② 进3个之后再出的情况,有3种,3,4,2,1 3,2,4,1
    3,2,1,4 ③ 进2个之后再出的情况,有5种,2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3
    2,1,3,4 ④ 进1个之后再出的情况,有5种,1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

    顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满?

    答:一般的一维数组队列的尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。
    采用循环队列是解决假溢出的途径。 另外,解决队满队空的办法有三: ① 设置一个布尔变量以区别队满还是队空;
    ② 浪费一个元素的空间,用于区别队满还是队空。 ③ 使用一个计数器记录队列中元素个数(即队列长度)。
    我们常采用法②,即队头指针、队尾指针中有一个指向实元素,而另一个指向空闲元素。
    判断循环队列队空标志是: f=rear
    队满标志是:f=(r+1)%N

    设循环队列的容量为40(序号从0到39),现经过一系列的入队和出队运算后,有
    ① front=11,rear=19; ② front=19,rear=11;问在这两种情况下,循环队列中各有元素多少个?

    答:用队列长度计算公式: (N+r-f)% N
    ① L=(40+19-11)% 40=8
    ② L=(40+11-19)% 40=32

    写出下列程序段的输出结果(队列中的元素类型QElem Type为char)。

    void main( ){
    Queue Q;  Init Queue (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);
    }
    

    答:输出为“char”。

    展开全文
  • 数据结构——的详解

    万次阅读 多人点赞 2020-04-20 00:02:43
    和队列是两种重要的线性结构,从数据结构的角度看,和...C语言和C++中的C语言中的栈栈的定义C语言中的基本操作的初始化判断是否为空栈判断是否为满栈入栈出栈C语言实现的具体代码C++中的C++中的基...

    栈和队列是两种重要的线性结构,从数据结构的角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表的子集。他们是操作受限的线性表,因此,可称为限定性的数据结构。但从数据类型角度看,他们是和线性表大不相同的两类重要的的抽象数据类型。

    C语言中的栈

    栈的定义

    栈(stack)是限定仅在表尾进行插入或者删除的线性表。对于栈来说,表尾端称为栈顶(top),表头端称为栈低(bottom)。不含元素的空表称为空栈。因为栈限定在表尾进行插入或者删除,所以栈又被称为后进先出的线性表(简称LIFO:Last in, First out.结构)。
    栈的示意图

    C语言中栈的基本操作

    栈的基本操作主要有:栈的初始化、判空、判满、取栈顶元素、在栈顶进行插入和删除。在栈顶插入元素称为入栈,在栈顶删除元素称为出栈

    栈的初始化

    栈和线性表类似,也有两种存储表示方法顺序栈链栈,链栈的操作是线性表操作的特例,操作比较容易实现。顺序栈即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置,top = 0表示空栈。由于栈在使用的过程中所需要的大小难以估计,所以通常是先为栈分配一个基本容量,然后再使用的过程中,当栈的空间不够使用的时候再继续追加存储空间。我们以下述类型说明作为顺序栈的定义:

    typedef struct{
    	SDataType *base; //栈底指针
    	SDataType *top;  //栈顶指针
    	int StackSize;   //当前已经分配的存储空间,以元素为单位 
    }SqStack;
    

    栈的初始化操作为:按照设定的初始分配量进行第一次存储分配,这里使用==malloc()==函数来分配存储空间。malloc()函数的详细说明请看:malloc详细说明。base作为栈底指针,它始终指向栈底,所以s.top = s.base可以作为栈空的标记。top为栈顶指针,top的初值指向栈底。每当插入一个元素时top加1,弹出一个元素时top减1,因此,非空栈中的栈顶指针始终在栈顶元素的下一个位置上
    栈顶指针和栈中元素的关系图

    //初始化顺序栈,构造一个空栈
    Status InitStack(SqStack &S){
    	//分配存储空间 
    	S.base = (SDataType *)malloc(STACK_INIT_SIZE*sizeof(SDataType));
    	if(!S.base){
    		//如果分配失败,则返回error 
    		return OVERFLOW;
    	}
    	//S.top 始终指向栈顶元素的下一个位置 
    	S.top = S.base;    //初始状态下为空栈 
    	S.StackSize = STACK_INIT_SIZE;   //当前已经分配的存储容量为100个 
    	return OK;	
    }
    

    判断是否为空栈

    当我们弹出栈顶元素时,往往需要判断一下栈是否为空来防止发生下溢。上面我们说到==base作为栈底指针,它始终指向栈底,所以s.top = s.base可以作为栈空的标记。==所以我们可以这样判断栈是否为空:

    //判断是否为空栈
    void judgeNull(SqStack &s){
    	if(s.top == s.base){
    		printf("此栈为空栈!\n");
    	}else{
    		printf("此栈不为空栈!\n");
    	}
    }
    

    判断是否为满栈

    当我们使一个元素入栈的之前,我们往往需要判断一下栈是否为满栈,防止发生上溢的情况。因为我们定义了一个StackSize来表示当前已经分配的存储空间,所以我们可以用s.top - s.base 来算出当前已经使用的栈空间。所以当s.top - s.base == s.StackSize 时表示已经满栈:

    //判断是否为满栈
    void judgeFull(SqStack &s){
    	if(s.top-s.base == s.StackSize){
    		printf("栈满!\n");
    	}else{
    		printf("栈未满!\n");
    	} 
    }
    

    入栈

    入栈时我们首先要判断栈是否为满栈,如果为满栈我们要首先追加存储空间,然后才能将元素入栈。realloc()函数详解请看realloc详解

    //入栈
    Status Push(SqStack &s,SDataType e){
    	SDataType *p;
    	//首先判断栈是不是满的(上溢) 
    	if(s.top-s.base == s.StackSize){
    		//追加空间 
    		p = (SDataType *)realloc(s.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SDataType));
    		if(!p){
    			//如果没有找到符合条件的存储空间,则返回error 
    			return OVERFLOW;
    		}
    		//成功找到则使s.base指向p 
    		s.base = p;
    		s.top = s.base + s.StackSize;
    		s.StackSize +=  STACKINCREMENT;
    	}
    	//先插入元素,然后将栈顶指针加 1 
    	*(s.top) = e;
    	s.top++;
    	return OK;
    }
    

    出栈

    出栈时我们首先要判断栈是否为空栈。如果栈已经空了,则返回error。

    //出栈
    Status Pop(SqStack &s,SDataType &e){
    	//判断是否会发生下溢 
    	if(s.top != s.base){
    		s.top--;    //先将栈顶指针减 1 
    		e = *(s.top);
    	}else{
    		return 0;
    	}
    	return e;
    }
    

    C语言实现栈的具体代码

    #include<stdio.h>
    #include<malloc.h>
    
    #define STACK_INIT_SIZE 100  //栈的初始容量 
    #define STACKINCREMENT 10    //容量增量
    #define OK 1 
    #define OVERFLOW -2
    typedef int SDataType;
    typedef int Status;
    
    typedef struct{
    	SDataType *base; //栈底指针
    	SDataType *top;  //栈顶指针
    	int StackSize;   //当前已经分配的存储空间,以元素为单位 
    }SqStack;
    
    //初始化顺序栈,构造一个空栈
    Status InitStack(SqStack &S){
    	//分配存储空间 
    	S.base = (SDataType *)malloc(STACK_INIT_SIZE*sizeof(SDataType));
    	if(!S.base){
    		//如果分配失败,则返回error 
    		return OVERFLOW;
    	}
    	//S.top 始终指向栈顶元素的下一个位置 
    	S.top = S.base;    //初始状态下为空栈 
    	S.StackSize = STACK_INIT_SIZE;   //当前已经分配的存储容量为100个 
    	return OK;	
    } 
    
    //入栈
    Status Push(SqStack &s,SDataType e){
    	SDataType *p;
    	//首先判断栈是不是满的(上溢) 
    	if(s.top-s.base == s.StackSize){
    		//追加空间 
    		p = (SDataType *)realloc(s.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SDataType));
    		if(!p){
    			//如果没有找到符合条件的存储空间,则返回error 
    			return OVERFLOW;
    		}
    		//成功找到则使s.base指向p 
    		s.base = p;  //系统会将原来的内容复制过来
    		s.top = s.base + s.StackSize;
    		s.StackSize +=  STACKINCREMENT;
    	}
    	//先插入元素,然后使栈顶指针加 1 
    	*(s.top) = e;
    	s.top++;
    	return OK;
    } 
    
    //出栈
    Status Pop(SqStack &s,SDataType &e){
    	//判断是否会发生下溢 
    	if(s.top != s.base){
    		s.top--;    //先将栈顶指针减 1 
    		e = *(s.top);
    	}else{
    		return 0;
    	}
    	return e;
    }
    
    //判断是否为空栈 
    void judgeNull(SqStack &s){
    	if(s.top == s.base){
    		printf("此栈为空栈!\n");
    	}else{
    		printf("此栈不为空栈!\n");
    	}
    }
    
    //判断是否为满栈
    void judgeFull(SqStack &s){
    	if(s.top-s.base == s.StackSize){
    		printf("栈满!\n");
    	}else{
    		printf("栈未满!\n");
    	} 
    } 
    
    int main(){
    	SqStack s;
    	SDataType element;
    	
    	InitStack(s);  //初始化栈
    	//将1-5入栈
    	for(int i=1;i<=10;i++){
    		Push(s,i);
    	}
    	
    	judgeNull(s);
    	judgeFull(s);
    	
    	printf("出栈:\n");
    	//只要栈不为空 
    	while(s.top != s.base){
    		Pop(s,element);    //出栈的元素用e接收 
    		printf("%d ",element);
    	}
    	
    	printf("\n"); 
    	judgeNull(s);
    	
    	return 0;
    	 
    } 
    

    C++中的栈

    C++ 对模板(Template)支持得很好,STL 就是借助模板把常用的数据结构及其算法都实现了一遍,并且做到了数据结构和算法的分离。STL的代码从广义上讲分为三类:algorithm(算法)、container(容器)和iterator(迭代器),几乎所有的代码都采用了模板类和模版函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中,STL被组织为下面的13个头文件:<algorithm >、<deque >、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。其中的<stack>就是栈。

    C++的STL已经将栈的操作都封装成了函数,我们只需要引进#include<stack>头文件即可使用。

    C++中栈的基本操作

    初始化

    我们可以直接使用stack<int> s;来创建一个空的 stack 对象。

    判断是否为空栈

    使用empty()函数来判断栈是否为空。
    empty()函数详解

    入栈

    使用push()函数来完成入栈操作。
    push()函数详解

    出栈

    使用pop()函数实现出栈
    pop()函数详解

    返回栈顶元素

    使用top()函数返回栈顶元素
    top()函数详解

    返回栈中元素数目

    使用size()函数返回栈中元素的数目。
    size()函数详解


    以上就是C语言和C++中栈的基本用法了,如果你觉得我的文章对你有用请点个赞支持一下吧,如果喜欢我写的文章那么请点个关注再走。
    嘿嘿
    下一篇将继续写数据结构的队列,后续将会再写一些有关栈和队列的具体应用。我是ACfun:一个成长中的程序猿,感谢大家的支持。

    展开全文
  • Java实现一个简单的栈将十进制转为二进制、八进制、十六进制打印输出 栈的主要方法: push(); //入栈 pop(); //出栈并返回栈顶值 empty(); //判断栈是否为空 peek(); //获取栈顶的值 search(elem); //判断元素elem...
  • 数据结构 实验三 的基本运算

    千次阅读 2020-10-07 21:42:30
    栈的基本运算 任务: 顺序栈的基本操作 任务描述: 本关任务:实现顺序栈的基本操作,...栈未满才执行以下进栈操作 s->top++; s->data[s->top]=x; - 出栈 出栈操作需要判断栈是否为空 栈空条件:s->to
  • 【数据结构】两共享空间的进一步理解

    千次阅读 多人点赞 2019-01-03 23:03:55
    栈满条件的理解: 总结  前言 在阅读《大话数据结构》时,对文中“两共享空间”中部分知识点存在困惑,多读了几遍后,将其中的疑惑进行梳理一下。 (关于书中“两共享空间”的知识点,大家可以看一下我...
  • B A.-15 B.15 C.-20 D.20 2-15假定利用数组a[n]顺序存储一个栈,用top表示栈顶指针,用top==-1表示栈空,并已知栈未满,当元素x进栈时所执行的操作为(C)。 A.a[–top]=x B.a[top–]=x C.a[++top]=x D.a[top++]=x ...
  • 共享存储空间算法

    千次阅读 2017-12-26 07:50:37
    对于一个栈,我们只能经理设计出合适大小的数组进行处理,但是对于2个相同类型的,我们可以共享其存储空间,最大限度的利用事先开辟的存储空间进行操作。 关键思路:他们是数组的两端,向中间靠拢。top1和...
  • 将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue) An algorithm to check for balancing symbols in an expression uses a stack to store
  • 数据结构:第3章和队列B.ppt
  • 数据结构和队列

    千次阅读 多人点赞 2020-11-08 16:00:06
    文章目录三、和队列3.1、和队列的定义和特点3.1.1、的定义和特点3.1.2、队列的定义和特点3.2、案例引入3.3、的表示和操作的实现3.3.1、的类型定义3.3.2、顺序的表示和实现3.3.3、链栈的表示和实现3.4、...
  • 牛客刷题笔记--(专项练习)

    千次阅读 2021-01-26 16:34:16
    使用一个数组来存储两个,让一个栈底为该数组的始端,另一个栈底为该数组的末端,每个从各自的端点向中间延伸 2 下列关于的叙述中,错误的是 。(I、Ⅲ、Ⅳ) Ⅰ.采用非递归方式重写递归程序时必须...
  • 计算机软件基础:12第四章数据结构_队列.doc
  • 第三章 和队列 的实现

    千次阅读 多人点赞 2020-06-22 21:52:49
    第三章 和队列   大家好,我叫亓官劼(qí guān jié ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博客地址为:亓官劼的博客 本文原创为亓官劼,请大家支持原创,部分平台... 初始化一个空栈S
  • 《数据结构》判断题中的错误表述 第1章 绪论: 1. 数据元素是数据的最小单位 × (数据元素是数据的基本单位,数据项是数据的最小单位) 2. 数据对象就是组数据元素的集合 × (这里强调数据元素的性质相同) 3. ...
  • 数据结构 -- 和队列的实现及应用

    万次阅读 多人点赞 2018-09-06 18:04:39
    1、 1.1 的定义 1.2 的顺序存储结构实现 顺序的操作示意图如下: 顺序的实现如下: 1.3 的链式存储结构实现 链栈的操作示意图如下: 链栈的实现如下: 1.4 两种的效率分析 1.5 的应用 破...
  • 数据结构:和队列(Stack & Queue)【详解】

    万次阅读 多人点赞 2021-02-18 19:52:33
    和队列知识框架 一、的基本概念 1、的定义 (Stack):是只允许在一端进行插入或删除的线性表。首先是一种线性表,但限定这种线性表只能在某一端进行插入和...S):初始化一个空栈S。 StackEmpty(S):
  • 一文读懂堆与的区别

    万次阅读 多人点赞 2018-06-29 15:24:05
    堆(Heap)与(Stack)是开发人员必须面对的两概念,在理解这两概念时,需要放到具体的场景下,因为不同场景下,堆与代表不同的含义。一般情况下,有两层含义: (1)程序内存布局场景下,堆与表示的是...
  • 在处理链表的后一半元素时,当访问到链表的一个元素后,就从中弹出一个元素,两个元素比较,若相等,则将链表中的下一个元素与中再弹出的元素比较,直至链表到尾。这时若是空栈,则得出链表中心对称的结论;...
  • 第三章 和队列 队列

    千次阅读 多人点赞 2020-06-22 21:54:22
    第三章 和队列   大家好,我叫亓官劼(qí guān jié ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博客地址为:亓官劼的博客 本文原创为亓官劼,请大家支持原创,部分平台一直在盗取博主的...
  • 含超详细注释的完整且健壮的的三种实现方式代码: 顺序 // // main.c // SequenceStack // // Created by Eason on 2020/8/1. // Copyright © 2020 Eason. All rights reserved. // #include <stdio.h> ...
  • 顺序—基本操作的实现及简单应用(C语言)

    千次阅读 多人点赞 2020-12-02 17:53:28
    文章目录的顺序表示和实现以及简单应用(C语言)、顺序的基本概念二、代码实现:1.引入库2.读入数据总结 提示:以下是本篇文章正文内容,下面案例可供参考 、顺序的基本概念 示例:pandas 是基于NumPy 的...
  • 线性表、、队列作业题

    千次阅读 2020-01-14 18:51:43
    、单选题(每题 2 分,共30分) (1)数据在计算机存储器内表示时,物理地址和逻辑地址相同并且是连续的,称之为 ( C )。 A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构 (2) 用链表表示线性表的优点是...
  • 与队列的特点,与队列的作用,与队列的实现,完整C语言代码
  • 在进行各类操作时,底指针固定不动,掌握空、栈满判断条件。 (2)实验内容 用顺序存储结构,实现教材定义的的基本操作,提供数制转换功能,将输入的十进制整数转换成二进制、八进制或十六进制。 (3)...
  • 首先说一个结论:链表,指的是链序存储的线性表。 1.单链表
  • ——概念、基本操作及其应用

    千次阅读 2021-03-12 10:21:15
    、pandas是什么? 示例:pandas 是基于NumPy 的种工具,该工具是为了解决数据分析任务而创建的。 二、使用步骤 1.引入库 代码如下(示例): import numpy as np import pandas as pd import matplotlib.pyplot ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,399
精华内容 8,559
关键字:

判断一个栈为满的条件

友情链接: a+b.zip