Queues Linear list.
One end is called front.
Other end is called rear.
Additions are done at the rear only.
Removals are made from the front only.
Queues Linear list.
One end is called front.
Other end is called rear.
Additions are done at the rear only.
Removals are made from the front only.
By comparison, in a stack adds and removes are to/from the same end of he list.
Bus Stop Queue Bus Stop front rear rear rear rear rear
Bus Stop Queue Bus Stop front rear rear rear
Bus Stop Queue Bus Stop front rear rear
Bus Stop Queue Bus Stop front rear rear
This is FIFO queue. Some real life queues are not FIFO. Removal from a queue may be done by prioirty rather than by arrival time order. For example, loading into a plane– first class, frequent fliers, by rows from back of plane rather than by order in which you arrive at the departure gate.
Queue – formula based (b). Delete(x) , (c). Add(D)
ADT of Queue
Revisit Of Stack Applications Applications in which the stack cannot be replaced with a queue.
Parentheses matching.
Towers of Hanoi.
Switchbox routing.
Method invocation and return.
Try-catch-throw implementation.
Application in which the stack may be replaced with a queue.
Rat in a maze.
Results in finding shortest path to exit.
Wire Routing
Represent as a grid in which components and already placed wires are denoted by
blocked grid positions.
Lee’s Wire Router start pin end pin Label all reachable squares 1 unit from start.
Could use rat in a maze animation from Web site instead.
Blue squares are blocked squares. Orange squares are available to route a wire.
A queue of reachable squares is used. The queue is initially empty, and the start pin square/cell is the examine cell. This cell has a distance value of 0. Unreached unblocked squares adjacent to the examine cell are marked with their distance (this is 1 more than the distance value of the examine cell) and added to the queue. Then a cell is removed from the queue and made the new examine cell. This process is repeated until the end pin is reached or the queue becomes empty. Cells become examine cells in order of their distance from the start pin.
Lee’s Wire Router start pin end pin Label all reachable unlabeled squares 2 units from start. 1 1
Lee’s Wire Router start pin end pin Label all reachable unlabeled squares 3 units from start. 1 1 2 2 2 2 2
Lee’s Wire Router start pin end pin Label all reachable unlabeled squares 4 units from start. 1 1 2 2 2 2 2 3 3 3 3
Lee’s Wire Router start pin end pin Label all reachable unlabeled squares 5 units from start. 1 1 2 2 2 2 2 3 3 3 3 4 4 4 4 4
Lee’s Wire Router start pin end pin Label all reachable unlabeled squares 6 units from start. 1 1 2 2 2 2 2 3 3 3 3 4 4 4 4 4 5 5 5 5 5 5
Comments