0

下面是我的数据结构课的教授幻灯片之一，我一直在做研究，无法弄清楚这里的概念，我必须在我的数据结构课上用它来构建一个程序。

.back 有什么作用？我们将什么发送到下面的实际功能中：请解释一下，就像我是一个 6 岁的孩子......

ADT-Queue（工具包函数数组实现）

//Create a q.
void create_queue(Queue & q)
{
    q.back = -1;
}

//check if Queue is empty
int empty( const QUEUE & q)
{
    return (q.back == -1);
}

//Purge elements in the queue
void purge(Queue & q)
{
    q.back = -1;
}

//Add an element on the q.
void enq(Queue & q, CONST INFOREC & item)
{
    ++ q.back;
q.i[q.back] = item; // i is an array of ints previously declared
}

// delete an item from the q
void deq(Queue &q, INFOREC & item)
{
    int ct; 
    item =q.i[0]; front;
    // step forward loop, moving the entire array components 1 place forward and
    // shifting the pointers
    for (ct = 1; ct < q.back; ++ct);
    q.i[ct -1] = q.i [ct];  
    --q.back;
 }
4

3 回答 3

1

编辑以反映问题中给出的新信息。

back是指向队列中最后一个元素的指针，也就是最近添加的元素。

与 一起i，这就是队列维护其内部数据结构所需的全部内容。由于i是静态分配的，并且元素仅使用 索引back，因此没有必要从队列中显式删除元素；这就是为什么不需要对 inside 进行i更改purge()。如果你添加元素，purge()或者deq()它们，然后添加更多元素，新元素只会覆盖内存中以前的元素，这正是你想要的；并且由于back在这些方法中的每一个中都进行了适当的调整，因此不可能访问逻辑上不再在队列中的数据成员，即使它们仍然存在于系统内存中。

请注意，“de”中的“de”deq不代表“delete”；deq是“dequeue”的缩写，它是从队列中检索最旧元素的标准术语。将元素添加到队列后面的相应术语是“入队”。

于 2013-03-21T03:33:32.553 回答
1

队列的前面在0，后面在q.back，所以队列为空时q.back初始化为-1。

检查队列是否为空，返回为 -1 时返回 true，否则返回 false：

bool empty(const Queue & q)
{
    return (q.back == -1);
}

purge 使队列再次为空，因此与 init 相同。

于 2013-03-21T03:37:49.317 回答
0

好的，我的猜测是 ADT 的设计方式是队列始终指向添加的第一个元素，并且back当队列中没有元素时始终为 -1。

检查create_queue，创建了一个新队列并且还没有元素入队，因此初始化back为 -1

同样empty，如果不存在任何元素，则back仍为 -1

在purge中，所有元素都被删除，因此back需要更新为 -1

所以如果有一个名为enqueue..的函数back将被更新为一个不是-1的值

PS:- 这是一个疯狂的猜测，因为在我们看到完整的代码之前我们无法预测 :)

*编辑*** 根据我建议的更新代码工作正常，如果队列为空，则返回-1...否则它的数组指向从 0 到 n-1(max_queue_size) ... 0 -->第一个元素

于 2013-03-21T03:45:36.180 回答