Linked queues
Append and Serve:
练习
试用一个bool变量区分队列空与不空（不使 用count）实现循环队列 • 写出 队列的class定义； • 说明队列空和队列满的条件分别是什么； • 完成队列的实现。
队列
演示与测试
Demonstration and testing
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
good.
Circular Queue
Circular arrays（循环数组）
• 将数组设想为一个循环的，而非线性的； • 用两个下标front和rear记录队头和队尾位置； • 添加元素时，rear右移，将元素置于rear位
置。当rear等于max时(last index), rear 置 0. • 元素出队时，删除位于front位置的元素，然
class Extended_queue:public Queue { public: bool full() const; int size() const; void clear(); Error_code serve_and_retrieve(Queue_entry &item); };
队列
• 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
• 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).
Definition of Queues
Queue Operations
设 QБайду номын сангаасeue_entry 表示队列元素的类型。
Constructor
Insertion （入队）
Queue Operations （2）
Deletion 出队
Get the front 取队头元素
Queue Operations (3)
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)); }
后front右移. 当front 等于 max时, 置 front 为 0。
Boundary conditions
rear
front
No difference
rear
front
remove
empty after deletion
rear insert
front
Full after addition
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]; };
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
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'. */{
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; }
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
• To verify the methods, we write a demonstration program.
• The program interactively accepts commands and prints the results, a kind of black box testing.
• 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
}
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; }
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
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')
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.
rear
front
Boundary conditions
• 问题：无法区分满队列与空队列。 • 解决方法: 1. 在数组中空一个位置； 2. 使用一个布尔量表示队列是否满。当
rear刚好到达front之前时，置 此标志为 true. 3. 使用一个计数器（ counter）以记录队列 中的元素个数。