1

在大学里，教授要求我们设计一种算法来实现循环队列。我们必须为“remove()”和“insert()”函数编写算法。这是我经过数小时思考后得出的结论。

Declarations: q = circular queue structure that contains 3 elements 
                --> x[MAX] = array of MAX integers
                --> rear = logical pointer used for inserting elements at that particular index
                --> front = logical pointer used for deleting elements at that particular index
Predefined functions:
                --> incr (int y) : special function to set y to 0 once it contains MAX else do y++
                --> decr (int y) : special function to set y to MAX if it contains 0 else do y--

Preconditions : At the initial time of defining the structure set rear and front both at 0

Algorithm REMOVE(q): Returns an int
1.  set a <- q.x[q.front]
2.  incr (q.front) 
3.  if q.front >= q.rear 
    1.  decr (q.front)
    2.  print "Queue Empty"
    else
    1. return a

Algorithm INSERT(q,a) : Returns nothing
1.  incr (q.rear)
2.  if q.rear = q.front
    1.  decr (q.rear)
    2.  print "Queue Full"
    else
    1.  set q.x[q.rear] <- a

该算法使用“前”永远不会超过“后”的事实。因此，如果“前=后”增加“前”意味着队列为空。如果'rear = front'意味着队列已满，则增加'rear'。

但是当我向我的教授展示这个时，他说这不是解决方案。

这个逻辑不正确吗？如果是这样，这个算法的缺陷是什么？此外，如果可能，请提出改进​​建议。

（PS：我没有谷歌搜索解决方案的原因是因为我想自己实现这个。）

4

1 回答 1

0

如果您的队列初始化后的第一个操作是 REMOVE 请求，您的设置将失败。这样做的原因是您首先增加前索引，然后检查是否等于后索引以检测队列是空的还是满的。但是，在初始化之后，两个索引已经相等，而队列为空。

于 2013-08-24T06:14:05.240 回答