{"id":3582,"date":"2021-08-05T08:49:02","date_gmt":"2021-08-05T08:49:02","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3582"},"modified":"2022-12-13T11:24:24","modified_gmt":"2022-12-13T11:24:24","slug":"reverse-a-stack-without-using-extra-space-in-on","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/","title":{"rendered":"Reverse a stack without using extra space in O(n)"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png\" alt=\"\" \/><\/p>\n<h3>Problem Statement<\/h3>\n<p>In this problem, we are given a stack. We have to reverse the stack without using extra space in O(n). <\/p>\n<\/p>\n<h3>Problem Statement Understanding<\/h3>\n<p>As we know, reversing a stack using recursion is the normally used technique. But here, we cannot use recursion because we have to reverse it in O(1) space. So, how can we complete the task with the given constraint?<\/p>\n<p>Linked List. Yes, we can use the technique of reversing a linked list in this problem. Let us have a glance at our approach to get a clearer look.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/3_1-01.png\" alt=\"\" \/><\/p>\n<p><strong>Explanation:<\/strong> The given stack is reversed.<\/p>\n<h3>Approach<\/h3>\n<p>The approach is going to be pretty simple. We have to represent the stack as a linked list. By doing this, we can use the linked list reversal technique, which takes O(n) time and O(1) space. Even though the reversal will take O(n) time, push and pop operations will still take O(1) time.<\/p>\n<h3>Algorithm<\/h3>\n<ul>\n<li>Create a StackNode class to represent the given stack as a linked list.<\/li>\n<li>For the push method, if the top is NULL, then create a new StackNode with the given data and put it at the top. <\/li>\n<li>Else, Create a new StackNode, say s. Now, the next of s will point to the top, and s will become the new top.<\/li>\n<li>For the pop method, create a new StackNode, say s, and it will point to the top. Now, to delete the element, the top will point to the next of the top. In the end, we will return s.<\/li>\n<li>In the reverse method, simply perform the linked list reversal logic on the given stack.<\/li>\n<\/ul>\n<h3>Dry Run<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/AI_3_2-01.png\" alt=\"\" \/><\/p>\n<h4>Code Implementation<\/h4>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_3581 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_3581 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_3581 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_3581 .wpsm_nav-tabs > li.active > a, #tab_container_3581 .wpsm_nav-tabs > li.active > a:hover, #tab_container_3581 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_3581 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_3581 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_3581 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_3581 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_3581 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_3581 .wpsm_nav-tabs > li > a:hover , #tab_container_3581 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_3581 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_3581 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_3581 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_3581 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_3581 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_3581 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_3581 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_3581 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_3581 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_3581 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_3581 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_3581\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_3581\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_3581_1\" aria-controls=\"tabs_desc_3581_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_3581_2\" aria-controls=\"tabs_desc_3581_2\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_3581_3\" aria-controls=\"tabs_desc_3581_3\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Python<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_3581\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_3581_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include<bits\/stdc++.h>\r\nusing namespace std;\r\n \r\nclass StackNode {\r\n    public:\r\n    int data;\r\n    StackNode *next;\r\n     \r\n    StackNode(int data)\r\n    {\r\n        this->data = data;\r\n        this->next = NULL;\r\n    }\r\n};\r\n \r\nclass Stack {\r\n     \r\n    StackNode *top;\r\n     \r\n    public:\r\n     \r\n    \/\/ Push function\r\n    void push(int data)\r\n    {\r\n        if (top == NULL) {\r\n            top = new StackNode(data);\r\n            return;\r\n        }\r\n        StackNode *s = new StackNode(data);\r\n        s->next = top;\r\n        top = s;\r\n    }\r\n    \/\/  Pop function\r\n    StackNode* pop()\r\n    {\r\n        StackNode *s = top;\r\n        top = top->next;\r\n        return s;\r\n    }\r\n \r\n    \/\/ Function to display the element of the stack\r\n    void display()\r\n    {\r\n        StackNode *s = top;\r\n        while (s != NULL) {\r\n            cout << s->data << \" \";\r\n            s = s->next;\r\n        }\r\n        cout << endl;\r\n    }\r\n \r\n    \/\/ Stack reversal using the linked list reversal logic\r\n    void reverse()\r\n    {\r\n        StackNode *prev, *cur, *succ;\r\n        cur = prev = top;\r\n        cur = cur->next;\r\n        prev->next = NULL;\r\n        while (cur != NULL) {\r\n \r\n            succ = cur->next;\r\n            cur->next = prev;\r\n            prev = cur;\r\n            cur = succ;\r\n        }\r\n        top = prev;\r\n    }\r\n};\r\n\r\nint main()\r\n{\r\n    Stack *s = new Stack();\r\n    s->push(1);\r\n    s->push(3);\r\n    s->push(5);\r\n    s->push(7);\r\n    cout << \"Original Stack\" << endl;;\r\n    s->display();\r\n    cout << endl;\r\n    s->reverse();\r\n    cout << \"Reversed Stack\" << endl;\r\n    s->display();\r\n     \r\n    return 0;\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_3581_2\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"java\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nclass StackNode {\r\n    int data;\r\n    StackNode next;\r\n    public StackNode(int data)\r\n    {\r\n        this.data = data;\r\n        this.next = null;\r\n    }\r\n}\r\n \r\nclass Stack {\r\n    StackNode top;\r\n\r\n    public void push(int data)\r\n    {\r\n        if (this.top == null) {\r\n            top = new StackNode(data);\r\n            return;\r\n        }\r\n        StackNode s = new StackNode(data);\r\n        s.next = this.top;\r\n        this.top = s;\r\n    }\r\n    public StackNode pop()\r\n    {\r\n        StackNode s = this.top;\r\n        this.top = this.top.next;\r\n        return s;\r\n    }\r\n\r\n    public void display()\r\n    {\r\n        StackNode s = this.top;\r\n        while (s != null) {\r\n            System.out.print(s.data + \" \");\r\n            s = s.next;\r\n        }\r\n        System.out.println();\r\n    }\r\n\r\n    public void reverse()\r\n    {\r\n        StackNode prev, cur, succ;\r\n        cur = prev = this.top;\r\n        cur = cur.next;\r\n        prev.next = null;\r\n        while (cur != null) {\r\n \r\n            succ = cur.next;\r\n            cur.next = prev;\r\n            prev = cur;\r\n            cur = succ;\r\n        }\r\n        this.top = prev;\r\n    }\r\n}\r\n \r\npublic class reverseStackWithoutSpace {\r\n    public static void main(String[] args)\r\n    {\r\n        Stack s = new Stack();\r\n        s.push(1);\r\n        s.push(3);\r\n        s.push(5);\r\n        s.push(7);\r\n        System.out.println(\"Original Stack\");\r\n        s.display();\r\n        s.reverse();\r\n        System.out.println(\"Reversed Stack\");\r\n        s.display();\r\n    }\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_3581_3\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"Python\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"Python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nclass stackNode:\r\n\tdef __init__(self, data):\r\n\t\tself.data = data\r\n\t\tself.next = None\r\n\r\nclass stack:\r\n\tdef __init__(self):\r\n\t\tself.top = None\r\n\r\n\tdef push(self, data):\r\n\t\tif self.top == None:\r\n\t\t\tself.top = stackNode(data)\r\n\t\t\treturn\r\n\t\ts = stackNode(data)\r\n\t\ts.next = self.top\r\n\t\tself.top = s\r\n\r\n\tdef pop(self):\r\n\t\ts = self.top\r\n\t\tself.top =self.top.next\r\n\t\treturn s\r\n\r\n\tdef display(self):\r\n\t\ts = self.top\r\n\t\twhile s:\r\n\t\t\tprint(s.data, end = \" \")\r\n\t\t\ts = s.next\r\n\r\n\tdef reverse(self):\r\n\t\tcur = self.top\r\n\t\tprev = self.top\r\n\t\tcur = cur.next\r\n\t\tprev.next = None\r\n\t\twhile cur:\r\n\t\t\tsucc = cur.next\r\n\t\t\tcur.next = prev\r\n\t\t\tprev = cur\r\n\t\t\tcur = succ\r\n\t\tself.top = prev\r\n\r\n\r\ns = stack()\r\ns.push(1)\r\ns.push(3)\r\ns.push(5)\r\ns.push(7)\r\nprint(\"Original Stack\")\r\ns.display()\r\ns.reverse()\r\nprint(\"Reversed Stack\")\r\ns.display()\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_3581 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_3581 a\"),jQuery(\"#tab-content_3581\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Output<\/strong><br \/>\nOriginal Stack<br \/>\n7 5 3 1       <\/p>\n<p>Reversed Stack<br \/>\n1 3 5 7<\/p>\n<p>[forminator_quiz id=&#8221;3584&#8243;]<\/p>\n<p><strong>Space Complexity:<\/strong> O(1), as only temporary variables are being created.<\/p>\n<p>So, in this article, we have tried to explain the most efficient approach to reverse a stack without using extra space in O(n). As we are saving up on space in this approach, this problem becomes an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Linked List<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Statement In this problem, we are given a stack. We have to reverse the stack without using extra space in O(n). Problem Statement Understanding As we know, reversing a stack using recursion is the normally used technique. But here, we cannot use recursion because we have to reverse it in O(1) space. So, how [&hellip;]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[127],"tags":[],"class_list":["post-3582","post","type-post","status-publish","format-standard","hentry","category-stacks"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Reverse a stack without using extra space in O(n)<\/title>\n<meta name=\"description\" content=\"Learn the most efficient way to reverse a stack without using extra space in O(n). In this problem, we are given a stack. We have to reverse the stack without using extra space in O(n).\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Reverse a stack without using extra space in O(n)\" \/>\n<meta property=\"og:description\" content=\"Learn the most efficient way to reverse a stack without using extra space in O(n). In this problem, we are given a stack. We have to reverse the stack without using extra space in O(n).\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-08-05T08:49:02+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-12-13T11:24:24+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png\" \/>\n<meta name=\"author\" content=\"Prepbytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prepbytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Reverse a stack without using extra space in O(n)\",\"datePublished\":\"2021-08-05T08:49:02+00:00\",\"dateModified\":\"2022-12-13T11:24:24+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/\"},\"wordCount\":376,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png\",\"articleSection\":[\"Stacks\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/\",\"name\":\"Reverse a stack without using extra space in O(n)\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png\",\"datePublished\":\"2021-08-05T08:49:02+00:00\",\"dateModified\":\"2022-12-13T11:24:24+00:00\",\"description\":\"Learn the most efficient way to reverse a stack without using extra space in O(n). In this problem, we are given a stack. We have to reverse the stack without using extra space in O(n).\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Stacks\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/stacks\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Reverse a stack without using extra space in O(n)\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Reverse a stack without using extra space in O(n)","description":"Learn the most efficient way to reverse a stack without using extra space in O(n). In this problem, we are given a stack. We have to reverse the stack without using extra space in O(n).","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/","og_locale":"en_US","og_type":"article","og_title":"Reverse a stack without using extra space in O(n)","og_description":"Learn the most efficient way to reverse a stack without using extra space in O(n). In this problem, we are given a stack. We have to reverse the stack without using extra space in O(n).","og_url":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-08-05T08:49:02+00:00","article_modified_time":"2022-12-13T11:24:24+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Reverse a stack without using extra space in O(n)","datePublished":"2021-08-05T08:49:02+00:00","dateModified":"2022-12-13T11:24:24+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/"},"wordCount":376,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png","articleSection":["Stacks"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/","url":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/","name":"Reverse a stack without using extra space in O(n)","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png","datePublished":"2021-08-05T08:49:02+00:00","dateModified":"2022-12-13T11:24:24+00:00","description":"Learn the most efficient way to reverse a stack without using extra space in O(n). In this problem, we are given a stack. We have to reverse the stack without using extra space in O(n).","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926009711-107.Reverse%20a%20stack%20without%20using%20extra%20space%20in%20O%28n%29_Artboard%202.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/reverse-a-stack-without-using-extra-space-in-on\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Stacks","item":"https:\/\/prepbytes.com\/blog\/category\/stacks\/"},{"@type":"ListItem","position":3,"name":"Reverse a stack without using extra space in O(n)"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/3582","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=3582"}],"version-history":[{"count":6,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/3582\/revisions"}],"predecessor-version":[{"id":7837,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/3582\/revisions\/7837"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=3582"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=3582"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=3582"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}