{"id":272,"date":"2017-06-14T12:09:00","date_gmt":"2017-06-14T10:09:00","guid":{"rendered":"https:\/\/kindsonthegenius.com\/blog\/2017\/06\/14\/stacks\/"},"modified":"2020-08-22T20:42:45","modified_gmt":"2020-08-22T18:42:45","slug":"stacks","status":"publish","type":"post","link":"https:\/\/kindsonthegenius.com\/blog\/stacks\/","title":{"rendered":"Stacks"},"content":{"rendered":"
Stacks are very important in the study of Data Structures. But in this article we would examine the basics of Stack Data Structure and how stack is represented.<\/div>\n
<\/div>\n
<\/div>\n
Below is what is to be presented in this article.<\/div>\n
    \n
  1. Definition of Stack<\/li>\n
  2. Stack Representation<\/li>\n
  3. Application of Stacks<\/li>\n
  4. Conversion of Decimal to Binary<\/li>\n
  5. Expression Syntax Parsing<\/li>\n<\/ol>\n
    <\/div>\n
    <\/div>\n
    Definition<\/b>\u00a0of Stack<\/b><\/div>\n
    A stack is a linear data structure that allows for insertion and deletion of items from one end of the stack called the top of the stack. This means that the last item to be inserted into to stack is always the first item to be retrieved from the stack and vice versa. So we can can say that stack supports Last In First Out(LIFO), data storage and retrieval. Stacks are normally used in the computer system for temporary data storage.<\/div>\n
    <\/div>\n
    <\/div>\n
    <\/a><\/div>\n
    <\/div>\n
    <\/div>\n
    Take note of the following terms:<\/div>\n
    Push<\/b>: The action of inserting an item on top of the stack<\/div>\n
    Pop<\/b>: The action of retrieving an item from the top of the stack<\/div>\n
    Initialize<\/b>: Start a new stack<\/div>\n
    <\/div>\n
    <\/div>\n
    Linked-List Stack Representation<\/b><\/div>\n
    The most common representation of stack is by the use of linked list. Before we examine the Linked-List representation, below are operations that can be performed on a stack. These operation are actually methods that can generally be performed on an object of type Stack.<\/div>\n
    <\/div>\n
    push(new_item:item_type)<\/strong><\/div>\n
    Adds a new item on top of the stack.<\/div>\n
    <\/div>\n
    top() :<\/b>\u00a0item_type<\/div>\n
    Returns that last item inserted into the stack<\/div>\n
    <\/div>\n
    pop()<\/b><\/div>\n
    Retrieves that last item from top of the stack<\/div>\n
    <\/div>\n
    is-empty()<\/b>\u00a0: Boolean<\/div>\n
    Returns true if the Stack is empty else returns false<\/div>\n
    <\/div>\n
    is-full():<\/b>\u00a0Boolean<\/div>\n
    Returns True if the stack is full else returns false<\/div>\n
    <\/div>\n
    get-size()<\/b>\u00a0: Integer<\/div>\n
    Returns an integer representing the size of the stack.<\/div>\n
    <\/div>\n
    <\/div>\n
    Application of Stacks<\/b><\/div>\n
    Stacks can be applied in many areas of life including: Stack of trays in a restaurant, stack of books, stack of plates etc. But we are going to closely examine the following:<\/div>\n
    <\/div>\n
    1. Converting Decimal to Binary<\/b><\/div>\n
    Consider the conversion of a decimal number into its binary equivalent. The algorithm goes as follows:<\/div>\n
    <\/div>\n
    Read a decimal number<\/div>\n
    While the number is greater than zero, continue<\/div>\n
    \u00a0 \u00a0 Divide the number by two<\/div>\n
    \u00a0 \u00a0 Find the remainder<\/div>\n
    \u00a0\u00a0 \u00a0Write the remainder<\/div>\n
    End<\/div>\n
    <\/div>\n
    Example<\/b><\/i>
    \nImplement the algorithm, to covert the decimal number 25 to binary<\/i><\/div>\n
    If the algorithm above it applied, the program would print out the binary number 10011 and this would be the wrong answer.<\/div>\n
    <\/div>\n
    To get the right answer, we need to implement this algorithm using a stack data structure. Each of the binary digits is pushed on to a attack as they are generated. At the end of the whole conversion, each digit is retrieved from the stack and printed.<\/div>\n
    The correct result would be as shown in the figure below.<\/div>\n
    <\/div>\n
    \n
    <\/a><\/div>\n<\/div>\n
    <\/div>\n
    Other applications of stack include, Expression syntax evaluation, Rearranging Railroad cars and the Quicksort Algorithm.<\/div>\n","protected":false},"excerpt":{"rendered":"

    Stacks are very important in the study of Data Structures. But in this article we would examine the basics of Stack Data Structure and how … <\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0},"categories":[35],"tags":[],"_links":{"self":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/272"}],"collection":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/comments?post=272"}],"version-history":[{"count":2,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/272\/revisions"}],"predecessor-version":[{"id":713,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/272\/revisions\/713"}],"wp:attachment":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/media?parent=272"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/categories?post=272"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/tags?post=272"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}