{"id":2084,"date":"2018-03-13T02:59:56","date_gmt":"2018-03-13T09:59:56","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2084"},"modified":"2018-03-13T03:14:37","modified_gmt":"2018-03-13T10:14:37","slug":"leetcode-225-implement-stack-using-queues","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-225-implement-stack-using-queues\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 225. Implement Stack using Queues"},"content":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7528\u961f\u5217\u6765\u5b9e\u73b0\u6808\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/implement-stack-using-queues\/description\/\">https:\/\/leetcode.com\/problems\/implement-stack-using-queues\/description\/<\/a><\/p>\n<p>Implement the following operations of a stack using queues.<\/p>\n<ul>\n<li>push(x) &#8212; Push element x onto stack.<\/li>\n<li>pop() &#8212; Removes the element on top of the stack.<\/li>\n<li>top() &#8212; Get the top element.<\/li>\n<li>empty() &#8212; Return whether the stack is empty.<\/li>\n<\/ul>\n<p><b>Notes:<\/b><\/p>\n<ul>\n<li>You must use\u00a0<i>only<\/i>\u00a0standard operations of a queue &#8212; which means only\u00a0<code>push to back<\/code>,\u00a0<code>peek\/pop from front<\/code>,\u00a0<code>size<\/code>, and\u00a0<code>is empty<\/code>\u00a0operations are valid.<\/li>\n<li>Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.<\/li>\n<li>You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).<\/li>\n<\/ul>\n<p><strong>Idea:<\/strong><\/p>\n<p>Using a single queue, for every push, shift the queue (n &#8211; 1) times such that the last element becomes the first element in the queue.<\/p>\n<p>e.g.<\/p>\n<p>push(1): q: [1]<\/p>\n<p>push(2): q: [1, 2] -&gt; [2, 1]<\/p>\n<p>push(3): q: [2, 1, 3] -&gt; [1, 3, 2] -&gt; [3, 2, 1]<\/p>\n<p>push(4): q: [3, 2, 1, 4] -&gt; [2, 1, 4, 3] -&gt; [1, 4, 3, 2] -&gt; [4, 3, 2, 1]<\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>Time complexity:<\/p>\n<p>Push: O(n)<\/p>\n<p>Pop\/top\/empty: O(1)<\/p>\n<p>Space complexity: O(n)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 3 ms\r\nclass MyStack {\r\npublic:\r\n  \/** Initialize your data structure here. *\/\r\n  MyStack() {}\r\n\r\n  \/** Push element x onto stack. *\/\r\n  void push(int x) {\r\n    q_.push(x);\r\n    for (int i = 1; i &lt; q_.size(); ++i) {\r\n      q_.push(q_.front());\r\n      q_.pop();\r\n    }\r\n  }\r\n\r\n  \/** Removes the element on top of the stack and returns that element. *\/\r\n  int pop() {\r\n    int top = q_.front();\r\n    q_.pop();\r\n    return top;\r\n  }\r\n\r\n  \/** Get the top element. *\/\r\n  int top() {\r\n    return q_.front();\r\n  }\r\n\r\n  \/** Returns whether the stack is empty. *\/\r\n  bool empty() {\r\n    return q_.empty();\r\n  }\r\nprivate:\r\n  queue&lt;int&gt; q_;  \r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7528\u961f\u5217\u6765\u5b9e\u73b0\u6808\u3002 Problem: https:\/\/leetcode.com\/problems\/implement-stack-using-queues\/description\/ Implement the following operations of a stack using queues. push(x) &#8212; Push element x onto stack. pop() &#8212; Removes the element on&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89],"tags":[251,222,213,180],"class_list":["post-2084","post","type-post","status-publish","format-standard","hentry","category-data-structure","tag-design","tag-easy","tag-queue","tag-stack","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2084","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2084"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2084\/revisions"}],"predecessor-version":[{"id":2088,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2084\/revisions\/2088"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2084"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2084"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2084"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}