Implementation of stack using linked list

 Linked Lists in Stack Implementation

• Linked lists offer a dynamic memory allocation alternative to arrays.
• Despite different data structures, time complexities for stack operations remain consistent.
• Nodes are non-contiguously maintained in memory, each with a pointer to its successor node.
• Stack overflow occurs when insufficient memory heap space is available for node creation.
• Singly linked lists align standard linked list operations with stack operations, adhering to the Last In, First Out (LIFO) principle.
• Top variable guides operations like Pop, Push, Peek, and Display.
• Unlike arrays, linked lists offer flexibility, eliminating risk of overflow.

 

 Stack Implementation vs. Array vs. Linked List

• Array-based stacks work for a fixed number of data values, making them unsuitable for unknown data sizes.
•  Linked list stacks can work for unlimited data values, eliminating the need to fix the initial size.
• Linked list stacks insert new elements as 'top' elements, pointing to the 'top' node.
• To remove an element, move 'top' to its previous node in the list.
• The first element's next field must always be NULL.

Operations performed on Stack

Following operations can be performed on a stack:

• push(): It inserts an element to the top of the stack. It takes O(1) time, as each node is inserted at the head/top of the linked list.
• pop(): It removes an element from the top of the stack. It takes O(1) time, as the top always points to the newly inserted node.
• peek(): It returns the top element of the stack.
• size(): It returns the size of the stack, i.e., the total number of items in a stack.
• isEmpty(): Returns a boolean value. It returns true if the stack is empty. Else, it returns false.

 Before performing all the above operations, lets first define node structure

• Step 1 - Include all the header files which are used in the program. And declare all the user defined functions.
• Step 2 - Define a 'Node' structure with two members data and next.
• Step 3 - Define a Node pointer 'top' and set it to NULL.
• Step 4 - Implement the main method by displaying Menu with list of operations and make suitable function calls in the main method.

push(value) - Inserting an element into the Stack

We can use the following steps to insert a new node into the stack...

• Step 1 - Create a newNode with given value.
• Step 2 - Check whether stack is Empty (top == NULL)
• Step 3 - If it is Empty, then set newNode → next = NULL.
• Step 4 - If it is Not Empty, then set newNode → next = top.
• Step 5 - Finally, set top = newNode.

pop() - Deleting an Element from a Stack

We can use the following steps to delete a node from the stack...

• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the function
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
• Step 4 - Then set 'top = top → next'.
• Step 5 - Finally, delete 'temp'. (free(temp)).

display() - Displaying stack of elements

We can use the following steps to display the elements (nodes) of a stack...

• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
• Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until temp reaches to the first node in the stack. (temp → next != NULL).
• Step 5 - Finally! Display 'temp → data ---> NULL'.

NumPy Joining Array

In NumPy, joining arrays refers to combining the elements of multiple arrays into a single new array. There are two main ways to achieve this:

1. Concatenation: This involves joining arrays along a specified axis. The most common function for concatenation is np.concatenate. It takes a sequence of arrays as its first argument and optionally the axis along which to join them. By default, concatenation happens along axis 0 (rows for 2D arrays).

Here's an example of concatenating two arrays:

 

2. Stacking: This is similar to concatenation but with a key difference. Stacking creates a new axis along which the arrays are joined. NumPy provides convenience functions for stacking along specific axes:

• np.hstack: Stacks arrays horizontally (column-wise) by creating a new axis 1.
• np.vstack: Stacks arrays vertically (row-wise) by creating a new axis 0.
• np.dstack: Stacks arrays along depth (useful for 3D arrays) by creating a new axis 2.

Here are examples

NumPy Array Iterating

You can go through NumPy arrays in two main ways:

1. Using a for loop: This is the easiest way to go through each item in a NumPy collection. You can just do a loop over the array, and each time you do that, you'll be able to reach the current element.

2. Indexing with a for loop: You can also use a for loop and indexing to go through the parts of a NumPy array. This method works well when you need to get both the number and the index of the current element.

Both methods go through the elements of the array in row-major order, which is the usual way to order things in C. This means that the elements are gone through in a way that first fills up one row of the array and then goes on to the next row.

Besides these simple ways, NumPy also has the nditer function for more complex iteration. There are many useful tools like nditer that give you more freedom when iterating over arrays.

nditer is the way to go if you need more advanced features for going through NumPy collections. But a simple for loop, with or without numbering, will do for most simple situations.