Data structure (four)

The classmate said that I was too slow. Yes, I have been updated once. In fact, I also want to have a quick update, the soon the update, the faster I master the knowledge, the more. But work is not allowed. Every day, late, the idle implementation must also assign a little to foreign languages. However, I will work hard in the future, as long as there is a friend's support, I will dedicate my learning and experience to everyone. A little open source. Oh, of course, I have no qualification yet.

Remember, when you are school, whether in the class, on the courses, on the test paper, or ask questions in the teacher. The stack and queue will always be associated with the queue. This is fully illustrated that there is similarity in the stack and queue, and there is another difference. In the data structure (3), the stack is mentioned. It is a container that followed first, then what is the queue? I think you must guess, the queue is a container that first in the first out (FIFO). You see, the stacks and queues are put in front of you.

Linear queue and cycle queues are usually used to use two queues. In both queues, data items are inserted in the queue, then move to the team header and delete or get it from the queue header.

In order to help memories, we still give an example of an example. Give you half a minute, what example is more image? Ha ha! How do you think this example is the printer job? The printer has been used, and also knows.

Its speed is much slower than the computer, so the operating system assigns its print task to its print subsystem, and the print subsystem will insert these tasks into a print queue. The first task in the queue first prints first, and the last task is finally printed. How is it enough?

Here is an example in one cycle queue. As with the previous article, create a queue base class, then derive two subclasses, we use array and linked lists to be implemented separately.

#include "list.h" #include "array.h"

Template class queue {public: Virtual t & head () const = 0; Virtual void enqueue (T &) = 0; Virtual T & Dequeue () = 0; protected: int NLENGTH; int ncount;};

Array implementation method:

Template Class QueueArray: Public Queue {public: QueueArray (int NCNT) {ncount = 0; NHEAD = 0; NTAIL = 0; NLENGTH = NCNT; PARRAY = New Array (NCNT);

~ QueueArray () {if (null! = Parray) {delete parry;}}

T & Head () const {f (0 == ncount) {std :: domain_error ("queue is empty");} return (* parray) [nhead];

Void Enqueue (T & Value) {IF (ncount == NLENGTH) {std :: Domain_ERROR ("Queue Is Full");} IF ( ntail == Nlength) {ntail = 0;} else {--ntail;} (* parray) [NTAIL] = value; ntail; ncount;} T & dequeue () {if (0 == ncount) {std :: domain_error ("queue is empty");} t tell = (* PARRAY) [NHEAD]; if (nhead == nlength) {nHEAD = 0;} else { nhead;} ​​--ncount; return TRESULT;} private: array * parray; int nhead; int ntail;} ;

Link table implementation method: Template Class Queuelist: public queue {public: queuelist (int NCNT) {ncount = 0; NLENGTH = NCNT; PLIST = New LinkedList ();} ~ queuelist () { IF (null! = pList) {delete pList;}} T & head () const {= (0 == ncount) {std :: domain_error ("queue is empty");} return const_cast (plist-> gethead () -> getdatum ());} void enqueue (t & value) {if (NLENGTH == PLIST-> getLength ()) {std :: domain_error ("queue is full");} PLIST-> Append (Value) ncount;} T & deveue () {i (0 == ncount) {std :: domain_error ("queue is empty");} T truselt = plist-> getHead () -> getDatum (); plist-> DELELEMENT (1); - Ncount; Return Truselt;} private: LinkedList