{"id":5334,"date":"2019-07-22T22:10:16","date_gmt":"2019-07-23T05:10:16","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5334"},"modified":"2019-07-22T22:10:53","modified_gmt":"2019-07-23T05:10:53","slug":"leetcode-232-implement-queue-using-stacks","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-232-implement-queue-using-stacks\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 232. Implement Queue using Stacks"},"content":{"rendered":"\n<p>Implement the following operations of a queue using stacks.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>push(x) &#8212; Push element x to the back of queue.<\/li><li>pop() &#8212; Removes the element from in front of queue.<\/li><li>peek() &#8212; Get the front element.<\/li><li>empty() &#8212; Return whether the queue is empty.<\/li><\/ul>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">MyQueue queue = new MyQueue();\n\nqueue.push(1);\nqueue.push(2);  \nqueue.peek();  \/\/ returns 1\nqueue.pop();   \/\/ returns 1\nqueue.empty(); \/\/ returns false<\/pre>\n\n\n\n<p><strong>Notes:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>You must use&nbsp;<em>only<\/em>&nbsp;standard operations of a stack &#8212; which means only&nbsp;<code>push to top<\/code>,&nbsp;<code>peek\/pop from top<\/code>,&nbsp;<code>size<\/code>, and&nbsp;<code>is empty<\/code>&nbsp;operations are valid.<\/li><li>Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.<\/li><li>You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Use two stacks<\/strong><\/h2>\n\n\n\n<p>amortized cost: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass MyQueue {\npublic:\n  \/** Initialize your data structure here. *\/\n  MyQueue() {}\n\n  \/** Push element x to the back of queue. *\/\n  void push(int x) {\n    s1_.push(x);\n  }\n\n  \/** Removes the element from in front of queue and returns that element. *\/\n  int pop() {\n    if (s2_.empty()) move();\n    int top = s2_.top();\n    s2_.pop();\n    return top;\n  }\n\n  \/** Get the front element. *\/\n  int peek() {\n    if (s2_.empty()) move();\n    return s2_.top();\n  }\n\n  \/** Returns whether the queue is empty. *\/\n  bool empty() {\n    return s1_.empty() && s2_.empty();\n  }\nprivate:\n  stack<int> s1_;\n  stack<int> s2_;\n  \n  void move() {\n    while (!s1_.empty()) {\n      s2_.push(s1_.top());\n      s1_.pop();\n    }\n  }    \n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Implement the following operations of a queue using stacks. push(x) &#8212; Push element x to the back of queue. pop() &#8212; Removes the element from&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[407],"tags":[177,179,180],"class_list":["post-5334","post","type-post","status-publish","format-standard","hentry","category-stack","tag-medium","tag-simulation","tag-stack","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5334","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=5334"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5334\/revisions"}],"predecessor-version":[{"id":5336,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5334\/revisions\/5336"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5334"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5334"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5334"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}