Linked Stack :- In linked list implementation of stack, the nodes are maintained non-

contiguously in the memory. Each node contains a pointer to its immediate successor node in
the stack. Stack is said to be overflown if the space left in the memory heap is not enough to
create a node.

Stack :- Stack is a linear data structure which follows a particular order in which the operations
are performed. The stack consist of a bounded bottom and all the operations are carried out on
the top position.
A stack is a data structure that allows insertion and deletion operation in a LIFO (last-in-first-
out) manner. The memory operations, therefore, are regulated in a particular manner. When
an element is added to the stack, it occupies the top position. When it comes to removal
operation, the most recent element in terms of being inserted into the stack gets first removed,
hence the LIFO characteristic. This is similar to a stack of saucers or tiles, kept one over
another. We keep going on placing saucers on over another, and while removing, the most
recently added one is removed first.

 Array: Its a random-access  container, meaning any element of this container can be

accessed instantly.
 Linked List: It's a sequential-access container, meaning that elements of this data
structure can only be accessed sequentially.
→ Following a similar definition, a stack is a container where only the top element can be
accessed or operated upon.

Real life example of stack is stack of books.

 In a stack of books, you can only see the top book.

 If you want to access any other book, you would first need to remove the books on
top of it.
 The bottom-most book in the stack was put first and can only be removed at the last
after all books on top of it have been removed.

Push Operation

Push operation refers to inserting an element in the stack. Since there’s only one
position at which the new element can be inserted- Top of the stack, the new
element is inserted at the top of the stack.

Pop Opertion

Pop operation refers to the removal of an element. Again, since we only have access
to the element at the top of the stack, there’s only one element that we can remove.
We just remove the top of the stack.

PEEK Operation
Peek operation allows the user to see the element on the top of the stack. The stack is not
modified in any manner in this operation.

isEmpty: Check if stack is empty or not

To prevent performing operations on an empty stack, the programmer is required to
internally maintain the size of the stack which will be updated during push and pop
operations accordingly. isEmpty() conventionally returns a boolean value: True if size is 0,
else False. Initially, when the stack is created, the stack is empty that’s why we initialize
top variable to -1. Hence, when top == -1 then the stack is empty.

isFull: Check if stack is full or not. A stack is said to be full when associated array is
completely filled up. Whenever stack is full top points to the last element i.e top ==
Maxsize-1.

Stack Implementation.
You should remember one very important thing though →All operations in the stack must be
of O(1) time complexity.
We shall be implementing stack in two different ways by changing the underlying
container: Array and Linked List.

1. Array Implementation
 An array is one of the simplest containers offering random access to users based on
indexes. To access the element at top position we take index variable as top.
 Initially, when the stack is created, stack is empty that’s why we initialize top
variable to -1. Hence, when top == -1 then the stack is empty.
 When top == Maxsize – 1 then the stack is full.

int stack[10]
int top = -1
Here, 10 is a pre-defined capacity of the stack. We can throw a stack overflow error if a
user tries to exceed this capacity.

★ The default value for the top is -1, denoting that the stack is empty.

→Now, we need to implement the operations that we generally perform on stacks.

PUSH Operation
The operation to insert an element in a data structure is called Push operation. When we
insert an element into a stack, it occupies the bottom-most position, as an object pushed into a
pit. The next element inserted goes over the top of the previous element, and likewise, the
insertion of all elements happens. As each time, the insertion operation resembles pushing an
element into the stack, and the operation is termed as “Push operation”.
Algorithm for Push Operation

What changes are made to the stack when a new element is pushed?

 A new element is inserted on top

 The value of top increases by 1

▹ What if the stack is filled to its capacity?

We shall check if the stack if full before inserting a new element and throw an error if it is.

Now, let us implement this simply

Push Function
void push(stack*s,int element)
{
if ( is Full(s))
printf(“\nStack is full.”);
else
{
s->top++;
s->home[s -> top] = element;
}
}

POP Operation
Pop operation refers to the removal of an element. Again, since we only have access to the
element at the top of the stack, there’s only one element that we can remove. We just
remove the top of the stack. 

Note: We can also choose to return the value of the popped element back, its completely at
the choice of the programmer to implement this.

What changes are made to the stack internally for a pop operation?

 The top element is removed

 The value of top is decreased by 1

Let’s try implementing it now

int pop(stack*s)
{
int element = -9999;
if ( isEmpty(s))
print( "Stack is empty." );
else
{
element = s-> home[s->top];
s->top--;
}
return element;
}

Program for Implementing stack using array.

2. Linked List Implementation

Before implementing stack with a linked list, let us first try to visualize a stack as a linked
list. There are two ends of a linked list: head and tail.

Which end do you think should represent the top of the stack? (Think!)

The top of the stack should be represented by  head  because otherwise, we would not be
able to implement the operations of the stack in O(1) time complexity.
Let us assume that we have used class for linked list

class ListNode{
int val
ListNode next
}
What should an empty stack look like if implemented with a linked list? Ans: Its head will
point to NULL

ListNode head = NULL

Is there any benefit to implementing a stack as linked list compared to arrays? Ans: We do
not need to mention the size of the stack beforehand.
→ Although, if you want to implement a limit to prevent excess use, you may need to
encapsulate the class ListNode inside some other class along with a data member capacity.

class Stack{
int capacity
class ListNode{
int val
ListNode next
}
}
We shall be using just using class ListNode below for simplicity.

→Let us move towards stack operations

PUSH Operation
The same properties hold as above with an added benefit that we need not worry about the
stack being full

void push(int item)

{
ListNode temp = ListNode(item)
temp.next = head
head = temp
}
POP Operation
Properties of linked list relaxed us from checking if the stack is full in push operation. Do
they provide any relaxation for exceptions in pop operation? No. We still need to check if
the stack is empty.

Since the top is represented by the head in this implementation. How do we delete the first
element in a linked list?

Simple, we make the second element as the head.

void pop()
{
if ( head == NULL )
print ( "Stack is empty!" )
else
 head = head.next
}
★ You may be required to deallocate the popped node to avoid memory leak according to
your programming language's conventions.

Peek and isEmpty Operation

The implementation of these two operations is pretty simple and straight-forward in the
linked list too.

int peek()
{
if ( head == NULL )
{
print ( "Stack is empty!" )
return -1
}
else
return head.val
}
bool isEmpty()
{
if ( head == NULL )
return True
else
return False
}

Augmentations in Stack
You can augment the stack data structure according to your needs. You can implement
some extra operations like:-

 isFull(): tells you if the stack if filled to its capacity

 The pop operation could return the element being deleted
★ A quite interesting augmentation that has been asked in many interviews asks you to
implement a MinStack which holds all properties of a regular stack but also returns the
minimum value in the stack. Since all stack operations are expected to be executed in
constant time, you need to return the minimum element in the stack in O(1) time
complexity.
How does Stack work in Data Structure?
A stack is a very simple data structure, and there are necessarily two operations associated
with stack, which are Push and Pop. The working of the stack as a data structure can be
understood through these operations.

1.Insertion 0peration

The operation to insert an element in a data structure is called Push operation. When we
insert an element into a stack, it occupies the bottom-most position, as an object pushed into a
pit. The next element inserted goes over the top of the previous element, and likewise, the
insertion of all elements happens. As each time, the insertion operation resembles pushing an
element into the stack, and the operation is termed as “Push operation”.