西安建筑科技大学：《数据结构与算法》课程教学资源（PPT电子教案）第二部分 栈、队列、递归方法_队列 Chapter 3 QUEUES（英文）

Chapter 3 QUEUES 1. Specifications for Queues 2. Implementation of Queues L3 Contiguous Queues in C++ L 4. Demonstration and Testing 5. Application: Airport Simulation 6. Pointers and Pitfalls

Chapter 3 QUEUES 1. Specifications for Queues 2. Implementation of Queues 3. Contiguous Queues in C++ 4. Demonstration and Testing 5. Application: Airport Simulation 6. Pointers and Pitfalls

3.1 Specifications for Queue rear A Queue is a data structure in which insertions take place at front one end and deletions take place at the opposite end. 票签 Characteristic: First In first out

A Queue is a data structure in which insertions take place at one end and deletions take place at the opposite end. 3.1 Specifications for Queue Characteristic: First In First Out 2 3 4 1 1 1 2 2 front rear

Queue: Queue; Post: The queue has been created and is initialized to be empty Error code Queue append (const Queue entry &x) Post: If there is space, x is added to the queue as its rear. otherwise an error code of overflow is returned

Queue :: Queue( ); Post: The Queue has been created and is initialized to be empty. Error_code Queue :: append(const Queue entry &x); Post: If there is space, x is added to the Queue as its rear.Otherwise an Error code of overflow is returned

Error code Queue serve(; Post: If the Queue is not empty, the front of the Queue has been removed otherwise an error code of underflow is returned Error code Queue: retrieve Queue entry &x)const Post: If the Queue is not empty the front of the Queue has been recorded as x. otherwise an Error code of underflow is returned

Error_code Queue :: serve( ); Post: If the Queue is not empty, the front of the Queue has been removed. Otherwise an Error code of underflow is returned. Error_code Queue::retrieve(Queue entry &x) const; Post: If the Queue is not empty, the front of the Queue has been recorded as x. Otherwise an Error code of underflow is returned

bool Queue empty()const; Post: Return true if the Queue is empty, otherwise return false Extended Queues class Extended queue: public Queue i public: bool full()const; int size const void clear; Error code serve and retrieve Queue entry &item

bool Queue :: empty( ) const; Post: Return true if the Queue is empty, otherwise return false. Extended Queues class Extended queue: public Queue { public: bool full( ) const; int size( ) const; void clear( ); Error_code serve and retrieve(Queue entry &item); };

目君 re a front a-aa front front (a)empty (b)a,, enter (c)ara-a out (d)aa,enter Exist what problem?

Exist what problem?

0 Circular max-2 enpty Implementation front rear of Queues max-1 front rear occupied implementation front rear occupied max-1 max-2

Circular Implementation of Queues

Boundary Conditions Queue containing one item front Remove the item empty q ueue rear front with one empty osition rear or Insert an item m的 rear front

Boundary Conditions

3.2 Implementations of Queues The physical model: a linear array with the front always in the first position and all entries moved up the array whenever the front is deleted o Alinear array with two indices always IncreasIng b a circular array with front and rear indices and one position left vacant

3.2 Implementations of Queues The physical model: a linear array with the front always in the first position and all entries moved up the array whenever the front is deleted. A linear array with two indices always increasing. A circular array with front and rear indices and one position left vacant

+ a circular array with front and rear indices and a boolean flag to indicate fullness(or emptiness ba circular array with front and rear indices and an integer counter of entries o a circular array with front and rear indices taking special values to indicate emptiness 3.3 Circular Implementation of Queues in C++

A circular array with front and rear indices and a Boolean flag to indicate fullness (or emptiness). A circular array with front and rear indices and an integer counter of entries. A circular array with front and rear indices taking special values to indicate emptiness. 3.3 Circular Implementation of Queues in C++