{"id":266,"date":"2018-10-31T17:28:42","date_gmt":"2018-10-31T17:28:42","guid":{"rendered":"https:\/\/books.compclassnotes.com\/elementarycomputing\/?page_id=266"},"modified":"2018-11-05T12:26:38","modified_gmt":"2018-11-05T12:26:38","slug":"stacks","status":"publish","type":"page","link":"https:\/\/books.compclassnotes.com\/elementarycomputing\/stacks\/","title":{"rendered":"Stacks"},"content":{"rendered":"<p>Stacks are a <em>data structure:\u00a0<\/em>a logical collection of data which has various ways that programmers can access it. You\u00a0are probably used to data structures such as\u00a0<strong>arrays<\/strong>, which are typically fixed length indexed structures like the one below:<\/p>\n<div id=\"attachment_348\" style=\"width: 522px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-348\" class=\" wp-image-348\" src=\"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/11\/Array.png\" alt=\"\" width=\"512\" height=\"178\" srcset=\"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/11\/Array.png 1586w, https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/11\/Array-300x104.png 300w, https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/11\/Array-768x267.png 768w, https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/11\/Array-1024x356.png 1024w\" sizes=\"auto, (max-width: 512px) 100vw, 512px\" \/><p id=\"caption-attachment-348\" class=\"wp-caption-text\">A simple array with ten elements.<\/p><\/div>\n<p>Data structures such as arrays are\u00a0<em>random access<\/em>, meaning that we can access any part of them at any time. For example, we can directly access any part of it. A stack is a very restricted data structure. It has literally a stack of items, with a top and a bottom, but the only item we can directly access is the item on top.<\/p>\n<div id=\"attachment_267\" style=\"width: 270px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-267\" class=\"wp-image-267\" src=\"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/10\/Stack1.png\" alt=\"\" width=\"260\" height=\"223\" srcset=\"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/10\/Stack1.png 422w, https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/10\/Stack1-300x257.png 300w\" sizes=\"auto, (max-width: 260px) 100vw, 260px\" \/><p id=\"caption-attachment-267\" class=\"wp-caption-text\">A simple stack.<\/p><\/div>\n<p>Items are\u00a0<strong>pushed<\/strong> onto the top of the stack, so if we executed:<\/p>\n<p><strong>Push 11<\/strong><\/p>\n<p>Then\u00a0<strong>11<\/strong> would go on top of the stack:<\/p>\n<div id=\"attachment_269\" style=\"width: 269px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-269\" class=\" wp-image-269\" src=\"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/10\/Stack2.png\" alt=\"\" width=\"259\" height=\"205\" srcset=\"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/10\/Stack2.png 434w, https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-content\/uploads\/sites\/9\/2018\/10\/Stack2-300x237.png 300w\" sizes=\"auto, (max-width: 259px) 100vw, 259px\" \/><p id=\"caption-attachment-269\" class=\"wp-caption-text\">The stack with 11 pushed on top.<\/p><\/div>\n<p>To remove the top item, we\u00a0<strong>Pop<\/strong> the stack. Notice that Pop doesn&#8217;t take an argument, because it simply pops the top item off. If we pop this stack, pop returns 11 and removes it from the stack. Although restrictive in terms of how we access them, stacks have a number of advantages. First, they are dynamic data types, meaning that they grow and contract as needed. Second, they don&#8217;t have a data type &#8211; this is probably very different from most programming languages that you&#8217;ve dealt with, as they generally insist on being told what type (character, integer, float, etc.) is going to be stored. Stacks don&#8217;t even have to store items of the same type. Take a play with the example below:<\/p>\n\n<!-- iframe plugin v.6.0 wordpress.org\/plugins\/iframe\/ -->\n<iframe loading=\"lazy\" src=\"https:\/\/my.compclassnotes.com\/canonical\/connor\/stacks_example\" width=\"100%\" height=\"1280\" marginwidth=\"0\" marginheight=\"0\" 0=\"scrolling=&quot;yes\u201d\" scrolling=\"yes\" class=\"iframe-class\" frameborder=\"0\"><\/iframe>\n\n<p>Stacks are often used to process incoming strings of characters. In these cases, Push doesn&#8217;t take an argument, and instead simply pushes the first item from the string onto the stack. Similarly, Pop pops the stack and sends the character to the output.<\/p>\n<p>Take a look at the following example in which reverses the order of an expression:<\/p>\n\n<!-- iframe plugin v.6.0 wordpress.org\/plugins\/iframe\/ -->\n<iframe loading=\"lazy\" src=\"https:\/\/my.compclassnotes.com\/canonical\/connor\/stacks_infix_reverse_example\" width=\"100%\" height=\"2280\" marginwidth=\"0\" marginheight=\"0\" scrolling=\"yes\" class=\"iframe-class\" frameborder=\"0\"><\/iframe>\n\n<p>Great, so now we know how stacks work, but what can we do with them? The next section gives a nice simple algorithm that uses a stack to convert from an arbitrarily complex infix expression to the corresponding prefix one.<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Stacks are a data structure:\u00a0a logical collection of data which has various ways that programmers can access it. You\u00a0are probably used to data structures such as\u00a0arrays, which are typically fixed length indexed structures like the one below: Data structures such <span class=\"readmore\"><a href=\"https:\/\/books.compclassnotes.com\/elementarycomputing\/stacks\/\">Continue Reading<\/a><\/span><\/p>\n","protected":false},"author":4,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-266","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/266","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/comments?post=266"}],"version-history":[{"count":7,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/266\/revisions"}],"predecessor-version":[{"id":360,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/266\/revisions\/360"}],"wp:attachment":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/media?parent=266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}