{"id":611,"date":"2021-09-02T14:35:57","date_gmt":"2021-09-02T06:35:57","guid":{"rendered":"https:\/\/swordofmorning.com\/?p=611"},"modified":"2025-10-09T13:55:52","modified_gmt":"2025-10-09T05:55:52","slug":"pgexam-data-structure-02","status":"publish","type":"post","link":"https:\/\/swordofmorning.com\/index.php\/2021\/09\/02\/pgexam-data-structure-02\/","title":{"rendered":"\u8003\u7814\u6570\u636e\u7ed3\u6784 02 \u6808\u548c\u961f\u5217"},"content":{"rendered":"
\n
<\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/defs>\u7ebf<\/text><\/g>\u6027<\/text><\/g>\u8868<\/text><\/g><\/use><\/use><\/use><\/use><\/svg><\/use><\/svg><\/g>\u64cd<\/text><\/g>\u4f5c<\/text><\/g>\u53d7<\/text><\/g>\u9650<\/text><\/g><\/use><\/use><\/use><\/use><\/svg><\/use><\/svg><\/g>\u6808<\/text><\/g><\/use><\/use><\/use><\/use><\/svg><\/use><\/svg><\/g>\u987a<\/text><\/g>\u5e8f<\/text><\/g>\u6808<\/text><\/g><\/g><\/g><\/g>\u94fe<\/text><\/g>\u6808<\/text><\/g><\/g><\/g><\/g>\u5171<\/text><\/g>\u4eab<\/text><\/g>\u6808<\/text><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g>\u961f<\/text><\/g>\u5217<\/text><\/g><\/use><\/use><\/use><\/use><\/svg><\/use><\/svg><\/g>\u5faa<\/text><\/g>\u73af<\/text><\/g>\u961f<\/text><\/g>\u5217<\/text><\/g><\/g><\/g><\/g>\u94fe<\/text><\/g>\u5f0f<\/text><\/g>\u961f<\/text><\/g>\u5217<\/text><\/g><\/g><\/g><\/g>\u53cc<\/text><\/g>\u77ed<\/text><\/g>\u961f<\/text><\/g>\u5217<\/text><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g>\u63a8<\/text><\/g>\u5e7f<\/text><\/g><\/use><\/g>\u6570<\/text><\/g>\u7ec4<\/text><\/g><\/use><\/g>\u4e00<\/text><\/g>\u7ef4<\/text><\/g>\u6570<\/text><\/g>\u7ec4<\/text><\/g><\/g><\/g><\/g>\u591a<\/text><\/g>\u7ef4<\/text><\/g>\u6570<\/text><\/g>\u7ec4<\/text><\/g>\uff1a<\/text><\/g>\u538b<\/text><\/g>\u7f29<\/text><\/g>\u5b58<\/text><\/g>\u50a8<\/text><\/g>\u3001<\/text><\/g>\u7a00<\/text><\/g>\u758f<\/text><\/g>\u961f<\/text><\/g>\u5217<\/text><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/g><\/svg><\/use><\/use><\/use><\/g><\/g><\/g><\/svg><\/g><\/g><\/g><\/g><\/svg><\/mjx-container><\/div>\n<\/div>\n

<\/div><\/p>\n

\u4e00\u3001\u6808<\/h2>\n

1.1 \u57fa\u672c\u64cd\u4f5c<\/h3>\n
    \n
  1. bool empty()\uff1a\u8fd4\u56de\u6808\u662f\u5426\u4e3a\u7a7a\u3002<\/li>\n
  2. bool push(): \u5165\u6808\u3002<\/li>\n
  3. bool pop(): \u51fa\u6808\u3002<\/li>\n
  4. eleType top(): \u53d6\u5f97\u6808\u9876\u3002<\/li>\n
  5. void clear(): \u6e05\u7a7a\u3002<\/li>\n<\/ol>\n

    1.2 \u987a\u5e8f\u6808\u7684\u5b58\u50a8\u7ed3\u6784<\/h3>\n
    #define maxSize 50\ntypedef struct\n{\n    elemType data[maxSize];\n    int topIdx;     \/\/ \u5b58\u653e\u6808\u9876\u6307\u9488\n}Stack;\n<\/code><\/pre>\n
    1.2.1 init<\/h4>\n
    void init(stack& st)\n{\n    topIdx = -1;\n}\n<\/code><\/pre>\n
    1.2.2 empty<\/h4>\n
    bool empty(stack& st)\n{\n    return st.topIdx == -1 ?\n        true :\n        false;\n}\n<\/code><\/pre>\n
    1.2.3 push<\/h4>\n
    bool push(stack& st, eleType ele)\n{\n    if (st.topIdx < maxSize)\n    {\n        st.data[++st.topIdx] = ele;\n        return true;\n    }\n    return false;\n}\n<\/code><\/pre>\n
    1.2.4 pop<\/h4>\n
    bool push(stack& st)\n{\n    if (st.topIdx >= 0)\n    {\n        st.topIdx--;\n        return true;\n    }\n    return false;\n}\n<\/code><\/pre>\n
    1.2.5 top<\/h4>\n
    eleType top(stack& st)\n{\n    \/\/ \u8fd9\u91cc\u5ffd\u7565\u4e86\u5408\u6cd5\u6027\u68c0\u6d4b\n    return st.data[st.topIdx];\n}\n<\/code><\/pre>\n
    1.3 \u6808\u7684\u94fe\u5f0f\u5b58\u50a8\u7ed3\u6784<\/h3>\n
    typedef struct stackNode\n{\n    eleType data;\n    struct stackNode *next;   \n} *stackList;\n<\/code><\/pre>\n
      \u6240\u6709\u64cd\u4f5c\u5728\u5934\u7ed3\u70b9\u6267\u884c\u3002<\/p>\n
    \u4e8c\u3001\u961f\u5217<\/h2>\n
    2.1 \u57fa\u672c\u64cd\u4f5c<\/h3>\n
      \n
    1. bool empty(): \u67e5\u770b\u662f\u5426\u4e3a\u7a7a\u3002<\/li>\n
    2. bool push(): \u5165\u961f\uff08\u5c3e\u90e8\uff09\u3002<\/li>\n
    3. bool pop(): \u51fa\u961f\uff08\u5934\u90e8\uff09\u3002<\/li>\n
    4. eleType head(): \u53d6\u5f97\u961f\u5934\u3002<\/li>\n<\/ol>\n
      2.2 \u961f\u5217\u7684\u987a\u5e8f\u5b58\u50a8\u7ed3\u6784<\/h3>\n
      2.2.1 \u987a\u5e8f\u961f\u5217<\/h4>\n
      #define maxSize 50\n\ntypedef struct\n{\n    eleType data[maxSize];\n    int front, back;\n}\n<\/code><\/pre>\n
      2.2.2 \u5faa\u73af\u961f\u5217<\/h4>\n
      2.2.2.1 \u57fa\u672c\u6982\u5ff5<\/h5>\n
        \u6559\u6750\uff08\u738b\u9053\uff09\u63d0\u51fa\u4e86\u524d\u9762\u987a\u5e8f\u961f\u5217\u5b58\u5728\u201c\u5047\u6ea2\u51fa\u201d\u7684\u95ee\u9898\uff0c\u4f46\u5b9e\u9645\u4e0a\uff0c\u90a3\u662f\u7531\u4e8epush\/pop\u800c\u6ca1\u6709\u8fdb\u884c\u62f7\u8d1d\u5bfc\u81f4\u7684\u3002<\/p>\n
        \n
      • \u521d\u59cb\u72b6\u6001\uff1afront = back = 0;<\/li>\n
      • push: (back + 1) % maxSize;<\/li>\n
      • pop: (front - 1) % maxSize;<\/li>\n
      • length: (back + maxSize - front) % maxSize;<\/li>\n<\/ul>\n
          \u5982\u4f55\u533a\u5206\u7a7a\u961f\u5217\u548c\u6ee1\u961f\u5217\uff1f<\/p>\n
        (1) \u727a\u7272\u4e00\u4e2a\u5355\u5143<\/strong><\/p>\n
          \n
        • \u961f\u6ee1\uff1a(back + 1) % maxSize == front;<\/li>\n
        • \u5bf9\u7a7a\uff1afront = back;<\/li>\n
        • length: (back + maxSize - front) % maxSize<\/li>\n<\/ul>\n
          (2)\u589e\u52a0\u4e00\u4e2aqueue.size\u5143\u7d20<\/strong><\/p>\n
          2.2.2.2 init<\/h5>\n
          void init(stack& qst)\n{\n    qst.front = qst.back = 0;\n}\n<\/code><\/pre>\n
          2.2.2.3 empty<\/h5>\n
          bool empty(stack& qst)\n{\n    return qst.back == qst.front ?\n        true :\n        false;\n}\n<\/code><\/pre>\n
          2.2.2.4 push<\/h5>\n
          bool push(stack& qst, eleType ele)\n{\n    if ((back + 1) % maxSize == front)\n    {\n        return false;\n    }\n    qst.data[q.back] = x;\n    q.back = (q.back + 1) % maxSize;\n    return true;\n}\n<\/code><\/pre>\n
          2.2.2.5 pop<\/h5>\n
          bool pop(stack& qst)\n{\n    if (qst.empty())\n    {\n        return false;\n    }\n    qst.front = (q.front + 1) % maxSize;\n    return true;\n}\n<\/code><\/pre>\n
          2.3 \u94fe\u5f0f\u961f\u5217<\/h3>\n
            \u6559\u6750\u4e0a\u8bf4\u5f97\u7f57\u91cc\u5427\u55e6\uff0c\u8fd9\u91cc\u6211\u4eec\u76f4\u63a5\u505a\u4e00\u4e2a\u53cc\u5934\u7684\u94fe\u5f0f\u961f\u5217\u3002<\/p>\n
          template<typename eleType>\nclass deque\n{\nprivate:\n    struct node\n    {\n        eleType data;\n        node* next, prior;\n\n        node()\n        {\n            next = prior = nullptr;\n        }\n    }\n\n    \/\/ \u6210\u5458\n    node* m_front, m_back;\n    int m_size;\npublic:\n    deque()\n    {\n        front = back = nullptr;\n        size = 0;\n    }\n\n    \/\/ \u5224\u65ad\u4e3a\u7a7a\n    bool empty() const\n    {\n        return size == 0 ?\n            true :\n            false;\n    }\n\n    \/\/ \u961f\u5c3e\u5165\u961f\n    void push(const eleType& ele)\n    {\n        if (this->empty())\n        {\n            eleType* ins = new eleType;\n            ins.data = ele;\n\n            m_front = ele;\n            m_back = ele;\n        }\n        else if (!this->empty())\n        {\n            eleType* ins = new eleType;\n            ins.data = ele;\n\n            m_back->next = ins;\n            ins->prior = m_back;\n\n            m_back = ins;\n        }\n\n        m_size++;\n    }\n\n    \/\/ \u961f\u9996\u51fa\u961f\n    void pop()\n    {\n        if (!this->empty())\n        {\n            auto deletePtr = m_front;\n            m_front = m_front->next;\n\n            delete deletePtr;\n        }\n        m_size--;\n    }\n\n    \/\/ \u83b7\u53d6\u9996\u5143\u7d20\n    eleType head()\n    {\n        \/\/ \u8fd9\u91cc\u6700\u597d\u4f7f\u7528try catch\n\n        eleType re;\n\n        if (!this->empty())\n        {\n            re = m_front.data;\n        }\n\n        return re;\n    }\n\n    \/\/ \u6570\u91cf\n    int size()\n    {\n        return m_size;\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
          \u7ebf\u6027\u8868\u64cd\u4f5c\u53d7\u9650\u6808\u987a\u5e8f\u6808\u94fe\u6808\u5171\u4eab\u6808\u961f\u5217\u5faa\u73af\u961f\u5217\u94fe\u5f0f\u961f\u5217\u53cc\u77ed\u961f\u5217\u63a8\u5e7f\u6570\u7ec4\u4e00\u7ef4\u6570\u7ec4\u591a\u7ef4\u6570\u7ec4\uff1a\u538b\u7f29\u5b58\u50a8\u3001\u7a00\u758f\u961f\u5217 \u4e00\u3001\u6808 1.1 \u57fa\u672c\u64cd\u4f5c …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/611"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=611"}],"version-history":[{"count":2,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/611\/revisions"}],"predecessor-version":[{"id":615,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/611\/revisions\/615"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}