{"id":27389,"date":"2018-02-02T20:56:39","date_gmt":"2018-02-02T15:26:39","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27389"},"modified":"2018-02-02T20:56:39","modified_gmt":"2018-02-02T15:26:39","slug":"design-stack-operations-middle-element","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/design-stack-operations-middle-element\/","title":{"rendered":"Design a stack with operations on middle element"},"content":{"rendered":"<p>How to implement a stack which will support following operations in<strong> O(1) time complexity<\/strong>?<br \/>\n1) push() which adds an element to the top of stack.<br \/>\n2) pop() which removes an element from top of stack.<span id=\"more-119140\"><\/span><br \/>\n3) findMiddle() which will return middle element of the stack.<br \/>\n4) deleteMiddle() which will delete the middle element.<br \/>\nPush and pop are standard stack operations.<\/p>\n<p>The important question is, whether to use a linked list or array for implementation of stack?<\/p>\n<p>Please note that, we need to find and delete middle element. Deleting an element from middle is not O(1) for array. Also, we may need to move the middle pointer up when we push an element and move down when we pop(). In singly linked list, moving middle pointer in both directions is not possible.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>The idea is to use Doubly Linked List (DLL). We can delete middle element in O(1) time by maintaining mid pointer. We can move mid pointer in both directions using previous and next pointers.<\/p>\n<p>Following is C implementation of push(), pop() and findMiddle() operations. Implementation of deleteMiddle() is left as an exercise. If there are even elements in stack, findMiddle() returns the first middle element. For example, if stack contains {1, 2, 3, 4}, then findMiddle() would return 2.<\/p>\n<p><b>C Programming:<\/b><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F*%20Program%20to%20implement%20a%20stack%20that%20supports%20findMiddle()%20and%20deleteMiddle%0A%20%20%20in%20O(1)%20time%20*%2F%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F*%20A%20Doubly%20Linked%20List%20Node%20*%2F%0Astruct%20DLLNode%0A%7B%0A%20%20%20%20struct%20DLLNode%20*prev%3B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20DLLNode%20*next%3B%0A%7D%3B%0A%20%0A%2F*%20Representation%20of%20the%20stack%20data%20structure%20that%20supports%20findMiddle()%0A%20%20%20in%20O(1)%20time.%20%20The%20Stack%20is%20implemented%20using%20Doubly%20Linked%20List.%20It%0A%20%20%20maintains%20pointer%20to%20head%20node%2C%20pointer%20to%20middle%20node%20and%20count%20of%0A%20%20%20nodes%20*%2F%0Astruct%20myStack%0A%7B%0A%20%20%20%20struct%20DLLNode%20*head%3B%0A%20%20%20%20struct%20DLLNode%20*mid%3B%0A%20%20%20%20int%20count%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20create%20the%20stack%20data%20structure%20*%2F%0Astruct%20myStack%20*createMyStack()%0A%7B%0A%20%20%20%20struct%20myStack%20*ms%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(struct%20myStack*)%20malloc(sizeof(struct%20myStack))%3B%0A%20%20%20%20ms-%3Ecount%20%3D%200%3B%0A%20%20%20%20return%20ms%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20push%20an%20element%20to%20the%20stack%20*%2F%0Avoid%20push(struct%20myStack%20*ms%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20DLLNode%20and%20put%20in%20data%20*%2F%0A%20%20%20%20struct%20DLLNode*%20new_DLLNode%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(struct%20DLLNode*)%20malloc(sizeof(struct%20DLLNode))%3B%0A%20%20%20%20new_DLLNode-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20Since%20we%20are%20adding%20at%20the%20begining%2C%0A%20%20%20%20%20%20prev%20is%20always%20NULL%20*%2F%0A%20%20%20%20new_DLLNode-%3Eprev%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20DLLNode%20*%2F%0A%20%20%20%20new_DLLNode-%3Enext%20%3D%20ms-%3Ehead%3B%0A%20%0A%20%20%20%20%2F*%20Increment%20count%20of%20items%20in%20stack%20*%2F%0A%20%20%20%20ms-%3Ecount%20%2B%3D%201%3B%0A%20%0A%20%20%20%20%2F*%20Change%20mid%20pointer%20in%20two%20cases%0A%20%20%20%20%20%20%201)%20Linked%20List%20is%20empty%0A%20%20%20%20%20%20%202)%20Number%20of%20nodes%20in%20linked%20list%20is%20odd%20*%2F%0A%20%20%20%20if%20(ms-%3Ecount%20%3D%3D%201)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20ms-%3Emid%20%3D%20new_DLLNode%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%20ms-%3Ehead-%3Eprev%20%3D%20new_DLLNode%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(ms-%3Ecount%20%26%201)%20%2F%2F%20Update%20mid%20if%20ms-%3Ecount%20is%20odd%0A%20%20%20%20%20%20%20%20%20%20%20ms-%3Emid%20%3D%20ms-%3Emid-%3Eprev%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20move%20head%20to%20point%20to%20the%20new%20DLLNode%20*%2F%0A%20%20%20%20ms-%3Ehead%20%20%3D%20new_DLLNode%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20pop%20an%20element%20from%20stack%20*%2F%0Aint%20pop(struct%20myStack%20*ms)%0A%7B%0A%20%20%20%20%2F*%20Stack%20underflow%20*%2F%0A%20%20%20%20if%20(ms-%3Ecount%20%20%3D%3D%20%200)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22Stack%20is%20empty%5Cn%22)%3B%0A%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20struct%20DLLNode%20*head%20%3D%20ms-%3Ehead%3B%0A%20%20%20%20int%20item%20%3D%20head-%3Edata%3B%0A%20%20%20%20ms-%3Ehead%20%3D%20head-%3Enext%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20linked%20list%20doesn\u2019t%20become%20empty%2C%20update%20prev%0A%20%20%20%20%2F%2F%20of%20new%20head%20as%20NULL%0A%20%20%20%20if%20(ms-%3Ehead%20!%3D%20NULL)%0A%20%20%20%20%20%20%20%20ms-%3Ehead-%3Eprev%20%3D%20NULL%3B%0A%20%0A%20%20%20%20ms-%3Ecount%20-%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20update%20the%20mid%20pointer%20when%20we%20have%20even%20number%20of%0A%20%20%20%20%2F%2F%20elements%20in%20the%20stack%2C%20i%2Ce%20move%20down%20the%20mid%20pointer.%0A%20%20%20%20if%20(!((ms-%3Ecount)%20%26%201%20))%0A%20%20%20%20%20%20%20%20ms-%3Emid%20%3D%20ms-%3Emid-%3Enext%3B%0A%20%0A%20%20%20%20free(head)%3B%0A%20%0A%20%20%20%20return%20item%3B%0A%7D%0A%20%0A%2F%2F%20Function%20for%20finding%20middle%20of%20the%20stack%0Aint%20findMiddle(struct%20myStack%20*ms)%0A%7B%0A%20%20%20%20if%20(ms-%3Ecount%20%20%3D%3D%20%200)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22Stack%20is%20empty%20now%5Cn%22)%3B%0A%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20ms-%3Emid-%3Edata%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20functions%20of%20myStack%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Let%20us%20create%20a%20stack%20using%20push()%20operation*%2F%0A%20%20%20%20struct%20myStack%20*ms%20%3D%20createMyStack()%3B%0A%20%20%20%20push(ms%2C%2011)%3B%0A%20%20%20%20push(ms%2C%2022)%3B%0A%20%20%20%20push(ms%2C%2033)%3B%0A%20%20%20%20push(ms%2C%2044)%3B%0A%20%20%20%20push(ms%2C%2055)%3B%0A%20%20%20%20push(ms%2C%2066)%3B%0A%20%20%20%20push(ms%2C%2077)%3B%0A%20%0A%20%20%20%20printf(%22Item%20popped%20is%20%25d%5Cn%22%2C%20pop(ms))%3B%0A%20%20%20%20printf(%22Item%20popped%20is%20%25d%5Cn%22%2C%20pop(ms))%3B%0A%20%20%20%20printf(%22Middle%20Element%20is%20%25d%5Cn%22%2C%20findMiddle(ms))%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><strong>Output:<\/strong><\/p>\n<pre>Item popped is 77\r\nItem popped is 66\r\nMiddle Element is 33<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Design a stack with operations on middle element &#8211; Stack &#8211; The idea is to use Doubly Linked List (DLL). We can delete middle element in O(1) time <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,73012,79607],"tags":[81518,81508,81510,81509,81521,81520,81515,70452,81519,81516,81517,81514,81512,77702,81511,81513],"class_list":["post-27389","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-data-structures","category-stack","tag-circular-queue-using-linked-list","tag-deletion-is-possible-for-middle-item-of-stack-true-or-false","tag-design-a-queue-with-operations-on-middle-element","tag-design-a-stack-with-operations-on-middle-element-in-c","tag-double-ended-queue","tag-doubly-linked-list-in-c-program","tag-doubly-linked-list-queue-java","tag-push-and-pop-operation-in-stack-in-data-structure","tag-queue-c","tag-queue-implementation-in-c-using-linked-list","tag-queue-using-array","tag-queue-using-doubly-linked-list-c","tag-queue-using-doubly-linked-list-in-c","tag-stack-program-in-c","tag-stack-using-doubly-linked-list-in-c","tag-the-smallest-divisor-of-an-integer-used-in"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27389","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=27389"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27389\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27389"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27389"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27389"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}