1. 栈

1.1用数组实现一个顺序栈

class ArrayStack(object):
    def __init__(self,n):
        self.items = []
        self.n=n
        self.count=len(self.items)
    
    #入栈操作
    def push_array(self,item):
        #数组空间不够了，直接返回 false，入栈失败。
        if (self.count == self.n): 
            return False
        #print(self.count)
        #将 item 放到下标为 count 的位置，并且 count 加一
        self.items.append(item)
        return True
  
    #出栈操作
    def pop_array(self):
        #栈为空，则直接返回 None
        if (self.count == []): 
            return None
        #返回最后一个数组元素，并且栈中元素个数 count 减一
        tmp = self.items[-1]
        #print(tmp)
        self.items.pop()
        self.count = self.count -1
        return tmp

1.2用链表实现一个链式栈

#基于链表实现的栈
from typing import Optional

class Node:
    def __init__(self, data: int, next=None):
        self._data = data
        self._next = next

class LinkedStack:
    def __init__(self):
        self._top: Node = None
    #入栈
    def push(self, value: int):
        new_top = Node(value)
        new_top._next = self._top
        self._top = new_top
    #出栈
    def pop(self) -> Optional[int]:
        if self._top:
            value = self._top._data
            self._top = self._top._next
            return value

    def __repr__(self) -> str:
        current = self._top
        nums = []
        while current:
            nums.append(current._data)
            current = current._next
        return " ".join(f"{num}]" for num in nums)

if __name__ == "__main__":
    stack = LinkedStack()
    for i in range(9):
        stack.push(i)
    print(stack)
    for _ in range(3):
        stack.pop()
    print(stack)

1.3编程模拟一个浏览器的前进、后退功能

#模拟浏览器的前进和后退
import sys
# 引用当前文件夹下的single_linked_list
sys.path.append('LinkStack.py')
from LinkStack import LinkedStack

class NewLinkedStack(LinkedStack):
    def is_empty(self):
        return not self._top

class Browser():
    def __init__(self):
        self.forward_stack = NewLinkedStack()
        self.back_stack = NewLinkedStack()

    def can_forward(self):
        if self.back_stack.is_empty():
            return False
        return True

    def can_back(self):
        if self.forward_stack.is_empty():
            return False
        return True

    def open(self, url):
        print("Open new url %s" % url, end="\n")
        self.forward_stack.push(url)

    def back(self):
        if self.forward_stack.is_empty():
            return
        top = self.forward_stack.pop()
        self.back_stack.push(top)
        print("back to %s" % top, end="\n")

    def forward(self):
        if self.back_stack.is_empty():
            return
        top = self.back_stack.pop()
        self.forward_stack.push(top)
        print("forward to %s" % top, end="\n")


if __name__ == '__main__':

    browser = Browser()
    browser.open('a')
    browser.open('b')
    browser.open('c')
    if browser.can_back():
        browser.back()
    if browser.can_forward():
        browser.forward()
        
    browser.back()
    browser.back()
    browser.back()

2. 队列

2.1用数组实现一个顺序队列

#数组实现的队列
from typing import Optional

class ArrayQueue:
    def __init__(self, capacity: int):
        self._items = []
        self._capacity = capacity
        self._head = 0
        self._tail = 0

    def enqueue(self, item: str) -> bool:
        if self._tail == self._capacity:
            if self._head == 0:
                return False
            else:
                for i in range(0, self._tail - self._head):
                    self._items[i] = self._items[i + self._head]
                self._tail = self._tail - self._head
                self._head = 0

        self._items.insert(self._tail, item)
        self._tail += 1
        return True

    def dequeue(self) -> Optional[str]:
        if self._head != self._tail:
            item = self._items[self._head]
            self._head += 1
            return item
        else:
            return None

    def __repr__(self) -> str:
        return " ".join(item for item in self._items[self._head : self._tail])

2.2用链表事项一个链式队列

2.3实现一个循环队列

from typing import Optional
from itertools import chain
#循环队列

class CircularQueue:
    def __init__(self, capacity):
        self._items = []
        self._capacity = capacity + 1
        self._head = 0
        self._tail = 0

    def enqueue(self, item: str) -> bool:
        if (self._tail + 1) % self._capacity == self._head:
            return False

        self._items.append(item)
        self._tail = (self._tail + 1) % self._capacity
        return True

    def dequeue(self) -> Optional[str]:
        if self._head != self._tail:
            item = self._items[self._head]
            self._head = (self._head + 1) % self._capacity
            return item

    def __repr__(self) -> str:
        if self._tail >= self._head:
            return " ".join(item for item in self._items[self._head : self._tail])
        else:
            return " ".join(item for item in chain(self._items[self._head:], self._items[:self._tail]))

if __name__ == "__main__":
    q = CircularQueue(5)
    for i in range(5):
        q.enqueue(str(i))
    q.dequeue()
    q.dequeue()
    q.enqueue(str(5))
    print(q)

3.链表

3.1实现单链表、循环链表、双向链表，支持增删操作

3.1.1单链表

class Node():
    '''链表结构的Node节点'''

    def __init__(self, data, next=None):
        '''Node节点的初始化方法.
        参数:
            data:存储的数据
            next:下一个Node节点的引用地址
        '''
        self.__data = data
        self.__next = next

    @property
    def data(self):
        '''Node节点存储数据的获取.
        返回:
            当前Node节点存储的数据
        '''
        return self.__data

    @data.setter
    def data(self, data):
        '''Node节点存储数据的设置方法.
        参数:
            data:新的存储数据
        '''
        self.__data = data

    @property
    def next(self):
        '''获取Node节点的next指针值.
        返回:
            next指针数据
        '''
        return self.__next

    @next.setter
    def next(self, next):
        '''Node节点next指针的修改方法.
        参数:
            next:新的下一个Node节点的引用
        '''
        self.__next = next
#单向链表
class SinglyLinkedList():
    def __init__(self):
        '''单向列表的初始化方法.'''
        self.__head = None

    def find_by_value(self, value):
        '''按照数据值在单向列表中查找.
        参数:
            value:查找的数据
        返回:
            Node
        '''
        node = self.__head
        if node != None and node.data != value:
            node = node.next
        else:
            return node

    def find_by_index(self, index):
        '''按照索引值在列表中查找.
        参数: index:索引值
        返回: Node
        '''
        node = self.__head
        pos = 0
        while node != None and pos != index:
            node = node.next
            pos += 1
        return node

    def insert_to_head(self, value):
        '''在链表的头部插入一个存储value数值的Node节点.
        参数:value:将要存储的数据
        '''
        node = Node(value)
        node.next = self.__head
        self.__head = node

    def insert_after(self, node, value):
        '''在链表的某个指定Node节点之后插入一个存储value数据的Node节点.
        参数:
            node:指定的一个Node节点
            value:将要存储在新Node节点中的数据
        '''
        if node == None:  # 如果指定在一个空节点之后插入数据节点，则什么都不做
            return
        new_node = Node(value)
        new_node.next = node.next
        node.next = new_node

    def insert_before(self, node, value):
        '''在链表的某个指定Node节点之前插入一个存储value数据的Node节点.
        参数:
            node:指定的一个Node节点
            value:将要存储在新的Node节点中的数据
        '''
        if node == None or self.__head == None:  # 如果指定在一个空节点之前或者空链表之前插入数据节点，则什么都不做
            return
        if node == self.__head:  # 如果是在链表头之前插入数据节点，则直接插入
            self.insert_to_head(value)
            return
        new_node = Node(value)
        pro = self.__head
        not_found = False  # 如果在整个链表中都没有找到指定插入的Node节点，则该标记量设置为True
        while pro.next != node:  # 寻找指定Node之前的一个Node
            if pro.next == None:  # 如果已经到了链表的最后一个节点，则表明该链表中没有找到指定插入的Node节点
                not_found = True
                break
            else:
                pro = pro.next
        if not_found == False:
            pro.next = new_node
            new_node.next = node

    def delete_by_node(self, node):
        '''在链表中删除指定Node的节点.
        参数:
            node:指定的Node节点
        '''
        if self.__head == None:  # 如果链表是空的，则什么都不做
            return
        if node == self.__head:  # 如果指定删除的Node节点是链表的头节点
            self.__head = node.next
            return
        pro = self.__head
        not_found = False  # 如果在整个链表中都没有找到指定删除的Node节点，则该标记量设置为True
        while pro.next != node:
            if pro.next == None:  # 如果已经到链表的最后一个节点，则表明该链表中没有找到指定删除的Node节点
                not_found == True
                break
            else:
                pro = pro.next
        if not_found == False:
            pro.next = node.next

    def delete_by_value(self, value):
        '''在链表中删除指定存储数据的Node节点.
        参数:
            value:指定的存储数据
        '''
        if self.__head == None:  # 如果链表是空的，则什么都不做
            return

        if self.__head.data == value:  # 如果链表的头Node节点就是指定删除的Node节点
            self.__head = self.__head.next

        pro = self.__head
        node = self.__head.next
        not_found = False
        while node.data != value:
            if node.next == None:  # 如果已经到链表的最后一个节点，则表明该链表中没有找到执行Value值的Node节点
                not_found == True
                break
            else:
                pro = node
                node = node.next
        if not_found == False:
            pro.next = node.next

    def create_node(self, value):
        '''创建一个存储value值的Node节点.
        参数:
            value:将要存储在Node节点中的数据
        返回:
            一个新的Node节点
        '''
        return Node(value)

    def print_all(self):
        '''打印当前链表所有节点数据.'''
        pos = self.__head
        if pos == None:
            print('当前链表还没有数据')
            return
        while pos.next != None:
            print(str(pos.data) + ' --> ', end='')
            pos = pos.next
        print(str(pos.data))

3.1.2双向链表

#双向链表
class Node(object):
    def __init__(self, data=None):
        self.data = data
        self.pre = None
        self.next = None


class DoublyLinkedList(object):
    """初始化双向链表"""

    def __init__(self):
        """
        设置头尾，操作比较容易
        头－－（next）－－》尾
        尾－－（pre）－－》头
        :return:
        """
        head = Node()
        tail = Node()
        self.head = head
        self.tail = tail
        self.head.next = self.tail
        self.tail.pre = self.head

    """追加节点"""

    def append(self, data):
        """
        :param data:
        :return:
        """
        node = Node(data)
        pre = self.tail.pre
        pre.next = node
        node.pre = pre
        self.tail.pre = node
        node.next = self.tail
        return node

    """插入节点"""

    def insert(self, index, data):
        """
        因为加了头尾节点所以获取节点node就一定存在node.next 和 node.pre
        :param index:
        :param data:
        :return:
        """
        length = len(self)
        if abs(index + 1) > length:
            return False
        index = index if index >= 0 else index + 1 + length

        next_node = self.get(index)
        if next_node:
            node = Node(data)
            pre_node = next_node.pre
            pre_node.next = node
            node.pre = pre_node
            node.next = next_node
            next_node.pre = node
            return node

    """删除节点"""

    def delete(self, index):
        node = self.get(index)
        if node:
            node.pre.next = node.next
            node.next.pre = node.pre
            return True
        return False
    """反转链表"""
    def __reversed__(self):
        """
        1.node.next --> node.pre
          node.pre --> node.next
        2.head.next --> None
          tail.pre --> None
        3.head-->tail
         tail-->head
        :return:
        """
        pre_head = self.head
        tail = self.tail

        def reverse(pre_node, node):
            if node:
                next_node = node.next
                node.next = pre_node
                pre_node.pre = node
                if pre_node is self.head:
                    pre_node.next = None
                if node is self.tail:
                    node.pre = None
                return reverse(node, next_node)
            else:
                self.head = tail
                self.tail = pre_head

        return reverse(self.head, self.head.next)

    """获取链表长度"""

    def __len__(self):
        length = 0
        node = self.head
        while node.next != self.tail:
            length += 1
            node = node.next
        return length

    """获取节点"""

    def get(self, index):
        """
        获取第index个值，若index>0正向获取else 反向获取
        :param index:
        :return:
        """
        length = len(self)
        index = index if index >= 0 else length + index
        if index >= length or index < 0: return None
        node = self.head.next
        while index:
            node = node.next
            index -= 1
        return node

    """设置节点"""
    def set(self, index, data):
        node = self.get(index)
        if node:
            node.data = data
        return node

    """清空链表"""
    def clear(self):
        self.head.next = self.tail
        self.tail.pre = self.head

    """打印链表"""

    def show(self, order=1):
        """
        输出双向链表
        :param order 1－－》正向；－1－－》反向 :
        :return: None
        """
        if order >= 0:
            node = self.head.next
            while node is not self.tail:
                print(node.data, end=" ")
                node = node.next
        else:
            node = self.tail.pre
            while node is not self.head:
                print(node.data, end=" ")
                node = node.pre
        print()


if __name__ == '__main__':
    ls = DoublyLinkedList()
    print(len(ls))
    ls.append(1)
    ls.append(2)
    ls.show(1)
    print(len(ls))
    print(ls.get(0).data)
    ls.set(0, 10)
    ls.show()
    ls.insert(1, -2)
    ls.show()
    ls.delete(-2)
    ls.show()
    reversed(ls)
    ls.show()
    ls.clear()
    ls.show()

3.1.3循环链表

class Node():
    '''链表结构的Node节点'''

    def __init__(self, data, next=None):
        '''Node节点的初始化方法.
        参数:
            data:存储的数据
            next:下一个Node节点的引用地址
        '''
        self.__data = data
        self.__next = next

    @property
    def data(self):
        '''Node节点存储数据的获取.
        返回:
            当前Node节点存储的数据
        '''
        return self.__data

    @data.setter
    def data(self, data):
        '''Node节点存储数据的设置方法.
        参数:
            data:新的存储数据
        '''
        self.__data = data

    @property
    def next(self):
        '''获取Node节点的next指针值.
        返回:
            next指针数据
        '''
        return self.__next
class Single_CYCLE_LinkList():
    """单向循环链表"""
    def __init__(self,node=None):
        self._head=node
        if node:
            node.next=node
    def is_empty(self):
        #链表是否为空
        if self._head==None:
            return True
        else:
            return False

    def length(self):
        #链表长度
        if self.is_empty():
            return 0
        cur=self._head
        count=1
        while cur.next!=self._head:
            count+=1
            cur=cur.next
        return count

    def travel(self):
        #遍历整个链表
        if self.is_empty():
            return
        else:
            cur=self._head
            while cur.next!=self._head:
                print(cur.elem,end=' ')
                cur=cur.next
            print(cur.elem)

    def add(self,item):
        node=Node(item)
        if self.is_empty():
            self._head=node
            node.next=node
        else:
            cur=self._head
            while cur.next!=self._head:
                cur=cur.next
            node.next=self._head
            self._head=node
            cur.next=node

    def append(self,item):
        node=Node(item)
        if self._head == None:
            self._head = node
            node.next=node
        else:
            cur=self._head
            while cur.next!=self._head:
                cur=cur.next
            cur.next=node
            node.next=self._head

    def insert(self,pos,item):
        if pos<=0:
            self.add(item)
        elif pos>=self.length():
            self.append(item)
        else:
            node=Node(item)
            pre=self._head
            count=0
            while count<pos-1:
                count+=1
                pre=pre.next
            node.next=pre.next
            pre.next=node

    def remove(self,item):
        """删除一个节点"""
        # 若链表为空，则直接返回
        if self.is_empty():
            return
        # 将cur指向头节点
        pre=None
        cur=self._head
        while cur.next !=self._head:
            if cur.elem==item:
                #先判断此节点是否是头结点
                if cur==self._head:
                    #先找到尾节点
                    rear=self._head
                    while rear.next !=self._head:
                        rear=rear.next
                    rear.next=self._head
                    self._head=cur.next

                else:
                    #中间节点
                    pre.next=cur.next
                return
            else:
                pre=cur
                cur=cur.next
        #退出循环，cur指向尾节点
        if cur.elem==item:
            if self.length()==1:
                self._head=None
            else:
                pre.next = cur.next

    def search(self,item):
        if self.is_empty():
            return False
        cur=self._head
        while cur.next!=self._head:
            if cur.elem==item:
                return True
            else:
                cur=cur.next
        if cur.elem==item:
            return True

3.2实现单链表反转

class Node(object):
    def __init__(self, data=None):
        self.data = data
        self.next = None
class Solution(Node):
    def reverseList(self, head):
        cur, prev = head, None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        return prev

3.3实现两个有序的链表合并为一个有序的链表

class ListNode:
    def __init__(self, x):
         self.val = x
         self.next = None
 
class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = ListNode(0)
        first = head
        while l1 != None and l2 != None:
            if l1.val > l2.val:
                head.next = l2
                l2 = l2.next
            else :
                head.next = l1
                l1 = l1.next
            head = head.next
        if l1 == None:
            head.next = l2
        elif l2 == None:
            head.next = l1

3.4实现求链表的中间结点

class Node(object):
    def __init__(self, data=None):
        self.data = data
        self.next = None
class findMidNode(Node):
    def find_mid_node(self):
        '''查找链表中的中间节点.
        主体思想:设置快、慢两种指针，快指针每次跨两步，慢指针每次跨一步，则当快指针到达链表尾部的时候，慢指针指向链表的中间节点
        返回: node:链表的中间节点
        '''
        fast = self.__head
        slow = self.__head
        while fast.next != None:
            fast = fast.next.next
            slow = slow.next
        return slow