Yashb | Stack
Home / STL

Stack

Warawreh 02 Feb, 2022 10 min

Table of contents

Stack


Definition


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 
#include //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






Read Also

Queue
Deque
Kaggle Competitions
Federated Learning
YOLO Real-Time Object Detection

Most Read

What is big O notation (The complexity) and how to calculate it?
Queue
Deque
Random Number Generator (RNG)
Convert image to text using PYTHON!