电梯机构的DataStructure

Question

这个问题是在公司面试时问我的--哪种数据结构对于实现电梯机制是有效的？

我无法找到它的有效的数据结构，即使在谷歌了很多次之后。

我可以想到优先级队列来实现it.Is优先级队列，有没有高效的数据结构或者更高效的数据结构来实现电梯机制？

谢谢!

Answer 1

由于您不能在软件中实现机制(尽管您肯定可以对它们进行建模)，因此我假设问题是关于的。

该算法看起来很简单，但即使手头有一组很好的数据结构，它的实现也令人惊讶地非常困难。用于此算法的一个很好的结构是三个优先级队列：

当前方向为

1. ，条目超过当前点，
2. 为相反方向，
3. 为当前点之前的当前方向。

您的实现将首先决定方向，然后选择一个队列来放置所请求的一对{from, to}值。

Answer 2

如果我们使用两个链表，一个用于向上移动请求，另一个用于向下移动请求。

例如

First request: a).while lift在0楼，3楼有请求。

用于向上移动的链表。

3->null。

用于向下移动的链表。

空。

第二个请求： b)。升降机已移至一楼，二楼有向上移动的要求。

用于向上移动的链表。

2->3->null

用于向下移动的链表。

空。

第三个请求： c)假设两个人进入2楼，一个人按下5楼的按钮，另一个人按下1楼的按钮。

用于向上移动的链表。

3->5->null

注意:此处2已从向上链表中删除，因为已到达。

用于向下移动的链表。

1->null。

D)假设一个人从3楼进入，按下0楼的按钮

用于向上移动的链表。

5->null

用于向下移动的链表。

1->0->null。

一旦到达第五层，向上请求链表变为空，因此可以考虑向下移动链表。

如果两个链表都为空，则电梯将处于静止状态。

所以我认为链表也可以作为电梯的一种有效的数据结构

Answer 3

为简单起见，让我们考虑单个电梯系统。

使用的数据结构:简单的列表用于存储floor#，枚举用于事件和状态。

系统可以是事件状态驱动的。用户行为或环境的每个方面都必须仔细考虑，以决定可以在电梯中使用的所有场景。

Events of the elevator : GOINGUP, GOINGDOWN, STOP 
States of the elevator : ONMOVE, WAITING (between door open and close), IDLE (serving no one), UNDERMAINTENANCE

Elevator movement is usually driven by two activites:
1. Press Up or Down key (before the entry gate of elevator) and wait for the elevator to come and serve you. (Press-And-Wait, say PAW) 
2. Enter inside the elevator and make request by pressing keys (Enter-And-Request, say EAR)

So it can said that PAW from outside and EAR from inside can decide the hops of the elevator. But what about direction?

Two possible types of PAW: PAWup (press Up button) and PAWdown (press Down button)

Now, EAR can be any of the three types depending upon the users behavior. These are the critical challenges in deciding the algorithm: 
1.) Normal - same direction as PAW (wanted to go down and enter lower floor#) 
2.) Opposite - wanted to go down BUT enter higher floor#
3.) Indecisive - Do Nothing, no key press

Now comes all the important rules:
RULE 1: If at IDLE, use FCFS to decide between the DownList front and UpList front - whoever is oldest, serve it first to ensure less waiting time. 
RULE 2: When both lists (DownList and UpList) are empty, move elevator to IDLE state. 
RULE 3: Elevator state change GOINGUP->STOP clears that floor# from UpList. Similarly, GOINGDOWN->STOP clears that floor from DownList.
RULE 4: Absolute Zero Skipping: GOINGxxx serves as many floors in xxxList as possible. 
RULE 5: Elevator doesn't favour Opposite-EAR, and obviously can't serve Indecisive-EAR.
RULE 6: Elevator in UNDERMAINTENANCE state is shunned from all external signals.
RULE 7: In the event of Power-cuts or Fire, the elevator goes and stops at Lobby. Flooding??

To achieve RULE#5, GOINGDOWN clears all the lower floor# in DownList in ONE GO. Similarly, GOINGUP clears all the higher floor# in UpList.    

Lets discuss one scenario to clear the above concepts:
Say, an elevator is resting at floor 7 is at IDLE state, 
    DownList : 
    UpList : 

IDLE@7 - PAWdown@12 then PAWup@9 then PAWdown@13
    DownList : 12, 13 (older requests at lower index.Push new requests at front.)
    UpList : 9 
    Using RULE#2, in the above case, 
    Event: GOINGUP to Pick@12.  

WAITING@12  - 12 cleared following RULE#3

MeanWhile, PAWup@8 then PAWup@10 then PAWdown@10, so updated lists are:
    DownList : 13, 10 
    UpList : 9, 8, 10

So here, in the current situation, if the EAR is
1.) Normal, GOINGDOWN(towards new EAR) is triggered.
2.) Opposite/Indecisive, GOINGDOWN(towards 9) is triggered and add the new EAR in UpList. 

使用上面提到的规则，电梯继续正常工作。