data-structures Stack Intro to Stack

Example

The stack is a LIFO (last-in, first-out) data-structure, i.e. the most recent (or "last in") element added to the stack will be the first element removed ("first out").

Let us consider the example of books in a box. Only one book can be added or removed from from the box at a time, and it can only be added and removed from the top.

Now, the box with the first two books looks like this:

  |--------|
  | book 2 | ◀──── top of box
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

If we add book 3, it will be at the top. The rest of the books, which were added before book 3, will remain below it:

  |--------|
  | book 3 | ◀──── top of box
  |--------|
  | book 2 |
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

The box is like a stack and the books are data elements. Adding a book to the box is the push operation while removing/getting a book from the top of the box is the pop operation. If we perform the pop operation, we will get book 3, and the box will go back to the way it was before we pushed book 3. This means that the last (or most recent) element that we put in was the first element we got out (LIFO). In order to get book 1, we have to perform two more pops: one to remove book 2, and the second to get book 1.

Implementation of the stack using an array. For this, we need an index pointing to the top location (tos). Every time an element is pushed into the stack the tos increments by one and whenever a pop operation is performed the index pointing the top of the stack (tos) is decremented by one.

PUSH:

Before the PUSH operation

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|

void push(dataElment item){
    stack[top]=item; //item = i4
    top++;
    
}

After the PUSH operation The stack has a pointer to the top of the stack. Whenever the push operation is called it places the value at the top and updates it the value.

        tos -- Top of the stack
                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |     |
        |-----|-----|-----|-----|

POP : The pop operation removes the content from the top of the stack and updates the value of tos by decrementing by 1

Before the pop operation:

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|

dataElment pop(){
    dataElment value = stack[tos--];
    return value;
}

After the pop operation:

                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |
        |-----|-----|-----|-----|
        When a push operation is performed it overwrites i4.