Stack Implementation in Python.

In Python, the stack data structure represents a fundamental and versatile form of collection, adhering to the Last In, First Out (LIFO) principle. It organizes elements in a manner where the last element added is the first one to be removed, resembling a stack of items. Python facilitates stack implementation through its built-in data structures like lists or by utilizing modules from the collections or queue libraries.

Note: Here we will cover stack implementation in Python programming. If you are not familiar with stack data structure then you can check our post "Introduction to Stack Data Structure" in which we have explained the stack in complete detail with code.

Basic Stack Operations.

• push(element): Add/Insert an element onto the stack.
• pop(): Remove the element from the top of the stack.
• peek(): View the top element without removing it.
• empty(): Check if the stack is empty. Return true if the stack is empty.
• size(): Find the number of elements present in the stack.

Implementation of Stack in Python.

There are various methods to implement stack in Python and here we are going to learn three different methods:

• Using List.
• Using collection.deque.
• Using queue.LifoQueue.

Stack Implementation Using List.

The stack implementation in Python using a list mirrors the behavior of a traditional stack data structure by utilizing Python's built-in list functions. Elements are added to the top of the stack, resembling a push operation via the append() method. Similarly, the pop() function removes and returns the top element, replicating the stack's pop operation.

To view the top element without removing it (peek operation), referencing the last element (self.stack[-1]) of the list is employed, providing a glimpse into the topmost element of the stack. The size of the stack is determined by obtaining the length of the underlying list (len(self.stack)), indicating the number of elements present.

However, the implementation has drawbacks. Python lists utilize dynamic arrays, resulting in automatic resizing to accommodate elements. While append() and pop() operations typically offer O(1) time complexity, the occasional resizing might lead to O(n) complexity in specific cases, impacting performance.

Python Code:

class StackUsingList:
    # Initializing an empty list as a stack
    def __init__(self):
        self.stack = []  
    
    # Adding an element to the top of the stack
    def push(self, element):
        self.stack.append(element)  

    # Removing and returning the top element from the stack
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()  
        else:
            return "Stack is empty"
    
    # Returning the top element without removing it
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]  
        else:
            return "Stack is empty"
    
    # Checking if the stack is empty
    def is_empty(self):
        return len(self.stack) == 0  
    
    # Determining the size of the stack
    def size(self):
        return len(self.stack)  

# Example usage:
stack = StackUsingList()
stack.push(10)
stack.push(20)
stack.push(30)

print("Size of stack:", stack.size())  

print("Top element:", stack.peek()) 

print("Popped element:", stack.pop()) 

print("Is stack empty?", stack.is_empty())  

Output:

Size of stack: 3
Top element: 30
Popped element: 30
Is stack empty? False

Stack Implementation Using collection.deque.

The stack implementation using collection.deque in Python provides an efficient alternative to mimic stack behavior while addressing some of the drawbacks of using lists.

Implementation:

• To Initialize an empty dequeue from the collections module to serve as the stack: stack = dequeu().
• To add elements to the stack (push) we use the append() function of deque. This adds elements to the right side of the deque, emulating the stack's push operation.
• To remove or retrieve the top element (pop) from the stack we use pop() function of the deque. This removes and returns the rightmost element, simulating the stack's pop operation.
• To access the top element without removing it (peek) by referencing the rightmost element (stack[-1]) of the deque, providing a view into the top element.
• To verify if the stack is empty we check the length of the deque and if the length is 0 (len(stack) == 0) it means the stack is empty.
• To determine the size of the stack by retrieving the length of the deque (len(stack)), indicating the count of elements in the stack.

Python Code:

from collections import deque

class StackUsingDeque:
    # Initializing an empty deque as a stack
    def __init__(self):
        self.stack = deque()  

    # Adding an element to the top of the stack
    def push(self, element):
        self.stack.append(element)  

    # Removing and returning the top element from the stack
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()  
        else:
            return "Stack is empty"

    # Returning the top element without removing it
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]  
        else:
            return "Stack is empty"
    
    # Checking if the stack is empty
    def is_empty(self):
        return len(self.stack) == 0  
    
    # Determining the size of the stack
    def size(self):
        return len(self.stack)  

# Example usage:
stack = StackUsingDeque()
stack.push(10)
stack.push(20)
stack.push(30)

print("Size of stack:", stack.size())  

print("Top element:", stack.peek())

print("Popped element:", stack.pop())

print("Is stack empty?", stack.is_empty())  

Output:

Size of stack: 3
Top element: 30
Popped element: 30
Is stack empty? False

Stack Implementation using queue.LifoQueue.

The implementation of a stack queue.LifoQueue in Python provides a direct and thread-safe approach to creating a stack data structure adhering to the Last-In, First Out (LIFO) principle. This implementation is part of the queue module, offering synchronization and efficient LIFO-based operations for managing in a stack-like manner.

The functionality of Stack Implementation using the queue.LifoQueue:

• Initialize an empty stack using LifoQueue: stack = LifoQueue(). This creates a stack structure optimized for LIFO operations.
• Add elements onto the stack (push) using the put() method of LifoQueue. Elements are inserted into the stack, following the LIFO order, ensuring the last element added becomes the top of the stack.
• Remove and retrieve elements from the top of the stack(pop) using the get() method of LifoQueue. This retrieves elements in the reverse order of their insertion, effectively mimicking the behavior of a stack.
• Accessing the top element of the stack without removing it (peek) by using not_empty() attribute allows viewing the top element without altering the stack contents.
• Obtain the size of the stack using the qsize() method of LifoQueue, which retrieves the count of elements present in the stack.

Python Code:

from queue import LifoQueue

# Initializing a LifoQueue as a stack
class StackUsingLifoQueue:
    def __init__(self):
        self.stack = LifoQueue()

    # Adding an element to the top of the stack
    def push(self, element):
        self.stack.put(element)

    # Removing and returning the top element from the stack
    def pop(self):
        if not self.is_empty():
            return self.stack.get()  
        else:
            return "Stack is empty"

    def peek(self):
        if not self.is_empty():
            top_element = self.stack.get()
            # Restoring the element after peeking
            self.stack.put(top_element)
            # Returning the top element without removing it  
            return top_element  
        else:
            return "Stack is empty"

    # Checking if the stack is empty
    def is_empty(self):
        return self.stack.empty()  
     
    # Determining the size of the stack
    def size(self):
        return self.stack.qsize()

# Example usage:
stack = StackUsingLifoQueue()
stack.push(10)
stack.push(20)
stack.push(30)

stack.push(40)

print("Size of stack:", stack.size()) 

print("Top element:", stack.peek())  

print("Popped element:", stack.pop())  

print("Is stack empty?", stack.is_empty())  

Output:

Size of stack: 4
Top element: 40
Popped element: 40
Is stack empty? False

I hope now you understand three different ways to implement stack data structure in Python. Stack is a very useful data structure and have many applications in numerous domains, from handling function calls to algorithmic problem-solving, making it an essential component in Python programming.

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.

Python Program to Subtract two Matrices.

Matrix subtraction is a fundamental operation in linear algebra and is often required in various scientific and computational applications. In this article, we'll explore how to subtract two matrices using Python programming.

In matrix subtraction, elements of one matrix are subtracted from their corresponding elements in another matrix of the same dimensions. The result is a new matrix with dimensions identical to the original matrices being subtracted. 

Quick Tip: Ensure matrices have the same dimensions for subtraction (m x n).

Matrix Subtraction Program in Python.

Step-by-step Algorithm:

• Define two matrices A and B, each represented as nested lists in Python.

• Create a new matrix to store the result of the subtraction.

• Subtract corresponding elements of matrices A and B to obtain the elements of the resultant matrix.

• Use nested loops to iterate through each element in the matrices and perform subtraction.

Python Code:

# Python code for matrix subtraction
def subtract_matrices(matrix_A, matrix_B):
    result_matrix = []
    for i in range(len(matrix_A)):
        row = []
        for j in range(len(matrix_A[0])):
            row.append(matrix_A[i][j] - matrix_B[i][j])
        result_matrix.append(row)
    return result_matrix

# Example usage
matrix_A = [[1, 2, 3],
            [4, 5, 6],
            [7, 8, 9]]

matrix_B = [[9, 8, 7],
            [6, 5, 4],
            [3, 2, 1]]

result = subtract_matrices(matrix_A, matrix_B)
print("Resultant Matrix after subtraction:")
for row in result:
    print(row)

Output:

Resultant Matrix after subtraction:
[-8, -6, -4]
[-2, 0, 2]
[4, 6, 8]

• Time Complexity: O(m x n) where m is the number of rows and n is the number of columns.
• Space Complexity: O(m x n) because we need extra space to store the resultant matrix.

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 Change Keyboard Language in Windows 11.

Changing the keyboard language in Windows 11 can be essential for multilingual users or those who prefer a different input method. Here's a detailed guide on how to seamlessly switch and, if needed, remove keyboard languages on your Windows 11 system.

How To Change Keyboard Language in Windows.

In the initial setup of Windows 11, you'll be prompted to select your primary keyboard language, which will serve as the default setting for your computer. Nevertheless, the Windows Settings app provides a straightforward method to change this language repertoire by installing additional keyboard languages. This allows you to seamlessly switch between different languages.

Below are the steps that you need to follow to add another language to your keyboard:

Step 1: Open Windows Settings, Click on the Start menu, and select the gear-shaped icon for "Settings."

Step 2: In the Settings window, choose "Time & Language" from the left sidebar and select Language & Region.

Step 3: Under the "Preferred languages" section, click on "Add a language."

Step 4: Scroll through the list of available languages, select the one you want to add, and click "Next."

Step 5: If the language supports multiple keyboard layouts, choose the specific layout you prefer and click "Install."

Step 6: Once installed, you can set the newly added language as the default by clicking on it and selecting "Set as default."

Step 7: To change the keyboard language while typing, press the "Windows key + Spacebar" to cycle through the installed languages or you can click the language icon in the taskbar to choose the language you want to use.

Quick Tip: You can enable the Language Bar for quick access to language settings. In Language settings, go to "Advanced keyboard settings" and turn on the "Use the desktop language bar when it's available." (alert-success)

Quick Tip: Customize a shortcut key for easy switching between languages. In Language settings, go to "Advanced keyboard settings" and under "Switching input methods," click on "Change language bar hot keys." (alert-success)

How To Remove Keyboard Language in Windows.

If you've added a language you no longer require and want to change your language presence, removing it is a straightforward process. Below is a step-by-step guide on how to remove a keyboard language from your Windows 11 system.

 

Step 1: Click on the Start button or press the Windows key, and select the "Settings" icon (gear-shaped) on the left side of the Start menu.

Step 2: In the Settings menu, select "Time & Language" from the left sidebar and click on "Language & region".

Step 3: Scroll down to the section labeled Preferred languages and click on the language you want to remove. 

Step 4: Once you've selected the language, click on the three-dot options button that appears on the right and click on "Remove".

Step 5: A confirmation window will pop up asking if you want to remove the language. Click on "Remove" to confirm your action.

Quick Tip: If you're removing a language that was set as the default input, Windows will automatically switch to the next available language in the list. (alert-success)

Applications of Stack Data Structure.

The stack is a linear data structure that operates on the Last In, First Out (LIFO) principle, which means whatever data is inserted at last in the stack will come out first. Imagine it like a stack of plates where the last plate placed is the first one to be removed from the top. A stack can be visualized as a collection of elements stacked on top of each other, allowing two primary operations: push and pop.

When an element is pushed onto the stack, it becomes the new top element. Subsequent pushes place new element on the top, effectively forming a sequence. The pop operation removes the top element, revealing the next element in the stack. This behavior ensures that the most recently added item is always the first to be removed as the insertion and deletion of an element happens from the same end (top).  

Additionally, a stack supports other operations like peek, enabling us to view the top element without removing it, and methods to determine whether the stack is empty (isEmpty) and to know its current size (size)

A stack can be implemented using either an array or linked lists. Arrays offer simplicity and constant-time access to elements but have a fixed size, whereas linked lists provide flexibility in size but might involve more memory overhead due to their node structure. 

Read our detailed article on stack data structure to understand the implementation in detail.

List of Common Stack Operations:

• push(element): Adds an element to the top of the stack.
• pop(): Removes and returns the element from the top of the stack.
• peek() or top(): Returns the element at the top of the stack without removing it.
• isEmpty(): Checks if the stack is empty.
• size(): Determines the number of elements in the stack.

These operations are fundamental for managing and manipulating elements within a stack.

Stack Data Structure

Exploring Applications of Stack Data Structure.

Stack is a fundamental data structure in computer science, and finds its utility across a wide array of applications. 

1. Function Calls and Recursion: 

Stacks play a crucial role in managing function calls in programming languages. When a function is called, its context, including local variables and execution point, is pushed onto the call stack. As subsequent functions are called or when recursion occurs, new contexts are stacked on top. Upon returning from a function or completing recursion, the corresponding context is popped off the stack, allowing the program to resume execution from the previous point.

2. Expression Evaluation: 

In evaluating mathematical expressions, stacks are used to handle parentheses, operators, and operands. The infix-to-postfix conversion and postfix expression evaluation utilize stacks to ensure proper sequencing and precedence of operations.

3. Undo Mechanisms in Text Editors: 

Text editors often implement undo functionalities using stacks. Each edit operation is pushed onto the stack, allowing users to revert changes sequentially. When the undo command is invoked, the most recent edit is popped off the stack, effectively undoing the action.

4. Browser History in Web Browsing: 

The back/forward functionality in web browsers uses stacks. Visited web pages are pushed onto the history stack. Clicking the back button pops the last visited page, simulating the LIFO behavior of a stack.

5. Memory Management in Operating Systems: 

Operating systems utilize stacks for memory management. The system stack, responsible for managing function calls and storing local variables, follows the stack data structure model. Additionally, the call stack helps in managing memory allocation and deallocation through its LIFO nature.

Advantages of Stack Data Structure.

• Stacks are simple to implement and understand, making them easy to use in various applications.
• They offer efficient data retrieval and storage for specific operations like push, pop, and peek, with a constant time complexity O(1).
• Stacks support automatic memory management, especially in programming languages that use stack-based memory allocation and deallocation.
• Stacks are useful for reversing a sequence of elements efficiently due to their LIFO behavior.

Disadvantages of Stack Data Structure.

• Stack provides limited access to elements. Direct access to arbitrary elements, other than the top one, is not possible without sequentially popping off elements.
• If implemented using arrays, stacks have a fixed maximum capacity, making them prone to overflow issues when trying to add elements beyond the size limit.
• Stack is not a suitable data structure for performing certain operations like searching and sorting as it is difficult to change the order of stack elements.

Difference Between Stack and Queue Data Structure.

Data structures are fundamental components in computer science that organize and store data efficiently, enabling easy access, insertion, deletion, and manipulation of data elements. Two essential data structures in this domain are stacks and queues. In this article, we will understand the difference between them and which one we should use in which condition.

Stack Data Structure.

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle which means the insertion (push) and deletion (pop) happen only from one side of the stack which is the top. The last element pushed onto the stack is the first to be popped off. Let's understand stack data structure with one real-life example:

Example:

Consider a practical scenario: browsing the internet. Your browser's back button functionality perfectly illustrates how a stack operates. When you visit the web pages, each visited page becomes analogous to a plate added to a stack. The most recently visited page sits on top, while the older pages form a stack beneath it. 

As you navigate through these pages, you often use the back button to revisit previously viewed pages. This action mimics the operation of a stack: when you press 'back' the last page (the most recent addition to the stack) gets popped off the stack and becomes the current page.

Stack Data Structure

Queue Data Structure.

A Queue is a linear data structure that operates on the principle of First In, First Out (FIFO), which means the element that is inserted first in the queue will out first from the queue. Elements are added at the rear end (enqueue) and removed from the front (dequeue), making it efficient for scenarios where data needs to be processed in the order it was received. Let's understand the queue data structure with one real-life example:

Example:

Consider a printer queue handling multiple print jobs, as documents are sent for printing, they join the queue. The printer processes these documents in the order they arrive. Similarly, in programming, a queue is used to manage data based on their arrival sequence.

Queue Data Structure

Difference Between Stack and Queue.

Stacks	Queues
Stack is based on the Last In, First Out (LIFO) principle, elements that are inserted first will come out at last.	A Queue is based on the First In, First Out (FIFO) principle, elements that are inserted first in the queue will come out first.
In stack, the insertion operation is known as the "Push" operation.	A queue insertion operation is known as an "Enqueue" operation.
In stack deletion operation is known as "Pop" operation.	In queue deletion operation is known as "Dequeue" operation.
In stack, access to elements is limited to the top element (or the element at the end).	In a queue, access to elements is limited to the front element (or the element at the beginning)
In stack, data moves in and out from the same end.	In queue, data enters from the rear and exits from the front.
It can be implemented using arrays or linked lists.	It can be implemented using arrays or linked lists.
Example: Browser history, call stack in programming, backtracking algorithms.	Example: Print queue, task scheduling in operating systems, and breadth-first search algorithms.

Similarities of Stack and Queue Data Structure.

Although stack and queue are completely two different data structures still they share a few similarities:

• Both stacks and queues are linear data structures where elements are stored in a sequential manner.

• They support common operations like isEmpty to check if the structure is empty, size to determine the number of elements, and peek to view the top/front element without removing it.

• Both structures can be implemented using arrays or linked lists to manage and organize their elements.