Yashb | Stack

Stack

  • by Warawreh
  • Last updated: 2022-02-02 12:23:10
  • Estimated time to read: 10 minutes


Stack

Defenition

Stack is an STL used to store and load items using the LIFO System (last in first out), which means items can be added to the end of the stack only and the last item added is the only item that can be accessed (get, edit or remove).


In the stack, all operations are done on one end, the right end, which is usually referred to as the "top".

Stack Operations

There are some operations used in stacks to add new items, access items in the stack, and remove items:

All operations supported by the stack have time complicity of O(1) so the overall complexity of the stack is O(1) the space complicity of the stack is O(n) where n is the number of items.

Example on Stack

Let's observe how the stack works when we apply the following operations in the same order they were given:

  1. Add 2
  2. Add 3
  3. Get
  4. Add 0
  5. Remove
  6. Add 1
  7. Remove
  8. Get

Stack       Stack 

(1) In the beginning the stack is empty, after the first operation 2 will be added to the top of the stack

Stack       Stack 

(2) After the second operation 3 will be added to the top of the stack

Stack 

(3) The third operation is a Get operation and the result is the item in the top (3)


Stack       Stack

(4) The fourth operation is an Add 0 operation so 0 is added to the top of the stack

Stack       Stack

(5) The fifth operation is a Remove operation so the item at the top of the stack is removed

 Stack       Stack

(6) The Sixth operation is an Add 1 operation so 1 is added to the top of the stack

Stack       Stack

(7) The seventh operation is a Remove operation so the item at the top of the stack is removed

  Stack

(8) The eighth operation is a Get operation and the result is the item in the top (3)


Stack Implementation


#include <iostream>
#include <stack>//Stack header

using namespace std;

int main(){
    /*
    In C++:
        push is used to add items to the stack
        pop is used to remove the last item in the stack
        top is used to get the last item in the stack
    */

    //Create an empty stack
    stack<int> items;

    //Add 2
    items.push(2);
    //2 is added to the end of the stack //items = 2 <- item in the top
        
    //Add 3
    items.push(3);
    //items = 2, 3 <- item in the top

    //Get
    cout << "Item on top is: " << items.top() << endl;
    //Prints the item in the top of the stack (3)

    //Add 0
    items.push(0);
    //items = 2, 3, 0 <- item in the top

    //Remove
    items.pop();
    //Removes the item in the top of the stack (0)//items = 2, 3 <- item in the top

    //Add 1
    items.push(1);
    //items = 2, 3, 1 <- item in the top

    //Remove
    items.pop();
    //Removes the item in the top of the stack (1)//items = 2, 3 <- item in the top

    //Get
    cout << "Item on top is: " << items.top() << endl;
    //Prints the item in the top of the stack (3)
}



Output:
Item on top is: 3
Item on top is: 3





Table of contents