\u961f\u5217\u9075\u5faa\u5148\u8fdb\u5148\u51fa\uff08FIFO\uff09\u7684\u89c4\u5219\uff0c\u4e5f\u662f\u53ef\u4ee5\u7528\u6570\u7ec4\u6216\u94fe\u8868\u6765\u63cf\u8ff0<\/p>\n\n\n\n
\u6570\u7ec4\u5b9e\u73b0\u65b9\u5f0f\u4e2d\uff0c\u5faa\u73af\u961f\u5217\u662f\u4e2a\u4e0d\u9519\u7684\u65b9\u6848\uff0c\u53ea\u662f\u8981\u6ce8\u610f\u63d2\u5165\u65b0\u5143\u7d20\u524d\u8981\u68c0\u67e5\u4e00\u4e0b\u961f\u5217\u6709\u6ca1\u6709\u6ee1\uff0c\u5426\u5219\u7a7a\u961f\u5217\u548c\u6ee1\u961f\u5217\u90fd\u4f1a\u9020\u6210\u961f\u9996\u5143\u7d20\u548c\u961f\u672b\u5143\u7d20\u7684\u7d22\u5f15\u76f8\u540c<\/p>\n\n\n\n
template<class T>\r\nclass arrayQueue\r\n{\r\npublic:\r\n arrayQueue(int initialCapacity = 10);\r\n ~arrayQueue() { delete[] queue; }\r\n bool empty() const { return theFront == theBack; }\r\n int size() const\r\n {\r\n return (theBack - theFront + arrayLength) % arrayLength;\r\n }\r\n T& front()\r\n {\/\/ return front element\r\n if (theFront == theBack)\r\n throw queueEmpty();\r\n return queue[(theFront + 1) % arrayLength];\r\n }\r\n T& back()\r\n {\/\/ return theBack element\r\n if (theFront == theBack)\r\n throw queueEmpty();\r\n return queue[theBack];\r\n }\r\n void pop()\r\n {\/\/ remove theFront element\r\n if (theFront == theBack)\r\n throw queueEmpty();\r\n theFront = (theFront + 1) % arrayLength;\r\n queue[theFront].~T(); \/\/ destructor for T\r\n }\r\n void push(const T& theElement);\r\nprivate:\r\n int theFront; \/\/ 1 counterclockwise from theFront element\r\n int theBack; \/\/ position of theBack element\r\n int arrayLength; \/\/ queue capacity\r\n T* queue; \/\/ element array\r\n};<\/code><\/pre>\n\n\n\n\u4e0b\u9762\u662f\u6784\u9020\u51fd\u6570\u548c\u63d2\u5165\u5143\u7d20<\/p>\n\n\n\n
\u63d2\u5165\u5143\u7d20\u65f6\u8981\u68c0\u67e5\u961f\u5217\u662f\u5426\u6ee1\u4e86\uff0c\u6ee1\u4e86\u5c31\u53cc\u500d\u6570\u7ec4\u957f\u5ea6\u5e76\u628a\u6240\u6709\u5143\u7d20\u6309\u987a\u5e8f\u5e73\u79fb\u5230\u5f00\u5934<\/p>\n\n\n\n
template<class T>\r\narrayQueue<T>::arrayQueue(int initialCapacity)\r\n{\/\/ Constructor.\r\n if (initialCapacity < 1)\r\n {\r\n ostringstream s;\r\n s << \"Initial capacity = \" << initialCapacity << \" Must be > 0\";\r\n throw illegalParameterValue(s.str());\r\n }\r\n arrayLength = initialCapacity;\r\n queue = new T[arrayLength];\r\n theFront = 0;\r\n theBack = 0;\r\n}\r\n\r\ntemplate<class T>\r\nvoid arrayQueue<T>::push(const T& theElement)\r\n{\/\/ Add theElement to queue.\r\n\r\n \/\/ increase array length if necessary\r\n if ((theBack + 1) % arrayLength == theFront)\r\n {\/\/ double array length\r\n \/\/ allocate a new array\r\n T* newQueue = new T[2 * arrayLength];\r\n\r\n \/\/ copy elements into new array\r\n int start = (theFront + 1) % arrayLength;\r\n if (start < 2)\r\n \/\/ no wrap around\r\n copy(queue + start, queue + start + arrayLength - 1, newQueue);\r\n else\r\n { \/\/ queue wraps around\r\n copy(queue + start, queue + arrayLength, newQueue);\r\n copy(queue, queue + theBack + 1, newQueue + arrayLength - start);\r\n }\r\n\r\n \/\/ switch to newQueue and set theFront and theBack\r\n theFront = 2 * arrayLength - 1;\r\n theBack = arrayLength - 2; \/\/ queue size arrayLength - 1\r\n arrayLength *= 2;\r\n queue = newQueue;\r\n }\r\n\r\n \/\/ put theElement at the theBack of the queue\r\n theBack = (theBack + 1) % arrayLength;\r\n queue[theBack] = theElement;\r\n}\r\n<\/code><\/pre>\n\n\n\n\u7528\u94fe\u8868\u63cf\u8ff0\u4e5f\u5f88\u7b80\u5355<\/p>\n\n\n\n
template<class T>\r\nclass linkedQueue : public queue<T>\r\n{\r\n public:\r\n linkedQueue(int initialCapacity = 10)\r\n {queueFront = NULL; queueSize = 0;}\r\n ~linkedQueue();\r\n bool empty() const \r\n {return queueSize == 0;}\r\n int size() const\r\n {return queueSize;}\r\n T& front()\r\n {\r\n if (queueSize == 0)\r\n throw queueEmpty();\r\n return queueFront->element;\r\n }\r\n T& back()\r\n {\r\n if (queueSize == 0)\r\n throw queueEmpty();\r\n return queueBack->element;\r\n }\r\n void pop();\r\n void push(const T&);\r\n private:\r\n chainNode<T>* queueFront; \/\/ pointer to queue front\r\n chainNode<T>* queueBack; \/\/ pointer to queue back\r\n int queueSize; \/\/ number of elements in queue\r\n};\r\n\r\ntemplate<class T>\r\nlinkedQueue<T>::~linkedQueue()\r\n{\/\/ Destructor.\r\n while (queueFront != NULL)\r\n {\/\/ delete front node\r\n chainNode<T>* nextNode = queueFront->next;\r\n delete queueFront;\r\n queueFront = nextNode;\r\n }\r\n}\r\n\r\ntemplate<class T>\r\nvoid linkedQueue<T>::pop()\r\n{\/\/ Delete front element.\r\n if (queueFront == NULL)\r\n throw queueEmpty();\r\n\r\n chainNode<T>* nextNode = queueFront->next;\r\n delete queueFront;\r\n queueFront = nextNode;\r\n queueSize--;\r\n}\r\n\r\n\r\ntemplate<class T>\r\nvoid linkedQueue<T>::push(const T& theElement)\r\n{\/\/ Add theElement to back of queue.\r\n\r\n \/\/ create node for new element\r\n chainNode<T>* newNode = new chainNode<T>(theElement, NULL);\r\n\r\n \/\/ add new node to back of queue\r\n if (queueSize == 0)\r\n queueFront = newNode; \/\/ queue empty\r\n else \r\n queueBack->next = newNode; \/\/ queue not empty\r\n queueBack = newNode;\r\n\r\n queueSize++;\r\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u961f\u5217\u7684\u7b80\u5355\u5b9e\u73b0<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[5],"tags":[],"class_list":["post-182","post","type-post","status-publish","format-standard","hentry","category-5"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/182","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/comments?post=182"}],"version-history":[{"count":1,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/182\/revisions"}],"predecessor-version":[{"id":183,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/182\/revisions\/183"}],"wp:attachment":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/media?parent=182"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/categories?post=182"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/tags?post=182"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}