Stack Class in Java Programming.

In Java, the Collection Framework is a unified architecture that provides a set of interfaces, implementations, and algorithms to manipulate and store collections of objects. It provides standard implementations (like ArrayList, LinkedList, HashSet, etc) for these interfaces, catering to diverse data storage and manipulation needs. The java.util.Stack class is a part of this framework, offering a dynamic, resizable implementation of a Last In, First Out (LIFO) stack data structure.

Stack Class in Java.

Stack is a subclass of Vector and follows its structure, but it's designed for stack operations, providing methods specifically for stack functionalities. Despite being part of the Collection Framework, it's an older implementation, and its use is discouraged in favor of more modern alternatives like Deque implementations.

The Stack class supports essential operations like push, pop, peek, empty check, and determining size, mirroring traditional stack functionalities.

List of Basic Stack Operations:

• push(element): Adds an element to the top of the stack.
• pop(): Removes and returns the top element from the stack.
• peek(): Returns the top element without removing it.
• isEmpty(): Checks if the stack is empty.
• search(element): Searches for an element in the stack and returns its position.

How To Use Stack Class in Java?

To create and use the stack in Java, you must import Stack Class from java.util package (java.util.stack) at the beginning of your Java file and instantiate a Stack object with the desired data type as shown below.

Example: Stack<Integer> myStack = new Stack<>(); 

Java Example Code:

// Java Stack Class Implementation code
import java.util.Stack;

public class StackOperationsExample {
    public static void main(String[] args) {
        // Creating a stack of integers
        Stack<Integer> myStack = new Stack<>();

        // Pushing elements onto the stack
        myStack.push(10);
        myStack.push(20);
        myStack.push(30);

        // Accessing the top element without removing it (peek)
        int topElement = myStack.peek();
        System.out.println("Top element: " + topElement);

        // Popping the top element
        int poppedElement = myStack.pop();
        System.out.println("Popped element: " + poppedElement);

        // Checking if the stack is empty
        boolean isEmpty = myStack.empty();
        System.out.println("Is stack empty? " + isEmpty);

        // Determining the size of the stack
        int stackSize = myStack.size();
        System.out.println("Size of stack: " + stackSize);

        // Search for an element in the stack
        int searchElement = 20;
        int position = myStack.search(searchElement);
        if (position != -1) {
            System.out.println("Element " + searchElement + " found at position: " + position);
        } else {
            System.out.println("Element " + searchElement + " not found in the stack");
        }
    }
}

Output:

Top element: 30
Popped element: 30
Is stack empty? false
Size of stack: 2Element 20 found at position: 1

In this above code, we have used integer stack to demonstrate the usage of stack operations in Java; similarly, you can create a stack for different data types. 

• Time Complexity: push(), pop(), peek(), empty(), size() have constant time O(1) complexity. These operations generally perform in constant time regardless of the number of elements in the stack.

• Space Complexity: The space complexity of the Stack in Java is O(n) where n is the number of elements in the stack.

The Stack class in Java offers a convenient way to implement a stack data structure with basic stack operations. While it follows the traditional stack behavior, it's recommended to use more efficient alternatives provided by the Collection Framework to enhance performance and versatility in modern Java programming.

Stack STL in C++.

Stack STL is a very useful tool when we have to work with Stack data structure in real programming because then we do not have to implement the complete stack from the beginning each time we use them in our code. But before learning Stack STL in detail let's get a short idea about C++ STL.

The Standard Template Library (STL) in C++ is a powerful collection of template classes and functions that provides a rich set of algorithms, containers, and functionalities to facilitate generic programming. It is a fundamental part of the C++ programming language, aiming to simplify and enhance code reusability, maintainability, and efficiency. 

What is Stack STL?

In the list of STL containers, we also have Stack STL which is a powerful tool that provides an efficient and easy-to-use implementation of the stack data structure. The std::stack class encapsulates the functionality of a stack, offering a convenient interface to manage data in a Last In, First Out (LIFO) manner.

std::stack abstracts the core stack operations (push, pop, top, isEmpty, and size) into intuitive member functions, simplifying the manipulation of elements in the stack. It is an adapter class that adapts an underlying container (like std::deque, std::vector, or std::list) to provide stack functionalities.

Functions Present in Stack STL.

The std::stack container adapter in C++ provides several functions to manipulate elements in a stack-like structure. Here are the functions available in std::stack:

stack.push(element): Adds an element to the top of the stack.

stack.pop(): Removes the top element from the stack.

stack.top(): Retrieves the top element from the stack without removing it.

stack.empty(): Checks if the stack is empty. Returns true if the stack is empty, else returns false.

stack.size(): Returns the number of elements in the stack.

Stack STL in C++ Program.

To use Stack STL in our code we first have to include <stack> header file and below is the syntax to declare a stack of specific type (e.g., integers).

Syntax: std::stack<dataType> myStack; 

C++ Code:

// C++ Code Example of Stack STL
#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> myStack;

    // Pushing elements onto the stack
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    // Accessing the top element
    cout << "Top element: " << myStack.top() << endl;

    // Popping the top element
    myStack.pop();

    // Checking if the stack is empty
    if (myStack.empty()) {
        cout << "Stack is empty\n";
    } else {
        cout << "Stack is not empty\n";
    }

    // Determining the size of the stack
    cout << "Size of stack: " << myStack.size() << endl;

    return 0;
}

Output:

Top element: 30
Stack is not empty
Size of stack: 2

Time and Space Complexity.

• Time Complexity: push(), pop(), top(), empty(), and size() have constant time complexity O(1) regardless of the number of elements in the stack.

• Space Complexity: The space complexity of std::stack mainly depends on the underlying container used. By default, it uses std::deque as its underlying container, which typically allocates memory in blocks. Therefore, the space complexity can be considered as O(n).

Mostly while problem-solving and in real-world applications we use STL of different data structures instead of building it from the beginning and we also encourage you to learn and use them in your code to make it more efficient but at the same time, you all should know the basic principle and working of stack and other data structure.

How To Initialize a Vector in C++? (5 Different Ways)

In C++, a vector is a dynamic array-like data structure provided by the Standard Template Library (STL). It allows the storage of elements of the same type in a contiguous memory block and provides dynamic resizing, allowing elements to be added or removed efficiently.

Vectors also support random access to elements and offer a variety of useful member functions for manipulation and iteration. There are multiple ways to initialize a vector and here we are going to see 5 different ways to do so. Let's learn each of them one by one.

1. Initializing with Initializer List: 

It is very much similar to initializing an array data structure using curly brackets and the size of the vector is decided based on the number of elements present. 

//C++ Program to initialize vector using initializer
#include<iostream>
#include<vector>
using namespace std;

int main(){

    vector<int> nums = {1, 2, 3, 4, 5};

    for(int it : nums){
        cout<< it << " ";
    }

    return 0;
}

Output:

1 2 3 4 5

2. Initializing using push_back() function: 

It is a built-in function present in the vector used to push the element at the end. Read more to know about vector built-in functions.

//C++ Program to initialize vector one by one
#include<iostream>
#include<vector>
using namespace std;

int main(){

    vector<int> nums;

    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(8);
    nums.push_back(0);

    for(int it : nums){
        cout<< it << " ";
    }

    return 0;
}

Output:

1 2 8 0

3. Initializing with Size and Default Value: 

Here we are declaring two values while creating the vector, the first value defines the size of the vector, and the second value is the default value assigned to all the elements.

//C++ Program to initialize vector by default value
#include<iostream>
#include<vector>
using namespace std;

int main(){

    //vector of size 5 with all elements initialized to 0
    vector<int> nums(5, 0);

    for(int it : nums){
        cout<< it << " ";
    }

    return 0;
}

Output:

0 0 0 0 0

4. Initializing with Range of Elements:

Here we are using one vector to initialize a new vector with the same elements.

//C++ Program to initialize one vector using another vector
#include<iostream>
#include<vector>
using namespace std;

int main(){

    vector<int> nums{7, 2, 3, 1, 5};
    // Create a new vector with the same elements as nums
    vector<int> copyNums(nums.begin(), nums.end()); 

    for(int it : copyNums){
        cout<< it << " ";
    }

    return 0;
}

Output:

7 2 3 1 5

5. Initializing with Array:

Here, in this case, we are going to use the array to initialize a vector. For this, we must know the size of the given array. We have calculated the size using sizeof() function. 

 

//C++ Program to initialize one vector using array
#include<iostream>
#include<vector>
using namespace std;

int main(){

    int arr[] = {1, 2, 3, 4, 5};
    //size of given array
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<int> nums(arr, arr + n);

    for(int it : nums){
        cout<< it << " ";
    }

    return 0;
}

Output:

7 2 3 1 5

So these are the few different ways in which we can initialize a vector. All these initialization is performed within O(n) time complexity. 

Vector Type STL in C++

Vectors are sequence containers that work the same as variable-size Arrays. It is a kind of STL (Standard Template Library) based on a class template that can provide standard functionality like a Dynamic Array. Similarly, like an array, a vector can be of any type like a character array, integer array, boolean array, string array, etc. 

A Template is not a class or function it is like a blueprint or a guideline for the compiler to use the template to create a specific class or function. We specify which class to instantiate by supplying additional information depending on the template in our case we will specify the vector data type in between two angle brackets after the template name.

• syntax: vector<datatype> vector_name;
• example: vector<int> myvec;(alert-success)

In a vector, elements are in contiguous memory locations, and when we insert a value in a vector stored at the end. Removing or inserting values into a vector takes a constant amount of time and their size grows dynamically as their storage is handled by a container. We need to include a specific <vector> header file in our C++ program to use all the functionality of vector. 

Vector Functions.

There is a list of member functions available in the vector header file that we can directly use for solving our coding problems. Let's understand them one by one.

Iterator member functions:

Member Function	Definition
begin()	This function returns an iterator pointer pointing to the first element of the vector.
end()	This function returns an iterator pointer pointing to the last element of the vector.
rbegin()	This function returns a reverse iterator pointer pointing to the last element of the vector. It follows a reverse order and moves from the last element toward the first.
rend()	This function returns a reverse iterator pointer pointing to the first element of the vector. It follows a reverse order and moves from the first element toward the last.
cbegin()	This function returns a const_iterator pointing to the first element of the vector container. This const_iterator is used to point to a const value.
cend()	This function returns a const_iterator pointing to the last element of the vector container. This const_iterator is used to point to a const value.
crbegin()	This function returns a const_reverse_iterator pointing to the last element of the vector container.
crend()	This function returns a const_reverse_iterator pointing to the first element of the vector container.

C++ Example Code:

//C++ Program to show iterator function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    cout<<"Printing values using begin() and end() fun: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    cout<<"\nPrinting values using rbegin() and rend(): ";
    for(auto it = myVec.rbegin(); it != myVec.rend(); it++)
       cout<<*it<<" ";

    cout<<"\nPrinting values using cbegin() and cend(): ";
    for(auto it = myVec.cbegin(); it != myVec.cend(); it++)
       cout<<*it<<" ";  

    cout<<"\nPrinting values using crbegin() and crend(): ";
    for(auto it = myVec.crbegin(); it != myVec.crend(); it++)
       cout<<*it<<" ";   

    return 0;        
}

Output:

Printing values using begin() and end() fun: 2 3 4 5 6 7
Printing values using rbegin() and rend(): 7 6 5 4 3 2
Printing values using cbegin() and cend(): 2 3 4 5 6 7
Printing values using crbegin() and crend(): 7 6 5 4 3 2

Vector Functions to Check Capacity.

Member Function	Definition
size()	This function returns the size of the vector or we can say it returns a number of elements present in the vector.
capacity()	This function returns the current allocated storage space to the vector. This capacity might not be equal to the size of the vector.
shrink_to_fit()	This function decreases the current capacity of the vector container and makes it equal to the size.
resize(n)	This function changes the vector's current size to make it fit for n elements.
reserve()	This function requests that the vector capacity be at least enough for n elements only when the current capacity is not enough for n elements.
empty()	This function is used to check if the vector is empty or not or if the size is equal to 0 then it returns true else returns false.
max_size()	This function gives us an idea about the maximum number of elements the vector can hold.

C++ Example Code:

//C++ Program to show capacity function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    if(!myVec.empty()){
        cout<<"Size: "<<myVec.size()<<endl;
        cout<<"Capacity: "<<myVec.capacity()<<endl;
        cout<<"Maximum Size: "<<myVec.max_size()<<endl;

        myVec.shrink_to_fit();
        cout<<"Capacity after shrinking: "<<myVec.capacity()<<endl;
    }
    else{
        cout<<"Vector is empty!!!"<<endl;
    } 

    cout<<"Elements present in the vector: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    return 0;        
}

Output:

Size: 6
Capacity: 8
Maximum Size: 230584300921363951
Capacity after shrinking: 6
Elements present in the vector: 2 3 4 5 6 7

Element Access member functions:

Member Function	Definition
operator[i]	This function returns a reference to the element at the position mentioned in the square bracket in the vector.
at(i)	This function works the same as the previous one and returns a reference to the element present at position i in the vector.
front()	This function returns a reference to the first element of the vector.
back()	This function returns a reference to the first element of the vector.
data()	This function returns a direct pointer to the memory array used internally by the vector to store its owned elements.

C++ Example Code:

//C++ Program to show Element access function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    cout<<"Elements present in the vector: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    cout<<"\nElement at position myVec[3]: "<<myVec[3]<<endl;
    myVec[3] = 10;
    cout<<"Element at position myVec[3]: "<<myVec.at(3)<<endl;

    cout<<"First element of vector: "<<myVec.front()<<endl;
    cout<<"Last element of vector: "<<myVec.back()<<endl;

    int *p = myVec.data();
    cout<<"First element of vector: "<<*p;

    return 0;        
}

Output:

Elements present in the vector: 2 3 4 5 6 7
Element at position myVec[3]: 5
Element at position myVec[3]: 10
First element of vector: 2
Last element of vector: 7
First element of vector: 2

Vector Modifier member functions.

Member Function	Definition
push_back()	This function is used to insert or add an element at the end of the vector.
pop_back()	This function is used to delete an element from the end of the vector.
insert()	This function is used to insert an element before the element at the specified position.
assign()	This function is used to assign new values to the vector elements by replacing the old values.
erase()	This function is used to remove a single element or a range of elements from a vector.
swap()	This function is used to swap the values of one vector with the values of other vectors of the same type. The size of both vectors might not be the same.
clear()	This function is used to remove all the elements of the vector and empty it.
emplace()	This function is used to insert a new element at a specific position and extend the size of the vector by one.
emplace_back()	This function is used to insert a new element at the end position and effectively extend the size of the vector by one.

C++ Example Code:

//C++ Program to show Element access function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    cout<<"Elements present in the vector: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    myVec.push_back(50);
    cout<<"\nLast Element after push_back: "<<myVec.back()<<endl;
    //removing the last element
    myVec.pop_back();
    cout<<"Last Element after pop_back: "<<myVec.back()<<endl;

    //inserting element at pos 4
    myVec.insert(myVec.begin()+3, 35);
    cout<<"Element at position 4: "<<myVec[4]<<endl;
    
    cout<<"Size of vector before emplace: "<<myVec.size()<<endl;
    myVec.emplace(myVec.begin()+4, 55);
    cout<<"Size of vector after emplace: "<<myVec.size()<<endl;

    myVec.clear();
    cout<<"Size of vector after clear: "<<myVec.size()<<endl;

    return 0;        
}

Output:

Elements present in the vector: 2 3 4 5 6 7
Last Element after push_back: 50
Last Element after pop_back: 7
Element at position 4: 5
Size of vector before emplace: 7
Size of vector after emplace: 8
Size of vector after clear: 0

Various operations that we perform on the vector has different time complexity like,

• Accessing any random element takes a constant amount of time O(1).
• Inserting or removing elements takes a linear amount of time O(n) except for the last element which takes a constant amount of time O(1).
• Resizing the vector size in an operation like insert or emplace takes a linear amount of time O(n). 

Next:

(getButton) #text=(Stack STL Container in C++) #icon=(link) #color=(#2339bd)

Stack STL Container in C++.

Stack is a Linear Data Structure that is based on LIFO (Last In First Out) principle and we also have a Stack container class in C++ STL (Standard Template Library) that is implemented based on the same LIFO principle. 

When you use STL Stack, you don't have to worry about the implementation part of the stack operations like push(), pop(), top(), and empty() because in STL Stack all these operations are already provided in the form of a member function. You can directly use these member functions inside your program without thinking about the implementation part. 

Important Stack STL member functions:

• push(): It is used to insert an element at the top end of the Stack.
• pop(): It is used to delete the topmost element of the Stack.
• top(): It returns the topmost element present in the Stack. This function just returns the value present on the top it does not remove that element from the Stack.
• empty(): It is a boolean function that will return true if Stack is empty else it will return false.
• size(): It is used to get the count of the number of elements present in the Stack.

Syntax: stack<datatype> stackname;

Example: C++ code for STL Stack.

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack<int> st;

    st.push(50);
    st.push(40);
    st.push(30);
    st.push(20);
    st.push(10);

    cout << "Element present at the top: " << st.top() << endl;
    // delete top element of the stack
    st.pop();
    cout << "Top element after deletion: " << st.top() << endl;
    if (st.empty())
    {
        cout << "Stack is Empty." << endl;
    }
    else
    {
        cout << "Stack is not Empty." << endl;
    }
    cout << "Number of element present in stack " << st.size() << endl;
}

Output:

Element present at the top: 10      
Top element after deletion: 20      
Stack is not Empty.
Number of element present in stack 4