这个问题是在公司面试时问我的——哪种数据结构对于实施电梯机制是有效的？
即使经过大量谷歌搜索，我也无法找到有效的数据结构。
我可以想到优先级队列来实现它。优先级队列是一种有效的数据结构还是更有效的数据结构来实现电梯机制？
谢谢！
问问题
48093 次
5 回答
33
由于您无法在软件中实现机制（尽管您当然可以对其进行建模），我认为问题是关于Elevator algorithm。
该算法看起来很简单，但实现起来却非常困难，即使手头有一套好的数据结构。该算法使用的一个很好的结构是三个优先级队列：
- 对于条目超过当前点的当前方向，
- 对于相反的方向，并且
- 对于当前点之前的当前方向。
您的实现将首先确定方向，然后选择一个队列来放置请求的一对{from, to}值。
于 2012-08-17T16:46:38.260 回答
14
如果我们使用两个链表，一个用于向上移动请求，另一个用于向下移动请求。
例如
第一个请求： a). 虽然电梯在 0 楼，但请求来到 3 楼。
向上移动的链表。
3->空。
向下移动的链表。
空值。
第二个请求： b）。电梯已移至 1 楼，而 2 楼提出向上移动的请求。
向上移动的链表。
2->3->空
向下移动的链表。
空值。
第三个请求： c) 假设 2 人进入 2 楼，一个人按下按钮进入 5 楼，另一个人进入 1 楼。
向上移动的链表。
3->5->空
注意：这里的 2 已经从上行链表中删除，因为它已经到达。
向下移动的链表。
1->空。
d) 假设一个人进入 3 楼并按下 0 楼的按钮
向上移动的链表。
5->空
向下移动的链表。
1->0->空。
一旦 iis 到达 5 楼，向上请求链表变为空，因此可以考虑移动向下链表。
如果两个链表都是空的，那么电梯将处于静止状态。
所以我认为链表也可以是电梯的有效数据结构
于 2015-07-01T17:13:33.803 回答
5
以下是设计电梯系统的一种方法。每个电梯都使用队列（可能是阻塞队列）来存储楼层请求。还有一个中央电梯管理器，它监控所有电梯队列，它可以根据一些业务规则将请求委托给某个电梯。ElevatorManager 的工作是有效地将请求委托给相关的电梯。下面的伪代码没有优化委托算法，但它显示了如何对电梯列表进行实际委托。
电梯系统所需的类：
ElevatorManager [Singleton - 这是管理建筑物中 n 部电梯的主电梯程序]
成员：
Floor.Request
的电梯
队列列表 // 这维护了两个方向的请求。一种改进可能是保留两个队列，每个方向一个，但它会增加复杂性
MIN_FLOOR
MAX_FLOOR
操作：
delgate()
halt() // 将整个电梯系统设置为维护模式或
停止操作 一座建筑物内可能有 n 部电梯]
会员：
楼层队列 // 这需要排序，因此可以使用 PriorityQueue
方向：枚举 [方向枚举 - 向上、向下、等待、空闲、维护]
CurrentFloor ：楼层
操作：
operate()
moveUp()
moveDown()
openDoor()
closeDoor()
callEmergencyLine()
getDirection()
getCurrentFloor()
setInMaintenanceMode()
楼层[代表各个楼层]
成员：
楼层数
类 Request {
currentFloor
destinationFloor
Direction [Up, Down]
}
操作：
goUp()
goDown()
上面组件的一些主要伪代码：
class Floor {
goUp() {
ElevatorManager.queue.offer(new Request(currentFloor, destinationFloor, up));
}
goDown() {
ElevatorManager.queue.offer(new Request(currentFloor, destinationFloor, down));
}
}
ElevatorManager {
delegate() {
// Instead of using one object, we could use a list to track idle and elevators moving in same direction so that these list could be used for next requests in queue
// but again to simplify pseudocode, I am using single objects instead of lists
Elevator idleElevator; // track idle elevator
Elevator elevatorMovingInSameDirection; // elevator moving in same direction as next request in main elevator manager queue
while(!halt()) { //keep delegating until powered down or whole system is halted through main controls
if(queue.peek() != null) {
Request req = queue.peek();
boolean startAgain = false; // flag to start from beginning if the request is already pushed to one of the elevators queue during iterating elevators
for(Elevator elevator : elevators) {
// first find if there is an elevator at current floor going in same direction as current request in queue
if(req.currentFloor == elevator.currentFloor && req.direction == elevator.direction) {
elevator.queue.offer(req.destinationFloor);
queue.poll(); // remove this request from Elevator Manager queue
startAgain = true;
break;
}
// check if this elevator is idle
if(elevator.direction == "idle")) {
idleElevator = elevator; // For this simple design, I am ok to overwrite idle elevator value and instead get the latest idle elevatior
}
// check if this elevator is moving in desired direction and elevator's current floor is behind desired floor in queue
if(elevator.direction == req.direction) {
// Make sure elevators moving in same direction should also be behind the floor where request is made
if(req.direction == "Up" && req.currentFloor - elevator.currentFloor > 0) {
elevatorMovingInSameDirection = elevator; // Same as above, it's ok to get this overwritten and instead get the latest elevator moving in same direction
}
// Make sure elevators moving in same direction should also be behind the floor where request is made
if(req.direction == "Down" && req.currentFloor - elevator.currentFloor < 0) {
elevatorMovingInSameDirection = elevator;
}
}
}
// Only delegate to other floors if you could not find elevator going in same direction at same floor from where the request was made
if(!startAgain && idleElevator != null) {
idleElevator.queue.offer(req.destinationFloor);
queue.poll();
}
// if we could neither find elevator at current floor nor idle elevator then send this request to elevator behind current Floor and moving in same direction as the request
if(!startAgain && elevatorMovingInSameDirection != null) {
elevatorMovingInSameDirection.queue.offer(req.destinationFloor);
queue.poll();
}
}
}
}
}
Elevator {
moveUp() {
this.currentFloor += 1;
}
moveDown() {
this.currentFloor -= 1;
}
operate() {
while(queue.peek() != null) {
Floor nextFloorInQueue = queue.peek();
while(this.currentFloor != nextFloorInQueue.request.destinationFloor) {
if(this.direction == "Up") {
moveUp();
} else if(this.direction == "down") {
moveDown();
}
}
queue.poll(); // remove the request from queue
open(); //open door
Direction backUpDirection = this.direction; //back up elevators direction to retrieve it later once dooor closes
this.direction = "idle"; // set state to idle to let elevatorManager know that requests at current floor could be offered to this elevator queue
Thread.sleep(10000); // sleep for 10 seconds so that people can leave elevator
close(); // once people are out close door to move to next floor in queue
this.direction = backUpDirection;
}
this.direction = "idle"; // once queue is empty set the direction to idle
}
}
它也可以在我的 Github 上找到：https ://github.com/prabhash1785/Java/blob/master/ObjectOrientedDesign/src/com/prabhash/java/design/objectoriented/elevator/ElevatorDesignWithPseudocode.md
于 2016-02-12T23:02:25.500 回答
2
为简单起见，让我们考虑一个 单一的电梯系统。
使用的数据结构：用于存储楼层#、事件和状态枚举的简单列表。
该系统可以由事件状态驱动。用户行为或环境的每个方面都必须在决定所有场景都可以扔到电梯上时加以注意。
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.
使用上述规则，电梯继续其正常工作。
于 2016-09-13T15:08:07.420 回答
1
拥有一个数组怎么样，其中每个数组条目代表一个楼层。当用户想停到某个楼层时，他会在阵列中标记该条目，如果电梯到达该楼层时，电梯将查看阵列并清除该条目。类似于 SCAN/CSAN 调度算法。我期待你的评论
于 2014-09-26T22:58:20.077 回答