数据结构——栈和队列（Python版）

数据结构——栈和队列（Python版） 栈结构

Stack是一种线性存储结构，特点:先进后出，只能在栈顶进行插入和删除。

node.py

class Node:
    def __init__(self,value):
        self.value = value
        self.pre = None  # 指向前一个节点的指针

stack.py

from node import Node


class Stack:
    def __init__(self):
        self.point = None
        self.length = 0

    def push(self,value):
        node = Node(value)
        if self.point!= None:
            node.pre = self.point
            self.point = node
        else:
            self.point = node
        self.length += 1

    def pop(self):
        if self.point!= None:
            node = self.point
            self.point = node.pre
            node.pre = None
            self.length -= 1
            return node.value
        else:
            return None

    def isNone(self):
        if self.length > 0:
            return False
        else:
            return True

---

栈的应用：十进制转二进制

示例1：

from stack import Stack
import math


def ten_to_tow(n):
    if n > 1:
        stack = Stack()
        temp = n
        while(temp>0):
            mod = temp % 2
            stack.push(mod)
            temp = math.floor(temp/2)
        v = stack.pop()
        while(stack.isNone()==False):
            v = v*10+stack.pop()
        return v
    else:
        return n

print(ten_to_tow(6))

示例2：

from stack import Stack
import  math


def ten_to_two(n):
    stack=Stack()
    while (n>0):
        mod = n % 2
        stack.push(mod)
        n = math.floor(n/2)
    for i in range(stack.length):
        v=stack.pop()
        print(v,end='')

ten_to_two(9)

---

最小栈

from node import Node

class MinStack:
    def __init__(self):
        self.point = None
        self.length = 0

    def push(self,value):
        node = Node(value)
        if self.point!= None:
           if node.value>self.point.value:
                minV=self.pop()
                self.add(node)
                self.length += 1
               self.add(Node(minV))
        else:
            self.point = node
        self.length += 1

    def add(self,node):
        node.pre = self.point
        self.point = node

    def pop(self):
        if self.point!= None:
            node = self.point
            self.point = node.pre
            node.pre = None
            self.length -= 1
            return node.value
        else:
            return None

    def isNone(self):
        if self.length > 0:
            return False
        else:
            return True

---

队列

队列是先进先出的线性表，它只允许在表的后端进行插入 *** 作，称为入队；它只允许在表的前端进行删除 *** 作，称为出队。

node.py

class Node:
    def __init__(self,value):
        self.value = value
        self.next = None  # 指向后一个节点的指针

quence.py

from node import Node


class Quenece:
    def __init__(self):
        self.head = None
        self.rear = None
        self.length = 0

    def inQue(self,value):
        node = Node(value)
        if self.head!=0:
            self.rear.next = node
            self.rear = node
        else:
            self.head = node
            self.rear = node
        self.length += 1

    def OutQue(self):
        node = self.head
        if node.next!=None:
            self.head = node.next
            node.next = None
        else:
            self.head = None
            self.rear = None
        self.length -= 1
        return node.value

    def isNone(self):
        if self.head!=None:
            return False
        else:
            return True

---

 两个栈实现一个队列

stackque.py

from stack import Stack

class StackQue:
    def __init__(self):
        self.a=Stack()
        self.b=Stack()

    def appendTail(self,value):
        if self.b.isNone() == False:
            b_length=self.b.length
            for i in range(b_length):
                self.a.push(self.b.pop())
        self.a.push(value)

    def deleteHead(self):
        if self.a.isNone() == False:
            a_length = self.a.length
            for i in range(a_length):
                self.b.push(self.a.pop())
        return self.b.pop()

stackque = StackQue()

for i in range(5):
    stackque.appendTail(i)

for i in range(2):
    print(stackque.deleteHead())

for i in range(7,10):
    stackque.appendTail(i)

for i in range(10):
    print(stackque.deleteHead())

---

以递归的方式反转一个栈

from stack import Stack
from node import Node
stack = Stack()


def rev(node):
    global stack
    preNode = node.pre
    if preNode!=None:
        rev(preNode)
        preNode.pre = node
    else:
        stack.point = node
for i in range(1,6):
    stack.push(i)
node = stack.point
rev(node)
node.pre = None
for i in range(stack.length):
    print(stack.pop())

---

递归加栈实现汉诺塔问题

from node import Node

class Stack:
    def __init__(self):
        self.point = None
        self.length = 0
        self.name = None

    def push(self, value):
        node = Node(value)
        if self.point != None:
            node.pre = self.point
            self.point = node
        else:
            self.point = node
            self.length += 1

    def pop(self):
        if self.point != None:
            node = self.point
            self.point = node.pre
            node.pre = None
            self.length -= 1
            return node.value
        else:
            return None

    def isNone(self):
        if self.length > 0:
            return False
        else:
            return True


a=Stack()
a.name='A'
b=Stack()
b.name='B'
c=Stack()
c.name='C'

def move(n,s1,s2,s3):
    if n!=1:
        move(n-1,s1,s3,s2)
        move(1,s1,s2,s3)
        move(n-1,s2,s1,s3)
    else:
        s3.push(s1.pop())
        print(s1.name,'=>',s3.name)

for i in range(4,0,-1):
    a.push(i)
n=a.length
move(n,a,b,c)
for i in range(n):
    print(c.pop())