


from __future__ import annotations

from collections.abc import Iterable
from dataclasses import dataclass
from typing import Any

class   A__							:
						UpperCAmelCase									=  ("_front", "_back", "_len")

						@dataclass
						class   A__							:
												UpperCAmelCase									=  None
												UpperCAmelCase									=  None
												UpperCAmelCase									=  None

						class   A__							:
												UpperCAmelCase									=  ("_cur",)




												def __init__(				self    :					int ,			_a    :					Deque._Node | None     )							->   None:


																"""simple docstring"""





																_SCREAMING_SNAKE_CASE	     =cur




												def __iter__(				self    :					Optional[Any]     )							->   Deque._Iterator:


																"""simple docstring"""





																return self




												def 							__UpperCamelCase (				self    :					Union[str, Any]     )							->   Any:


																"""simple docstring"""





																if self._cur is None:
																				# finished iterating
																				raise StopIteration
																_SCREAMING_SNAKE_CASE	     =self._cur.val
																_SCREAMING_SNAKE_CASE	     =self._cur.next_node

																return val




						def __init__(				self    :					Union[str, Any] ,			_a    :					Iterable[Any] | None = None     )							->   None:


										"""simple docstring"""





										_SCREAMING_SNAKE_CASE	     =None
										_SCREAMING_SNAKE_CASE	     =None
										_SCREAMING_SNAKE_CASE	     =0

										if iterable is not None:
														# append every value to the deque
														for val in iterable:
																		self.append(_UpperCamelCase     )




						def 							__UpperCamelCase (				self    :					Optional[Any] ,			_a    :					Any     )							->   None:


										"""simple docstring"""





										_SCREAMING_SNAKE_CASE	     =self._Node(_UpperCamelCase ,			_UpperCamelCase ,			_UpperCamelCase     )
										if self.is_empty():
														# front = back
														_SCREAMING_SNAKE_CASE	     =_SCREAMING_SNAKE_CASE	     =node
														_SCREAMING_SNAKE_CASE	     =1
										else:
														# connect nodes
														_SCREAMING_SNAKE_CASE	     =node
														_SCREAMING_SNAKE_CASE	     =self._back
														_SCREAMING_SNAKE_CASE	     =node  # assign new back to the new node

														self._len += 1

														# make sure there were no errors
														assert not self.is_empty(), "Error on appending value."




						def 							__UpperCamelCase (				self    :					Any ,			_a    :					Any     )							->   None:


										"""simple docstring"""





										_SCREAMING_SNAKE_CASE	     =self._Node(_UpperCamelCase ,			_UpperCamelCase ,			_UpperCamelCase     )
										if self.is_empty():
														# front = back
														_SCREAMING_SNAKE_CASE	     =_SCREAMING_SNAKE_CASE	     =node
														_SCREAMING_SNAKE_CASE	     =1
										else:
														# connect nodes
														_SCREAMING_SNAKE_CASE	     =self._front
														_SCREAMING_SNAKE_CASE	     =node
														_SCREAMING_SNAKE_CASE	     =node  # assign new front to the new node

														self._len += 1

														# make sure there were no errors
														assert not self.is_empty(), "Error on appending value."




						def 							__UpperCamelCase (				self    :					List[Any] ,			_a    :					Iterable[Any]     )							->   None:


										"""simple docstring"""





										for val in iterable:
														self.append(_UpperCamelCase     )




						def 							__UpperCamelCase (				self    :					str ,			_a    :					Iterable[Any]     )							->   None:


										"""simple docstring"""





										for val in iterable:
														self.appendleft(_UpperCamelCase     )




						def 							__UpperCamelCase (				self    :					str     )							->   Any:


										"""simple docstring"""





										assert not self.is_empty(), "Deque is empty."

										_SCREAMING_SNAKE_CASE	     =self._back
										_SCREAMING_SNAKE_CASE	     =self._back.prev_node  # set new back
										# drop the last node - python will deallocate memory automatically
										_SCREAMING_SNAKE_CASE	     =None

										self._len -= 1

										return topop.val




						def 							__UpperCamelCase (				self    :					Union[str, Any]     )							->   Any:


										"""simple docstring"""





										assert not self.is_empty(), "Deque is empty."

										_SCREAMING_SNAKE_CASE	     =self._front
										_SCREAMING_SNAKE_CASE	     =self._front.next_node  # set new front and drop the first node
										_SCREAMING_SNAKE_CASE	     =None

										self._len -= 1

										return topop.val




						def 							__UpperCamelCase (				self    :					Tuple     )							->   bool:


										"""simple docstring"""





										return self._front is None




						def __len__(				self    :					Optional[int]     )							->   int:


										"""simple docstring"""





										return self._len




						def __eq__(				self    :					Union[str, Any] ,			_a    :					object     )							->   bool:


										"""simple docstring"""





										if not isinstance(_UpperCamelCase ,			_UpperCamelCase     ):
														return NotImplemented

										_SCREAMING_SNAKE_CASE	     =self._front
										_SCREAMING_SNAKE_CASE	     =other._front

										# if the length of the dequeues are not the same, they are not equal
										if len(self     ) != len(_UpperCamelCase     ):
														return False

										while me is not None and oth is not None:
														# compare every value
														if me.val != oth.val:
																		return False
														_SCREAMING_SNAKE_CASE	     =me.next_node
														_SCREAMING_SNAKE_CASE	     =oth.next_node

										return True




						def __iter__(				self    :					Optional[Any]     )							->   Deque._Iterator:


										"""simple docstring"""





										return Deque._Iterator(self._front     )




						def __repr__(				self    :					Optional[Any]     )							->   str:


										"""simple docstring"""





										_SCREAMING_SNAKE_CASE	     =[]
										_SCREAMING_SNAKE_CASE	     =self._front
										while aux is not None:
														# append the values in a list to display
														values_list.append(aux.val     )
														_SCREAMING_SNAKE_CASE	     =aux.next_node

										return f"[{', '.join(repr(_UpperCamelCase     ) for val in values_list     )}]"


if __name__ == "__main__":
							import doctest

							doctest.testmod()





from __future__ import annotations

from typing import Generic, TypeVar

lowerCamelCase_  						=   TypeVar("T")
class       __a					( Generic[T]     ):


     """simple docstring"""


     def __init__(	self			: int				,_UpperCamelCase			: T						)		->   str:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=data  # Assign data
         SCREAMING_SNAKE_CASE__								=None  # Initialize next as null
         SCREAMING_SNAKE_CASE__								=None  # Initialize prev as null






class       __a					( Generic[T]     ):


     """simple docstring"""


     def __init__(	self			: Tuple						)		->   None:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=None




     def   __A				(	self			: Dict				,_UpperCamelCase			: T						)		->   None:


         '''simple docstring'''





         if self.head is None:
             SCREAMING_SNAKE_CASE__								=Node(_UpperCamelCase						)
         else:
             SCREAMING_SNAKE_CASE__								=Node(_UpperCamelCase						)
             SCREAMING_SNAKE_CASE__								=new_node
             SCREAMING_SNAKE_CASE__								=self.head
             SCREAMING_SNAKE_CASE__								=None
             SCREAMING_SNAKE_CASE__								=new_node




     def   __A				(	self			: List[str]						)		->   T | None:


         '''simple docstring'''





         if self.head is None:
             return None
         else:
             assert self.head is not None
             SCREAMING_SNAKE_CASE__								=self.head.data
             SCREAMING_SNAKE_CASE__								=self.head.next
             if self.head is not None:
                 SCREAMING_SNAKE_CASE__								=None
             return temp




     def   __A				(	self			: List[str]						)		->   T | None:


         '''simple docstring'''





         return self.head.data if self.head is not None else None




     def __len__(	self			: Optional[int]						)		->   int:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=self.head
         SCREAMING_SNAKE_CASE__								=0
         while temp is not None:
             count += 1
             SCREAMING_SNAKE_CASE__								=temp.next
         return count




     def   __A				(	self			: List[Any]						)		->   bool:


         '''simple docstring'''





         return self.head is None




     def   __A				(	self			: int						)		->   None:


         '''simple docstring'''





         print("""stack elements are:"""						)
         SCREAMING_SNAKE_CASE__								=self.head
         while temp is not None:
             print(temp.data				,end="""->"""						)
             SCREAMING_SNAKE_CASE__								=temp.next


# Code execution starts here
if __name__ == "__main__":
    # Start with the empty stack
    lowerCamelCase_  						=   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())






