






"""simple docstring"""


def 					a			(  UpperCamelCase_				:					int		)	->		list:
 __A						:							Dict      =						len(_UpperCAmelCase		)

 # Set the gap value to be decreased by a factor of 1.3
 # after each iteration
 __A						:							Union[str, Any]      =						1.3

 # Continue sorting until the gap is 1
 while gap > 1:
  # Decrease the gap value
  __A						:							Union[str, Any]      =						int(gap / shrink		)

  # Sort the elements using insertion sort
  for i in range(_UpperCAmelCase  ,						len(_UpperCAmelCase		)		):
   __A						:							Any      =						collection[i]
   __A						:							str      =						i
   while j >= gap and collection[j - gap] > temp:
    __A						:							List[str]      =						collection[j - gap]
    j -= gap
   __A						:							Optional[int]      =						temp

 return collection


if __name__ == "__main__":
   import doctest

   doctest.testmod()










"""simple docstring"""




from __future__ import annotations

from typing import Generic, TypeVar

_UpperCamelCase:					str     				=	TypeVar('T')


class 	a__		(    Generic[T]  ):


   def __init__(				self   :				Optional[int],  lowerCAmelCase   :				T      )     ->							List[Any]:
         lowercase	:   Optional[int]											= data  # Assign data
         lowercase	:   Node[T] | None											= None  # Initialize next as null
         lowercase	:   Node[T] | None											= None  # Initialize prev as null




class 	a__		(    Generic[T]  ):


   def __init__(				self   :				Optional[int]      )     ->							None:
         lowercase	:   Node[T] | None											= None


   def 							lowercase					(				self   :				Any,  lowerCAmelCase   :				T      )     ->							None:
         if self.head is None:
               lowercase	:   Tuple											= Node(lowerCAmelCase      )
         else:
               lowercase	:   Dict											= Node(lowerCAmelCase      )
               lowercase	:   str											= new_node
               lowercase	:   int											= self.head
               lowercase	:   List[str]											= None
               lowercase	:   List[str]											= new_node


   def 							lowercase					(				self   :				Dict      )     ->							T | None:
         if self.head is None:
               return None
         else:
               assert self.head is not None
               lowercase	:   Optional[int]											= self.head.data
               lowercase	:   Any											= self.head.next
               if self.head is not None:
                     lowercase	:   Optional[Any]											= None
               return temp


   def 							lowercase					(				self   :				List[Any]      )     ->							T | None:
         return self.head.data if self.head is not None else None


   def __len__(				self   :				int      )     ->							int:
         lowercase	:   Any											= self.head
         lowercase	:   List[Any]											= 0
         while temp is not None:
               count += 1
               lowercase	:   Any											= temp.next
         return count


   def 							lowercase					(				self   :				List[Any]      )     ->							bool:
         return self.head is None






   def 							lowercase					(				self   :				Optional[int]      )     ->							None:
         print('stack elements are:'      )
         lowercase	:   Optional[int]											= self.head
         while temp is not None:
               print(temp.data,  end='->'      )
               lowercase	:   List[str]											= temp.next


# Code execution starts here
if __name__ == "__main__":
     # Start with the empty stack
     _UpperCamelCase:					Stack[int]     				=	Stack()

     # Insert 4 at the beginning. So stack becomes 4->None
     print('Stack operations using Doubly LinkedList')
     stack.push(4)

     # Insert 5 at the beginning. So stack becomes 4->5->None
     stack.push(5)

     # Insert 6 at the beginning. So stack becomes 4->5->6->None
     stack.push(6)

     # Insert 7 at the beginning. So stack becomes 4->5->6->7->None
     stack.push(7)

     # Print the stack
     stack.print_stack()

     # Print the top element
     print('\nTop element is ', stack.top())

     # Print the stack size
     print('Size of the stack is ', len(stack))

     # pop the top element
     stack.pop()

     # pop the top element
     stack.pop()

     # two elements have now been popped off
     stack.print_stack()

     # Print True if the stack is empty else False
     print('\nstack is empty:', stack.is_empty())
