Stack

A stack is an abstract data type that follows the Last-In-First-Out (LIFO) . It is a collection of elements with two primary operations: "push" and "pop".The "push" operation adds an element to the top of the stack, while the "pop" operation removes and returns the topmost element from the stack. The stack can be visualized as a vertical structure, much like a stack of books. The element added last (most recently) is positioned at the top, and the element added first (earlier) is at the bottom. As new elements are added, they stack up on top, and when elements are removed, they are taken from the top.

Basic operations are performed in the stack are:

1. Push: It adds an item in the stack. If the stack is full, then the stack is said to be in Overflow condition.

2. Pop: It deletes an item from the stack. The items are popped out in the reverse order in which they were pushed in. If the stack is empty, then it is said to be in Underflow condition i.e no more items can be deleted.

3. Peek or Top: It returns the top element of the stack.

4. isEmpty: It returns true if stack is empty, otherwise false.

Linked Lists

A linked list is a linear data structure, but unlike arrays the elements are not stored at contiguous memory locations, the elements in a linked list are linked to each other using pointers. It consists of nodes where, each node contains a data field and a link to the next node. A stack can be represented using different data structures, but the most common choices are an array or a linked list. Linked list-based representation: In this representation, a linked list is used to implement the stack. Each node in the linked list represents an element of the stack and contains the actual data and a reference to the next node. The top of the stack is represented by the head of the linked list. The linked list-based representation allows for dynamic resizing and does not have a fixed maximum size. It can grow or shrink as needed. However, accessing elements in a linked list requires following the references from the head to the desired node, which takes O(n) time in the worst case

Algorithm for Implementing a Stack using Linked List

1. PUSH() Operation:

Step 1: Start

Step 2: Create a node new and declare variable top

Step 3: Set new data part to be Null // The first node is created, having null value and top pointing to it

Step 4: Read the node to be inserted.

Step 5: Check if the node is Null, then print "Insufficient Memory"

Step 6: If node is not Null, assign the item to data part of new and assign top to link part of new and also point stack head to new.

2. POP() Operation:

Step 1: Start

Step 2: Check if the top is Null, then print "Stack Underflow."

Step 3: If top is not Null, assign the top's link part to ptr and assign ptr to stack_head's link part.

Step 4: Stop

3. PEEK() Operation:

Step 1: Start

Step 2: Print or store the node pointed by top variable

Step 3: Stop

Note:

In the above Algorithium
1. We first create a node with value Null.
2. Then when we have to push an element new we check if new is not null otherwise insertion cannot be done. We then feed Item into data part of new and assign top to its link and top is updated to the new value. And thus, an element is inserted.
3. For popping we check first if the item is not null, otherwise stack is empty i.e underflow condition. The pointer is then made to point the next element and st_head link is assigned to the pointer's value. This eliminates the element from the link list. Thus, popping the element
4. Peek value is stored or printed by returning node at which top is pointing
5. Stop