# -*- coding: utf-8 -*-
"""
-------------------------------------------------
File Name:        链表实现栈
Description :   
Author :          wellqin
date:             2019/7/11
Change Activity:  2019/7/11
-------------------------------------------------
"""

'''
链表（Linked List）
堆栈的链表实现插到元素前面，因此都是对第一个节点进行操作
下面模块导入自我的链表学习笔记代码
'''
# from LinkedList import LinkedList
# from LinkedList import Node
class Node(object):
    """节点"""

    def __init__(self, elem):
        self.elem = elem
        self.next = None  # 初始设置下一节点为空

'''
上面定义了一个节点的类，当然也可以直接使用python的一些结构。比如通过元组（elem, None）
'''


# 下面创建单链表，并实现其应有的功能


class SingleLinkList(object):
    """单链表"""

    def __init__(self, node=None):  # 使用一个默认参数，在传入头结点时则接收，在没有传入时，就默认头结点为空
        self.__head = node

    def is_empty(self):
        '''链表是否为空'''
        return self.__head == None

    def length(self):
        '''链表长度'''
        # cur游标，用来移动遍历节点
        cur = self.__head
        # count记录数量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        '''遍历整个列表'''
        cur = self.__head
        while cur != None:
            print(cur.elem, end=' ')
            cur = cur.next
        print("\n")

    def add(self, item):
        '''链表头部添加元素'''
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        '''链表尾部添加元素'''
        node = Node(item)
        # 由于特殊情况当链表为空时没有next，所以在前面要做个判断
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        '''指定位置添加元素'''
        if pos <= 0:
                # 如果pos位置在0或者以前，那么都当做头插法来做
            self.add(item)
        elif pos > self.length() - 1:
            # 如果pos位置比原链表长，那么都当做尾插法来做
            self.append(item)
        else:
            per = self.__head
            count = 0
            while count < pos - 1:
                count += 1
                per = per.next
            # 当循环退出后，pre指向pos-1位置
            node = Node(item)
            node.next = per.next
            per.next = node

    def remove(self, item):
        '''删除节点'''
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判断该节点是否是头结点
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        '''查找节点是否存在'''
        cur = self.__head
        while not cur:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False


class LinkedStack(object):
    def __init__(self):
        self._list = LinkedList()

    def __len__(self):
        return self._list.length

    def is_empty(self):
        return self._list.length == 0

    # O(1)
    def push(self, e):
        self._list.add_first(e);

    # O(1)
    def top(self):
        return self._list.get_first().value;

    # O(1)
    def pop(self):
        return self._list.remove_first().value;

    def printstack(self):
        self._list.printlist()


# mystack = LinkedStack()
# print('size was: ', str(len(mystack)))
# mystack.push(1)
# mystack.push(2)
# mystack.push(3)
# mystack.push(4)
# mystack.push(5)
# print('size was: ', str(len(mystack)))
# mystack.printstack()
# mystack.pop()
# mystack.pop()
# print('size was: ', str(len(mystack)))
# mystack.printstack()
# print(mystack.top())
# mystack.pop()
# mystack.pop()
# mystack.pop()

"""
# 输出结果
size
was: 0
size
was: 5
4
3
2
1
size
was: 3
2
1
"""


class Stack:
    def __init__(self):
        self._first = None

    def push(self, item):
        self._first = _Node(item, self._first)

    def pop(self):
        self._first = self._first.next

    def isEmpty(self):
        return self._first is None


class _Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next


def main():
    stack = Stack()
    stack.push("a")
    stack.push("b")
    stack.push("c")
    print(stack._first.item)
    print(stack._first.next.item)
    print(stack._first.next.next.item)
    stack.pop()
    print(stack._first.item)
    print(stack._first.next.item)

    stack.pop()
    print(stack._first.item)



if __name__ == "__main__":
    main()
