队列的定义

Implementations of Queues
template <typename T> Error_code Queue<T>::append(const T &item)
{ if(count >= maxqueue) return overflow; count++; rear = ((rear + 1) == maxqueue)?0:(rear +1); entry[rear] = item; return success;
void get_command() Post: Get a valid command from the user and reurn it.
bool do_command(char c, Extended_queue<int> & test_queue) /*Post: perform the given commands. return true if c != 'q'. */{
good.
Circular Queue
Circular arrays（循环数组）
• 将数组设想为一个循环的，而非线性的； • 用两个下标front和rear记录队头和队尾位置； • 添加元素时，rear右移，将元素置于rear位
置。当rear等于max时(last index), rear 置 0. • 元素出队时，删除位于front位置的元素，然
• Testing is the process of executing a program with the intent of finding errors.
• Errors: valid input produces invalid output. • Choosing those inputs which are likely to go
3. Extreme values. Many programs err at the limits of their range of applications.
4. Illegal values. A good program should output some sensible error message for invalid inputs.
char get_command(){ char command; bool waiting = true; cout <<"select a command and press enter:"<<endl; while (waiting) { cin >> command; command = tolower(command); if (command == 'a' || command == 'q' || command == 's' || command == 'r')
Check STL queue implementation.
Extended Queue operations
• If we want to add some operations on queues, for example, full, clear, serve_and_retrieve, one way is to extend the class Queue:
Definition of Queues
• 一个队列(queue) 是同类型元素的线性表，其中
插入在一端进行，删除在另一端进行。
• 删除进行的一端称为队头（ the front ，or the
head). 最新加入的元素称为队尾（The rear or tail）。
• 例子: 等待打印的任务构成一个队列；等待CPU 服务的任务构成一个队列等。
Linked queues
Append and Serve:
练习百度文库
试用一个bool变量区分队列空与不空（不使 用count）实现循环队列 • 写出 队列的class定义； • 说明队列空和队列满的条件分别是什么； • 完成队列的实现。
队列
演示与测试
Demonstration and testing
队列
队列的定义
Queues 队列
队列(Queues)是生活中“排队”的抽象。队列的 特点是：
–有穷个同类型元素的线形序列； –新加入的元素排在队尾，出队的元素在对头删
除，即入队和出队分别在队列的两端进行； –先来的先得到服务；故称为先进先出表 (FIFO,
first in first out).
Testing and debugging
• A classic book on testing, now also online: The art of software testing, Glenford Myers • Read chapter 7 about debugging to reduce
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
bool do_command(char c, Extented_queue <int> &test_queue)
Pre: c is a valid command Post: Perform the given command c on
test_queue. Return false if c ==‘q’ (quit), otherwise, return true
the front is removed. Poor!
Linear implementation(线性实现）
• Two indices（下标） to keep track of both the front and the rear of the queue
• To serve an entry, take the entry and increase the front by one
Queue using array.
bool empty() const;
Error_code append(const Queue_entry &x);
Error_code serve();
Error_code retrieve(Queue_entry &x)const;
};// the data part is left out
Check emptiness 检查队是否空
The Queue class
• The ADT Queue class:
class Queue { public: Queue();
Add more to make it a safe class. Write the data part and implement ADT
Circular Implementation of Queues
template <class T> class Queue { public: Queue(); bool empty() const; Error_code serve(); Error_code append(const T &item); Error_code retrieve(T &item) const; protected: unsigned maxqueue; int count; int front,rear; T entry[maxqueue]; };
your effort on debugging.
int main() /*Post: Accept commands from user and execute them */ {
Extended_queue <int> test_queue; introduction();// instructions for the user while (do_command(get_command(), test_queue)); }
• To verify the methods, we write a demonstration program.
• The program interactively accepts commands and prints the results, a kind of black box testing.
• Alternatively, we can automate the testing: generate a sequence of operations and compare two queues (one is assumed to be the standard) to see if they have the same state after each operation (See lab notes).
后front右移. 当front 等于 max时, 置 front 为 0。
Boundary conditions
rear
front
No difference
rear
front
remove
empty after deletion
rear insert
front
Full after addition
}
Implementations
template <typename T> Queue <T>::Queue() /*post: the queue is initialized to be empty*/ {
count =0; rear = maxqueue -1; // rear is just before the front position //when it is empty front = 0; }
bool continue_input = true; int x; switch(c) { case 'a'://append an item
if (test_queue.full()) cout <<"full!"<<endl; else {
cout << "input an integer:"<<endl; cin >> x; test_queue.append(x); }; break; case …. } return continue_input; }
class Extended_queue:public Queue { public: bool full() const; int size() const; void clear(); Error_code serve_and_retrieve(Queue_entry &item); };
队列
• To append an entry to the queue, increase the rear by one and put the entry in that position
• Problem: cannot reuse the discarded space • When the queue is regularly emptied, this is
rear
front
Boundary conditions
• 问题：无法区分满队列与空队列。 • 解决方法: 1. 在数组中空一个位置； 2. 使用一个布尔量表示队列是否满。当
rear刚好到达front之前时，置 此标志为 true. 3. 使用一个计数器（ counter）以记录队列 中的元素个数。
wrong, especially the boundary cases.
1. Easy values. Test the program with data that are easy to check.
2. Typical, realistic values. Always try a program on data chosen to represent how the program will be used.
Definition of Queues
Queue Operations
设 Queue_entry 表示队列元素的类型。
Constructor
Insertion （入队）
Queue Operations （2）
Deletion 出队
Get the front 取队头元素
Queue Operations (3)