Home > Data Structures > Stack(for concept only only)

Stack(for concept only only)

November 12, 2010 Leave a comment Go to comments
  1. Abstraction

    Now, let’s think about a stack in an abstract way. I.e., it doesn’t hold any particular kind of thing (like books) and we aren’t restricting ourselves to any particular programming language or any particular implementation of a stack.

    Stacks hold objects, usually all of the same type. Most stacks support just the simple set of operations we introduced above; and thus, the main property of a stack is that objects go on and come off of the top of the stack.

    Here are the minimal operations we’d need for an abstract stack (and their typical names):

     

    • Push: Places an object on the top of the stack. 
    • Pop: Removes an object from the top of the stack and produces that object. 
    • IsEmpty: Reports whether the stack is empty or not.

    Because we think of stacks in terms of the physical analogy, we usually draw them vertically (so the top is really on top).

     

  2. Order produced by a stack: 

    Stacks are linear data structures. This means that their contexts are stored in what looks like a line (although vertically). This linear property, however, is not sufficient to discriminate a stack from other linear data structures. For example, an array is a sort of linear data structure. However, you can access any element in an array–not true for a stack, since you can only deal with the element at its top.

    One of the distinguishing characteristics of a stack, and the thing that makes it useful, is the order in which elements come out of a stack. Let’s see what order that is by looking at a stack of letters…

    Suppose we have a stack that can hold letters, call it stack. What would a particular sequence of Push and Pops do to this stack?

    We begin with stack empty:

    -----
    stack
    

    Now, let’s perform Push(stack, A), giving:

    -----
    | A |  <-- top
    -----
    stack
    

    Again, another push operation, Push(stack, B), giving:

    -----
    | B |  <-- top
    -----
    | A |
    -----
    stack
    

    Now let’s remove an item, letter = Pop(stack), giving:

    -----              -----
    | A |  <-- top     | B |
    -----              -----
    stack              letter
    

    And finally, one more addition, Push(stack, C), giving:

    -----
    | C |  <-- top
    -----
    | A |
    -----
    stack
    

    You’ll notice that the stack enforces a certain order to the use of its contents, i.e., the Last thing In is the First thing Out. Thus, we say that a stack enforces LIFO order.

    Now we can see one of the uses of a stack…To reverse the order of a set of objects.

     

  3. Implementing a stack with an array:Let’s think about how to implement this stack in the C programming language.

    First, if we want to store letters, we can use type char. Next, since a stack usually holds a bunch of items with the same type (e.g., char), we can use an array to hold the contents of the stack.

    Now, consider how we’ll use this array of characters, call it contents, to hold the contents of the stack. At some point we’ll have to decide how big this array is; keep in mind that a normal array has a fixed size.

    Let’s choose the array to be of size 4 for now. So, an array getting A, then B, will look like:

    -----------------
    | A | B |   |   |
    -----------------
      0   1   2   3
    contents
    

    Is this array sufficient, or will we need to store more information concerning the stack?

    Answer: We need to keep track of the top of the stack since not all of the array holds stack elements.

    What type of thing will we use to keep track of the top of the stack?

    Answer: One choice is to use an integer, top, which will hold the array index of the element at the top of the stack.

    Example:

    Again suppose the stack has (A,B) in it already…

    stack (made up of 'contents' and 'top')
    -----------------   -----
    | A | B |   |   |   | 1 |
    -----------------   -----
      0   1   2   3      top
    contents
    

    Since B is at the top of the stack, the value top stores the index of B in the array (i.e., 1).

    Now, suppose we push something on the stack, Push(stack, 'C'), giving:

    stack (made up of 'contents' and 'top')
    -----------------   -----
    | A | B | C |   |   | 2 |
    -----------------   -----
      0   1   2   3      top
    contents
    

    (Note that both the contents and top part have to change.)So, a sequence of pops produce the following effects:

     

    1. letter = Pop(stack)
      stack (made up of 'contents' and 'top')
      -----------------   -----    -----
      | A | B |   |   |   | 1 |    | C |
      -----------------   -----    -----
        0   1   2   3      top     letter
      contents
      
    2. letter = Pop(stack)
      stack (made up of 'contents' and 'top')
      -----------------   -----    -----
      | A |   |   |   |   | 0 |    | B |
      -----------------   -----    -----
        0   1   2   3      top     letter
      contents
      
    3. letter = Pop(stack)
      stack (made up of 'contents' and 'top')
      -----------------   -----    -----
      |   |   |   |   |   | -1|    | A |
      -----------------   -----    -----
        0   1   2   3      top     letter
      contents
      

    so that you can see what value top should have when it is empty, i.e., -1.

    Let’s use this implementation of the stack with contents and top fields.

     


    What happens if we apply the following set of operations? 

    1. Push(stack, 'D')
    2. Push(stack, 'E')
    3. Push(stack, 'F')
    4. Push(stack, 'G')

    giving:

    stack (made up of 'contents' and 'top')
    -----------------   -----
    | D | E | F | G |   | 3 |
    -----------------   -----
      0   1   2   3      top
    contents
    

    and then try to add H with Push(stack, 'H')?

    Thus, what is the disadvantage of using an array to implement a stack?

Advertisements
Categories: Data Structures
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: