<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Data Structure
list
stack
queue
tree
etc...
Linked List
|task|Linked List|Array|
|
Step1:  Doubly Linked List
Step2:  Stack
Step3:  ```
Input Stream
<ASSISTANT_TASK:>
Python Code:
# Node of a Singly Linked List
class Node:
    # constructor
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next
    
    # method of getter, setter for data
    def setData(self, data):
        self.data = data
    def getData(self):
        return self.data
    
    # method of getter, setter for next
    def setNext(self, next):
        self.next = next
    def getNext(self):
        return self.next
    
    # returns true if the node points to another node
    def hasNext(self):
        return self.next != None
        
# implement Singly Linked List
class SinglyLinkedList:
    def __init__(self, node=None):
        self.head = node
    
    def setHead(self, node):
        self.head = node
    def getHead(self):
        return self.head
    # returns length of list
    ## Time Complexity: O(n), for scanning the list of size n.
    ## Space COmplexity: O(1), for creating a temporary vaiable.
    def listLength(self):
        current = self.head
        count = 0
        
        while current != None:
            count += 1
            current = current.getNext()
            
        return count
    
    # method to insert
    ## - at beginning
    ## - at ending
    ## - at specific position
    def insertAtBeg(self, data):
        newNode = Node(data)
        length = self.listLength()
        
        if length == 0:
            self.setHead(newNode)
        else :
            newNode.setNext(self.getHead())
            self.setHead(newNode)
        
        return self
    
    def insertAtEnd(self, data):
        newNode = Node(data)
        current = self.getHead()
        
        while current.getNext() != None:
            current = current.getNext()
        
        current.setNext(newNode)
        return self
    def insertAtPos(self, data, pos):
        length = self.listLength()
        if pos > length or pos < 0:
            return None
        else:
            if pos == 0:
                self.insertAtBeg(data)
            else:
                newNode = Node(data)
                count = 0
                current = self.getHead()
                while count < pos - 1:
                    current = current.getNext()
                    count += 1
                newNode.setNext(current.getNext())
                current.setNext(newNode)
                return self
        
    # method to delete
    ## - at beginning
    ## - at ending
    ## - at specific position
    def deleteAtBeg(self):
        length = self.listLength()
        if length == 0:
            return None
        else :
            self.setHead(self.getHead().getNext())
            return self
    def deleteAtEnd(self):
        length = self.listLength()
        if length == 0:
            return None
        else :
            current = self.getHead()
            while current.getNext() != None:
                prev = current
                current = current.getNext()
            prev.setNext(None)
            return self
    def deleteAtPos(self, pos):
        length = self.listLength()
        if pos > length or pos < 0:
            return None
        else:
            count = 0
            current = self.getHead()
            while count < pos - 1:
                count += 1
                current = current.getNext()
            current.setNext(current.getNext().getNext())
            return self
        
    def show(self):
        if self.listLength() == 0:
            return "Null"
        current = self.getHead()
        acc = str(current.getData())
        while current.getNext() != None:
            current = current.getNext()
            acc = acc + "::" + str(current.getData())
        return acc+"::Null"
ls = SinglyLinkedList(Node(1))
print(ls.insertAtBeg(3).show())
print(ls.insertAtBeg(5).show())
print(ls.insertAtEnd(8).show())
print(ls.insertAtPos(12, 2).show())
print(ls.deleteAtPos(3).show())
print(ls.deleteAtEnd().show())
print(ls.deleteAtBeg().show())
Explanation: Data Structure
list
stack
queue
tree
etc...
Linked List
|task|Linked List|Array|
|:---|:----------|-----|
|indexing|O(n)|O(1)|
|insertion/deletion at beginning|O(1)|O(n)|
|insertion/deletion at ending|O(n)|O(1)|
|insertion/deletion at middle|O(n)|O(n)|
Singly Linked List
End of explanation
# Node of a Doubly Linked List
class Node:
    def __init__(self, data=None, next=None, prev=None):
        self.data = data
        self.next = next
        self.prev = prev
  
    def setNext(self, next):
        self.next = next
    def getNext(self):
        return self.next
    def setPrev(self, prev):
        self.prev = prev
    def getPrev(self):
        return self.prev
    def setData(self, data):
        self.data = data
    def getData(self):
        return self.data
class DSShow:
    def show(self):
        return self.list.show()
Explanation: Doubly Linked List
End of explanation
class Stack(DSShow):
    def __init__(self):
        self.list = SinglyLinkedList()
        self.length = 0
        
    def top(self):
        return self.list.getHead()
        
    def push(self, data):
        self.list.insertAtBeg(data)
        self.length += 1
        return self
    
    def pop(self):
        if self.length > 0:
            self.length -= 1
            top = self.top()
            self.list.deleteAtBeg()
            return top
        else:
            return None
stk = Stack()
stk.push(3)
stk.push(4)
stk.show()
stk.pop()
stk.show()
Explanation: Stack
End of explanation
class Queue(DSShow):
    def __init__(self):
        self.list = SinglyLinkedList()
        self.length = 0
        
    def enqueue(self):
        pass
    def dequeue(self):
        pass
    
Explanation: ```
Input Stream: 1, 2, 3, 3, 2, 1, 3
Output Stack State: 3::1::2::3::2::Null
```
End of explanation
<END_TASK>