Stack and it's Implementation in day to day Life!

 

Peek() Applications!

 

- Guided By Mrs. Sampada Kulkarni

This time let us continue the journey of exploring more into them and finding some new claim.

1. Stack :

Here Firstly as mentioned in the first blog , Stack is Linear & Static data structure. A Stack uses a basic principle of LAST-IN FIRST OUT (LIFO). It can be implemented using both the Array and Linked-List. There are two types of Stack :

a. Implicit Stack :

An Implicit Stack is used by the system to make the process of compilation, debugging , Storage Management, CPU processing and many more…

One not in these is → use of stack in bash scripting. An very basic need of stack in bash scripting.

Firstly let us see the problem first arise , which lead to this type of usage.

There is one Folder named “test” and another “dsatest” in my device.

NOTE : dsatest is inside the folder ls which is in DSA folder. (i.e. DSA/ls/dsatest)

Now let us understand the commands I used here :

Commands	Description
ls	Showing the contents of the current directory.
cd	Change the current directory to the home directory.
cd <PATH>	Change the current directory to the specified path.
cd -	Change the current directory to the previous directory.

Now the problem statement is ; “cd -” command only revert back to the previous but not the history of the commands we used previously.

This problem is solved using stack very easily ( i.e. LIFO principle).

There are two more commands used for implicit Stack :

Commands	Description
pushd	Adds the path to stack and change the directory to the pushed path.
popd	Removes the path from the stack and change the directory to the popped path.

If there is no path in the stack then it shows an error : stack is empty. Hence Solved.

One more application is → Arithmetic and Logical Unit (ALU ) using stack for Evaluation and Conversion of the Expression as given below. It uses Implicit stack which we can implement explicitly.

b. Explicit Stack :

Explicit Stack is when the programmer itself create a structure using linked list or an array implementing stack.

This stack can be created either in any type of programming language or explicitly as a structure for the theoretical concepts.

eg. in C++ programming language.

The above example shows that stack implemented using Linked-List having :

Data in the type of character and next field as the pointer to the next element in the linked-list

Let us take and example of Converting infix expression A * ( B * C + D *E ) + F

                         image courtesy by : https://www.techiedelight.com/wp-content/uploads/Infix-To-Postfix.png

Similarly is done with the Conversion of Infix to Prefix

Now the expression is A + B — C * D + (E^F)

Hence the Conversion is as below :

https://www.techiedelight.com/wp-content/uploads/Infix-To-Postfix.png

                        image courtesy by : https://miro.medium.com/v2/resize:fit:720/format:webp/1*_Intvr_huZXax2C4alO9hg.png

Now reverse it ..

           

                        image courtesy by : https://miro.medium.com/v2/resize:fit:640/format:webp/1*WAqUdBXblc0ZAc0Of4iSWg.png

This is how it is done By using stack.

Data Structure and Algorithm

No DSA? (->nullptr) Ahead! 

-Guided by- Mrs. Sampada A. Kulkarni    

Did you open the IDE to start implementing a data structure only to find out that it's just a "Hello World!" program? I did, too. Let's populate our array with some actual data structures! 

A data structure is a way of organizing a collection of meaningful information. This organization can involve creating objects, performing operations on those objects, allocating the objects, and much more... 

ARRAY : 

Non-primitive, linear, sequential, and static data structure. You might be wondering how to remember all these classifications.

    

An array is a Data structure consisting of a collection of elements that can be identified by an index. An array's index starts from 0 to n-1, where n is the length of the array. An array is homogenous(i.e. stores only one kind of data).

Exploring beyond the limits has been my best experience until now. Let's do the same.

-1 index Of Array

 

You may have heard of the array's -1 index. It is not accessible. Do you know how it is used in programming, especially in DSA?

-1 Index Can be used as follows when traversing the array or searching for some element. :

1. The end of an array.
2. A null value.
3. A special marker for an algorithm.

Understanding the -1 index concept is crucial in various algorithms and data structures, such as: 

Binary Search: -1 can indicate the absence of a target element.

Dynamic Programming: -1 can represent an invalid state.

Graph Algorithms: -1 can mark the absence of a connection.

Remember, there's no -1 position in an array, but the -1 index can hold significant meaning in the right context!

LINKED LIST :

It is Non-Primitive, Linear, Non-Sequential and Dynamic. Every element contains two parts: the data and the address of the next component.

In programming language, we call the second part the pointer towards the next element. Hence, the arrow is the representation of this pointer.

A node in a linked list typically consists of two parts:
1. Data: The actual value or information stored in the node.
2. Next Pointer (or Reference): A pointer or reference to the next node in the list.

A null pointer is given to the last element of the list.
This allows for efficient insertion and deletion of nodes at any position in the list.
Have you ever wondered if there's a way to create a linked list that never ends? A list that goes on forever, without a terminating node? Sounds like a paradox, right? But, bear with me, and let's explore this mind-bending concept.

Never Ending Linked List :

In theory, a never-ending linked list is possible. Imagine a circularly linked list, where the last node points back to the first node, creating a loop. This way, there is no terminating node, and the list appears endless.

Image courtesy by: https://quescol.com/wp-content/uploads/2021/02/Circular-Linked-List.png

These two data structures are used to create many big and complex data structures like .. Stack, Queue, Tree and Graph.

Combining Arrays and Linked Lists:

1. Enables creation of complex data structures like stacks, queues, trees, and graphs.

2. Binary search trees can be implemented using linked lists for efficient searching, insertion, and deletion.

3. Graphs can be represented using adjacency lists (linked lists of edges).

And that's a wrap, folks! Arrays and linked lists are just the beginning of our DSA journey. By mastering these fundamental data structures, you'll unlock the secrets of efficient data organization and manipulation.