Yashb | Stack

# Stack

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

## 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:

• Add: insert a new item to the right end of the stack (top).
• Remove: delete the last item added to the stack (the item at the top)
• Get: returns the last item added to the stack (the item at the top)

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:

3. Get
5. Remove
7. Remove
8. Get

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

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

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

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

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

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

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

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

## Stack Implementation

#include <iostream>

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;

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

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)

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

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