| <HTML> |
| <HEAD> |
| <TITLE>The queue Data Abstraction</TITLE> |
| <LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD> |
| <BODY BGCOLOR=#FFFFFF> |
| <A HREF="10-2.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="11.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV> |
| <H2>10.3 The queue Data Abstraction</H2> |
| <A NAME="idx194"><!></A> |
| <P>As a data abstraction, a <B><I><A HREF="../stdlibref/queue.html">queue</A></I></B> is traditionally defined as any object that implements the following operations given in <A HREF="10-3.html#Table 17">Table 17</A>:</P> |
| <H4><A NAME="Table 17">Table 17: Queue operations</A></H4> |
| <TABLE BORDER="1" CELLPADDING="3" CELLSPACING="3"> |
| <tr><td valign=top><B>Function</B> |
| </td><td valign=top><B>Implemented operation</B> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>empty()</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">Returns <SAMP>true</SAMP> if the collection is empty</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>size()</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">Returns number of elements in collection</P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>front()</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">Returns (but does not remove) the element at the front of the queue </P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>back()</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">Returns (but does not remove) the element at the end of the queue </P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>push(newElement)</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">Pushes a new element on to the end of the queue </P> |
| </td></tr> |
| <tr><td valign=top><P CLASS="TABLE"><SAMP>pop()</SAMP></P> |
| </td><td valign=top><P CLASS="TABLE">Removes (but does not return) the element at the front of the queue</P> |
| </td></tr> |
| </TABLE> |
| <P>Note that removing the element at the front of the <B><I><A HREF="../stdlibref/queue.html">queue</A></I></B> does not return a value. If the value of the element is important, you must retrieve the element before you remove the element</P> |
| <A NAME="1031"><H3>10.3.1 Include Files</H3></A> |
| <A NAME="idx195"><!></A> |
| <P>Programs that use the <B><I><A HREF="../stdlibref/queue.html">queue</A></I></B> data abstraction should include the <SAMP>queue</SAMP> header file:</P> |
| |
| <UL><PRE> |
| #include <queue> |
| </PRE></UL> |
| <A NAME="idx196"><!></A> |
| <A NAME="1032"><H3>10.3.2 Declaration and Initialization of queue</H3></A> |
| <A NAME="idx197"><!></A> |
| <P>A declaration for a <B><I><A HREF="../stdlibref/queue.html">queue</A></I></B> must specify the element type, and can also specify the container that will hold the values. For a <B><I>queue</I></B> the default container is a <B><I><A HREF="../stdlibref/deque.html">deque</A></I></B>, but a list can also be used. The <B><I><A HREF="../stdlibref/list.html">list</A></I></B> version is generally smaller, while the <B><I>deque</I></B> version may be slightly faster. The following are sample declarations for a <B><I>queue</I></B>:</P> |
| |
| <UL><PRE> |
| std::queue<int, list<int> > queueOne; |
| std::queue<double> queueTwo; // uses a deque |
| std::queue<Part*, list<Part*> > queueThree; |
| std::queue<Customer, list<Customer> > queueFour; |
| </PRE></UL> |
| <P>The last example creates a <B><I><A HREF="../stdlibref/queue.html">queue</A></I></B> of a user-defined type named <B><I>Customer</I></B>. As with the <B><I><A HREF="../stdlibref/stack.html">stack</A></I></B> container, all objects stored in a <B><I>queue</I></B> must understand <SAMP>operator<()</SAMP> and <SAMP>operator==()</SAMP>.</P> |
| <P>Because the <B><I><A HREF="../stdlibref/queue.html">queue</A></I></B> does not implement an iterator, few of the generic algorithms described in <A HREF="IV.html">Part IV</A> apply to <B><I>queue</I></B>s.</P> |
| <A NAME="idx198"><!></A> |
| <A NAME="1033"><H3>10.3.3 Example Program: Bank Teller Simulation</H3></A> |
| <BLOCKQUOTE><HR><B> |
| NOTE -- The complete version of the bank teller simulation program is in teller.cpp. |
| </B><HR></BLOCKQUOTE> |
| <A NAME="idx199"><!></A> |
| <P>Queues are often found in businesses, such as supermarkets or banks. Suppose you are the manager of a bank, and you need to determine how many tellers to have working during certain hours. You decide to create a computer simulation, basing your simulation on certain observed behavior. For example, you note that during peak hours there is a ninety percent chance that a customer will arrive every minute.</P> |
| <P>We create a simulation by first defining objects to represent both customers and tellers. For customers, the information we want to know is the average amount of time they spend waiting in line. Thus, customer objects simply maintain two integer data members: the time they arrive in line, and the time they spend at the counter. The latter is a value randomly selected between 2 and 8.</P> |
| |
| <UL><PRE> |
| class Customer |
| { |
| public: |
| |
| int arrivalTime; |
| int processTime; |
| |
| Customer (int at = 0) |
| : arrivalTime (at), |
| processTime (2 + irand () % 6) {} |
| |
| // are we done with our transaction? |
| bool done () { |
| return --processTime < 0; |
| } |
| |
| // order by arrival time |
| bool operator< (const Customer& c) const { |
| return arrivalTime < c.arrivalTime; |
| } |
| }; |
| </PRE></UL> |
| <P>Because objects can only be stored in a standard <B><I><A HREF="../stdlibref/queue.html">queue</A></I></B> if they can be compared for ordering, it is necessary to define <SAMP>operator<()</SAMP> for customers. Customers can also tell us when they are done with their transactions. Tellers are either busy servicing customers, or they are free. Thus, each teller value holds two data members: a customer, and a boolean flag. Tellers define a member function to answer whether they are free or not, as well as a member function that is invoked when they start servicing a customer.</P> |
| |
| <UL><PRE>class Teller |
| { |
| public: |
| Teller (): free (true) { } |
| |
| bool isFree () { // are we free to service new customer? |
| if (free) |
| return true; |
| if (customer.done()) |
| free = true; |
| return free; |
| } |
| |
| // start serving new customer |
| |
| void addCustomer (const Customer &c) { |
| customer = c; |
| free = false; |
| } |
| |
| private: |
| |
| bool free; |
| Customer customer; |
| }; |
| </PRE></UL> |
| <P>The main program, then, is a large loop cycling once each simulated minute. The probability is 0.9 that each minute a new customer is entered into the queue of waiting customers. Each teller is polled, and if any are free they take the next customer from the queue. Counts are maintained of the number of customers serviced and the total time they spent in queue. From these two values we can determine, following the simulation, the average time a customer spent waiting in the line.</P> |
| |
| <UL><PRE> |
| int main () |
| { |
| const int numberOfTellers = 5; |
| const int numberOfMinutes = 60; |
| double totalWait = 0; |
| int numberOfCustomers = 0; |
| |
| std::vector<Teller> teller (numberOfTellers); |
| std::queue<Customer> line; |
| |
| for (int t = 0; t < numberOfMinutes; t++) { |
| if (irand() % 10 < 9) |
| line.push (Customer (t)); |
| |
| for (int i = 0; i < numberOfTellers; i++) { |
| if (teller[i].isFree () && !line.empty ()) { |
| Customer& frontCustomer = line.front (); |
| numberOfCustomers++; |
| totalWait += t - frontCustomer.arrivalTime; |
| teller[i].addCustomer (frontCustomer); |
| line.pop (); |
| } |
| } |
| } |
| |
| std::cout << "average wait: " |
| << (totalWait / numberOfCustomers) << std::endl; |
| } |
| </PRE></UL> |
| <P>By executing the program several times, using various values for the number of tellers, the manager can determine the smallest number of tellers that can service the customers while maintaining the average waiting time at an acceptable level.</P> |
| |
| <BR> |
| <HR> |
| <A HREF="10-2.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="11.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A> |
| |
| <!-- Google Analytics tracking code --> |
| <script src="http://www.google-analytics.com/urchin.js" type="text/javascript"> |
| </script> |
| <script type="text/javascript"> |
| _uacct = "UA-1775151-1"; |
| urchinTracker(); |
| </script> |
| <!-- end of Google Analytics tracking code --> |
| |
| </BODY> |
| </HTML> |
