rit*_*ITW 21 algorithm design-patterns data-structures
在公司采访中我问过这个问题 - 哪种数据结构对实施电梯机制有效？
即使经过大量谷歌搜索,我也无法找到有效的数据结构.
我可以想到优先级队列来实现它.优先级队列是一个有效的数据结构还是更有效的数据结构用于实现电梯机制？
谢谢!
das*_*ght 29
由于您无法在软件中实现机制(尽管您可以对它们进行建模),我认为问题一直是关于Elevator算法的.
该算法看起来很简单,但实现起来却非常困难,即使手头有很好的数据结构.用于此算法的良好结构是三个优先级队列:
您的实现将首先确定方向,然后选择一个队列,将所请求的{from, to}值对放入其中.
sac*_*shi 14
如果我们使用两个链表1用于向上方向移动请求而另一个用于向下方向移动请求怎么办
例如
第一个要求: a).当电梯在0楼,请求来到3楼.
向上移动的链表.
3->空.
向下移动的链表.
空值.
第二个要求: b).电梯已移至1楼,请求从2楼向上移动.
向上移动的链表.
2-> 3->空
向下移动的链表.
空值.
第三个要求: c)假设2人进入二楼,一个按下5楼按钮,另一个按下第1个按钮.
向上移动的链表.
3-> 5->空
注意:此处的2已从上传链表中删除.
向下移动的链表.
1->空.
d)假设一个人进入三楼并按下0楼的按钮
向上移动的链表.
5->空
向下移动的链表.
1-> 0->空.
一旦到达5楼iis,请求链表变为空,因此可以考虑向下链表进行移动.
如果链表都是空的,那么电梯将处于静止状态.
所以我认为链表也可以成为电梯的有效数据结构
以下是设计电梯系统的一种方法。每台电梯都使用队列（可以是阻塞队列）来存储楼层请求。还有一个中央 ElevatorManager，它监视所有电梯队列，并且可以根据某些业务规则将请求委托给特定电梯。ElevatorManager 的工作是将请求有效地委托给相关电梯。下面的伪代码没有优化委托算法，但它显示了如何对电梯列表进行实际委托。
电梯系统所需的类：
ElevatorManager [Singleton - 这是将管理建筑物中的 n 部电梯的主电梯程序]
成员：
Floor.Request 的
电梯队列列表
// 这维护两个方向的请求。一项改进可能是保留两个队列，每个方向一个，但这会增加复杂性
MIN_FLOOR
MAX_FLOOR
操作：
delgate()
halt() // 将整个电梯系统设置为维护模式或停止运行
电梯[代表各个电梯。建筑物中可能有 n 部电梯]
Members:
Floor Queue // 这需要排序，因此可以使用 PriorityQueue
Direction : Enum [方向枚举 - 向上、向下、等待、空闲、维护]
CurrentFloor : Floor
操作：
opera()
moveUp()
moveDown()
openDoor()
closeDoor()
callEmergencyLine()
getDirection()
getCurrentFloor()
setInMaintenanceMode()
Floor [代表各个楼层]
成员：
eNum of Floors
class 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/objectorient/elevator/ElevatorDesignWithPseudocode.md