{"id":27355,"date":"2018-01-30T20:26:18","date_gmt":"2018-01-30T14:56:18","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27355"},"modified":"2018-01-30T20:26:18","modified_gmt":"2018-01-30T14:56:18","slug":"design-implement-special-stack-data-structure","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/design-implement-special-stack-data-structure\/","title":{"rendered":"Design and Implement Special Stack Data Structure"},"content":{"rendered":"<p><strong>Question:<\/strong> Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() <span id=\"more-14149\"><\/span>which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, .. etc.<\/p>\n<p>Example:<\/p>\n<pre>Consider the following SpecialStack\r\n16  --> TOP\r\n15\r\n29\r\n19\r\n18\r\n\r\nWhen getMin() is called it should return 15, which is the minimum \r\nelement in the current stack. \r\n\r\nIf we do pop two times on stack, the stack becomes\r\n29  --> TOP\r\n19\r\n18\r\n\r\nWhen getMin() is called, it should return 18 which is the minimum \r\nin the current stack.\r\n<\/pre>\n<p><strong>Solution:<\/strong> Use two stacks: one to store actual stack elements and other as an auxiliary stack to store minimum values. The idea is to do push() and pop() operations in such a way that the top of auxiliary stack is always the minimum. Let us see how push() and pop() operations work.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Push(int x) \/\/ inserts an element x to Special Stack <\/strong><br \/>\n1) push x to the first stack (the stack with actual elements)<br \/>\n2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y.<br \/>\n\u2026..a) If x is smaller than y then push x to the auxiliary stack.<br \/>\n\u2026..b) If x is greater than y then push y to the auxiliary stack.<\/p>\n<p><strong>int Pop() \/\/ removes an element from Special Stack and return the removed element <\/strong><br \/>\n1) pop the top element from the auxiliary stack.<br \/>\n2) pop the top element from the actual stack and return it.<\/p>\n<p>The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.<\/p>\n<p><strong>int getMin() \/\/ returns the minimum element from Special Stack <\/strong><br \/>\n1) Return the top element of auxiliary stack.<\/p>\n<p>We can see that <strong>all above operations are O(1)<\/strong>.<br \/>\nLet us see an example. Let us assume that both stacks are initially empty and 18, 19, 29, 15 and 16 are inserted to the SpecialStack.<\/p>\n<pre>When we insert 18, both stacks change to following.\r\nActual Stack\r\n18 <--- top     \r\nAuxiliary Stack\r\n18 <---- top\r\n\r\nWhen 19 is inserted, both stacks change to following.\r\nActual Stack\r\n19 <--- top     \r\n18\r\nAuxiliary Stack\r\n18 <---- top\r\n18\r\n\r\nWhen 29 is inserted, both stacks change to following.\r\nActual Stack\r\n29 <--- top     \r\n19\r\n18\r\nAuxiliary Stack\r\n18 <---- top\r\n18\r\n18\r\n\r\nWhen 15 is inserted, both stacks change to following.\r\nActual Stack\r\n15 <--- top     \r\n29\r\n19 \r\n18\r\nAuxiliary Stack\r\n15 <---- top\r\n18\r\n18\r\n18\r\n\r\nWhen 16 is inserted, both stacks change to following.\r\nActual Stack\r\n16 <--- top     \r\n15\r\n29\r\n19 \r\n18\r\nAuxiliary Stack\r\n15 <---- top\r\n15\r\n18\r\n18\r\n18\r\n<\/pre>\n<p>Following is C++ implementation for SpecialStack class. In the below implementation, SpecialStack inherits from Stack and has one Stack object <em>min<\/em> which work as auxiliary stack.<\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%3Ciostream%3E%0A%23include%3Cstdlib.h%3E%0A%20%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20A%20simple%20stack%20class%20with%20basic%20stack%20funtionalities%20*%2F%0Aclass%20Stack%0A%7B%0Aprivate%3A%0A%20%20%20%20static%20const%20int%20max%20%3D%20100%3B%0A%20%20%20%20int%20arr%5Bmax%5D%3B%0A%20%20%20%20int%20top%3B%0Apublic%3A%0A%20%20%20%20Stack()%20%7B%20top%20%3D%20-1%3B%20%7D%0A%20%20%20%20bool%20isEmpty()%3B%0A%20%20%20%20bool%20isFull()%3B%0A%20%20%20%20int%20pop()%3B%0A%20%20%20%20void%20push(int%20x)%3B%0A%7D%3B%0A%20%0A%2F*%20Stack\u2019s%20member%20method%20to%20check%20if%20the%20stack%20is%20iempty%20*%2F%0Abool%20Stack%3A%3AisEmpty()%0A%7B%0A%20%20%20%20if(top%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F*%20Stack\u2019s%20member%20method%20to%20check%20if%20the%20stack%20is%20full%20*%2F%0Abool%20Stack%3A%3AisFull()%0A%7B%0A%20%20%20%20if(top%20%3D%3D%20max%20-%201)%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F*%20Stack\u2019s%20member%20method%20to%20remove%20an%20element%20from%20it%20*%2F%0Aint%20Stack%3A%3Apop()%0A%7B%0A%20%20%20%20if(isEmpty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20cout%3C%3C%22Stack%20Underflow%22%3B%0A%20%20%20%20%20%20%20%20abort()%3B%0A%20%20%20%20%7D%0A%20%20%20%20int%20x%20%3D%20arr%5Btop%5D%3B%0A%20%20%20%20top\u2013%3B%0A%20%20%20%20return%20x%3B%0A%7D%0A%20%0A%2F*%20Stack\u2019s%20member%20method%20to%20insert%20an%20element%20to%20it%20*%2F%0Avoid%20Stack%3A%3Apush(int%20x)%0A%7B%0A%20%20%20%20if(isFull())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20cout%3C%3C%22Stack%20Overflow%22%3B%0A%20%20%20%20%20%20%20%20abort()%3B%0A%20%20%20%20%7D%0A%20%20%20%20top%2B%2B%3B%0A%20%20%20%20arr%5Btop%5D%20%3D%20x%3B%0A%7D%0A%20%0A%2F*%20A%20class%20that%20supports%20all%20the%20stack%20operations%20and%20one%20additional%0A%20%20operation%20getMin()%20that%20returns%20the%20minimum%20element%20from%20stack%20at%0A%20%20any%20time.%20%20This%20class%20inherits%20from%20the%20stack%20class%20and%20uses%20an%0A%20%20auxiliarry%20stack%20that%20holds%20minimum%20elements%20*%2F%0Aclass%20SpecialStack%3A%20public%20Stack%0A%7B%0A%20%20%20%20Stack%20min%3B%0Apublic%3A%0A%20%20%20%20int%20pop()%3B%0A%20%20%20%20void%20push(int%20x)%3B%0A%20%20%20%20int%20getMin()%3B%0A%7D%3B%0A%20%0A%2F*%20SpecialStack\u2019s%20member%20method%20to%20insert%20an%20element%20to%20it.%20This%20method%0A%20%20%20makes%20sure%20that%20the%20min%20stack%20is%20also%20updated%20with%20appropriate%20minimum%0A%20%20%20values%20*%2F%0Avoid%20SpecialStack%3A%3Apush(int%20x)%0A%7B%0A%20%20%20%20if(isEmpty()%3D%3Dtrue)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Stack%3A%3Apush(x)%3B%0A%20%20%20%20%20%20%20%20min.push(x)%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Stack%3A%3Apush(x)%3B%0A%20%20%20%20%20%20%20%20int%20y%20%3D%20min.pop()%3B%0A%20%20%20%20%20%20%20%20min.push(y)%3B%0A%20%20%20%20%20%20%20%20if(%20x%20%3C%20y%20)%0A%20%20%20%20%20%20%20%20%20%20min.push(x)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20min.push(y)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20SpecialStack\u2019s%20member%20method%20to%20remove%20an%20element%20from%20it.%20This%20method%0A%20%20%20removes%20top%20element%20from%20min%20stack%20also.%20*%2F%0Aint%20SpecialStack%3A%3Apop()%0A%7B%0A%20%20%20%20int%20x%20%3D%20Stack%3A%3Apop()%3B%0A%20%20%20%20min.pop()%3B%0A%20%20%20%20return%20x%3B%0A%7D%0A%20%0A%2F*%20SpecialStack\u2019s%20member%20method%20to%20get%20minimum%20element%20from%20it.%20*%2F%0Aint%20SpecialStack%3A%3AgetMin()%0A%7B%0A%20%20%20%20int%20x%20%3D%20min.pop()%3B%0A%20%20%20%20min.push(x)%3B%0A%20%20%20%20return%20x%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20SpecialStack%20methods%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20SpecialStack%20s%3B%0A%20%20%20%20s.push(10)%3B%0A%20%20%20%20s.push(20)%3B%0A%20%20%20%20s.push(30)%3B%0A%20%20%20%20cout%3C%3Cs.getMin()%3C%3Cendl%3B%0A%20%20%20%20s.push(5)%3B%0A%20%20%20%20cout%3C%3Cs.getMin()%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><br \/>\n10<br \/>\n5<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Space Optimized Version<\/strong><br \/>\nThe above approach can be optimized. We can limit the number of elements in auxiliary stack. We can push only when the incoming element of main stack is smaller than or equal to top of auxiliary stack. Similarly during pop, if the pop off element equal to top of auxiliary stack, remove the top element of auxiliary stack. Following is modified implementation of push() and pop().<\/p>\n<p>\u00a0<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F*%20SpecialStack\u2019s%20member%20method%20to%20insert%20an%20element%20to%20it.%20This%20method%0A%20%20%20makes%20sure%20that%20the%20min%20stack%20is%20also%20updated%20with%20appropriate%20minimum%0A%20%20%20values%20*%2F%0Avoid%20SpecialStack%3A%3Apush(int%20x)%0A%7B%0A%20%20%20%20if(isEmpty()%3D%3Dtrue)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Stack%3A%3Apush(x)%3B%0A%20%20%20%20%20%20%20%20min.push(x)%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Stack%3A%3Apush(x)%3B%0A%20%20%20%20%20%20%20%20int%20y%20%3D%20min.pop()%3B%0A%20%20%20%20%20%20%20%20min.push(y)%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%2F*%20push%20only%20when%20the%20incoming%20element%20of%20main%20stack%20is%20smaller%20%0A%20%20%20%20%20%20%20%20than%20or%20equal%20to%20top%20of%20auxiliary%20stack%20*%2F%0A%20%20%20%20%20%20%20%20if(%20x%20%3C%3D%20y%20)%0A%20%20%20%20%20%20%20%20%20%20min.push(x)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20SpecialStack\u2019s%20member%20method%20to%20remove%20an%20element%20from%20it.%20This%20method%0A%20%20%20removes%20top%20element%20from%20min%20stack%20also.%20*%2F%0Aint%20SpecialStack%3A%3Apop()%0A%7B%0A%20%20%20%20int%20x%20%3D%20Stack%3A%3Apop()%3B%0A%20%20%20%20int%20y%20%3D%20min.pop()%3B%0A%20%0A%20%20%20%20%2F*%20Push%20the%20popped%20element%20y%20%20back%20only%20if%20it%20is%20not%20equal%20to%20x%20*%2F%0A%20%20%20%20if%20(%20y%20!%3D%20x%20)%0A%20%20%20%20%20%20min.push(y)%3B%0A%20%0A%20%20%20%20return%20x%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Design and Implement Special Stack Data Structure &#8211; Stack &#8211;  Design a Data Structure SpecialStack that supports all the stack operations <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73012,79607],"tags":[81446,81445,80793,81448,81449,81444,81447,81451,80704,80703,80702,80792,80779,80795,80796,81450],"class_list":["post-27355","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-stack","tag-find-max-element-in-stack","tag-get-minimum-element-from-stack-geeksforgeeks","tag-how-to-sort-a-stack-using-a-temporary-stack","tag-min-stack-developer","tag-min-stack-interview-question","tag-min-stack-java","tag-min-stack-leetcode","tag-min-stack-python","tag-recursion-explanation-using-stack","tag-recursion-using-stack-example","tag-reverse-a-stack-using-recursion","tag-sort-a-stack-in-ascending-order-java","tag-sort-a-stack-in-ascending-order-using-another-stack","tag-sort-a-stack-using-another-stack-java","tag-sort-stack-c","tag-write-a-function-that-sorts-a-stack"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27355","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27355"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27355\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27355"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27355"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27355"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}