{"id":924,"date":"2023-01-13T09:45:28","date_gmt":"2023-01-13T01:45:28","guid":{"rendered":"https:\/\/swordofmorning.com\/?p=924"},"modified":"2025-10-09T13:55:19","modified_gmt":"2025-10-09T05:55:19","slug":"implement-queue-and-sort-via-stack","status":"publish","type":"post","link":"https:\/\/swordofmorning.com\/index.php\/2023\/01\/13\/implement-queue-and-sort-via-stack\/","title":{"rendered":"Implement Queue and Sort via Stack"},"content":{"rendered":"

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

  In this article we'll discuss how to implement queue and sort by stack. All these methods need to use two stacks.<\/p>\n

\u00a71 Queue<\/h2>\n

  Here we have a stack st1<\/code>, and we'll use a temporary stack st2<\/code> to reverse st1<\/code>. So, we can give method one:<\/p>\n

    \n
  1. in queue: directly in st1<\/code>.<\/li>\n
  2. out queue: reverse st1<\/code> to st2<\/code>, next pop the top, then reverse st2<\/code> to st1<\/code>.<\/li>\n<\/ol>\n

      This is the common method to achieve, to reduce the operation steps, we can have method two:<\/p>\n

      \n
    1. in queue: directly in st1<\/code>.<\/li>\n
    2. out queue: if<\/strong> st2<\/code> not empty, pop from st2<\/code>; else if<\/strong> st2<\/code> empty, reverse st1<\/code> to st2<\/code>, then pop from st2<\/code>.<\/li>\n<\/ol>\n

      Here is C++ example code:<\/p>\n

      \/\/ use stack to implement queue.\ntemplate<typename elemType>\nclass stque {\nprivate:\n    std::stack<elemType> m_st1;\n    std::stack<elemType> m_st2;\n\npublic:\n    stque() { \/* do nothing *\/ }\n\n    void reverse()\n    {\n        while (!m_st1.empty())\n        {\n            m_st2.push(m_st1.top());\n            m_st1.pop();\n        }\n    }\n\n    void push(elemType ele)\n    {\n        m_st1.push(ele);\n    }\n\n    elemType pop()\n    {\n        \/\/ if st2 empty, reverse st1 to st2 first, then pop.\n        if (m_st2.empty())\n        {\n            this->reverse();\n        }\n\n        \/\/ if st2 not empty, directly pop.\n        elemType retval = m_st2.top();\n        m_st2.pop();\n        return retval;\n    }\n};<\/code><\/pre>\n
      \u00a72 Sort<\/h2>\n
        Sort have the same idea with queue, here is my method. we have st1<\/code> which is to be sorted and sorted stack st2<\/code> i.e. the output. We use lt <<\/code> as order principle.<\/p>\n
      <\/p>\n
      \n
      that is, each time an element a is popped from the stack s, and the size of the top element b on the stack between it and s2 is judged, if a is less than or equal to b, then it is pushed to s2, otherwise, s2 is popped and merged Stack to s until the top element of s2 happens to be smaller than a, put a on the stack s2, repeat the above steps until s is empty.<\/p>\n<\/blockquote>\n
      Here is an example code:<\/p>\n
      \/\/ use stack to implement sort.\ntemplate<typename elemType>\nclass stsort {\npublic:\n    \/\/ sort principle: <, for st2: small nums on top, big nums in bottom\n    std::stack<elemType> sort(std::stack<elemType> st1)\n    {\n        std::stack<elemType> st2;\n\n        st2.push(st1.top());\n        st1.pop();\n\n        while (!st1.empty())\n        {\n            elemType st1Top = st1.top();\n            st1.pop();\n\n        loop:\n            elemType st2Top = st2.top();\n            st2.pop();\n            if (st1Top < st2Top)\n            {\n                st2.push(st2Top);\n                st2.push(st1Top);\n            }\n            else\n            {\n                st1.push(st2Top);\n                if (st2.empty())\n                {\n                    st2.push(st1Top);\n                    continue;\n                }\n                goto loop;\n            }\n        }\n        return st2;\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
        In this article we’ll discuss how to implement queue  ̷","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[14],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/924"}],"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=924"}],"version-history":[{"count":1,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/924\/revisions"}],"predecessor-version":[{"id":925,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/924\/revisions\/925"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=924"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=924"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=924"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}