Python用list实现堆栈和队列

Python中可以用list来模拟栈和队列：

• 栈（stack）:只能在一端进行数据操作，遵循后进先出（LIFO）原则
• 队列（queue）:可以在两端进行数据操作，遵循先进先出（FIFO）原则，出队列的一端称为队首，入队列的一端称为队尾

一、栈

1、栈要记录的数据

• 栈顶位置top：注意这个top有两种理解方式，一种是表示栈的最后一个数据的位置，另一种是表示栈的最后一个数据的下一个位置，这两种理解对栈的操作代码有一定的影响
• 栈最大大小size

2、栈的操作

• isEmpty()：判断栈是否为空
• isFull()：判断栈是否已满
• push(element)：向栈中添加一个值，注意栈是否为满的
• pop()：从栈中弹出一个值，注意栈是否为空

3、Python列表实现栈

class StackException(Exception):
    def __init__(self, data):
        self.data = data
    def __str__(self):
        return self.data

class Stack(object):
    def __init__(self,size = 10):
        self.S = []
        self.size = size  # 栈大小
        self.top = -1     # 栈顶位置

    def setSize(self, size):
        # 设置栈的大小
        self.size = size    

    def isEmpty(self):
        # 判断栈是否为空
        if self.top == -1:
            return True
        else:
            return False
    
    def isFull(self):
        # 判断栈是否满
        if self.top == self.size - 1:
            return True
        else:
            return False

    def peek(self):
        # 查看栈顶的对象，但不移除
        if self.isEmpty():
            raise StackException('StackUnderflow')
        else:
            element = self.S[-1]
            return element

    def pop(self):
        # 移除栈顶对象，并返回该对象的值
        if self.isEmpty():
            raise StackException('StackUnderflow')
        else:
            element = self.S[-1]
            self.top = self.top - 1
            del self.S[-1]
            return element

    def push(self, element):
        # 把对象压入栈顶
        if self.isFull():
            raise StackException('StackOverflow')
        else:
            self.S.append(element)
            self.top = self.top + 1

if __name__ == '__main__':
    s = Stack()
    # 压栈测试
    for i in range(10):
        s.push(i)
    # 栈满测试
    try:
        s.push(1)
    except Exception as e:
        print(e)
    # 出栈测试
    for i in range(10):
        print(s.pop())
    # 栈空测试
    try:
        s.pop()
    except Exception as e:
        print(e)

二、队列

1、队列要记录的数据

• 队头位置end
• 队列的大小size

2、标准做法

利用数组Q[1..n]来实现含有n-1个元素队列（保留一位元素用来判断队列空或满）。该列有一个属性Q.head指向队头元素，属性Q.tail指向下一个新元素将要插入的位置，列中的元素存放在位置Q.head, Q.head+1, …, Q.tail-1上。

• 初始时，Q.head = Q.tail = 1
• 当Q.head = Q.tail时， 队列为空
• 当Q.head = Q.tail + 1时，队列为满

3、队列的操作

• isEmpty()：判断队列是否为空
• isFull()：判断队列是否已满
• inQueue(element)：入队
• outQueue()：出队

4、Python列表实现队列

class QueueException(Exception):
    def __init__(self, data):
        self.data = data
    def __str__(self):
        return self.data

class Queue(object):
    def __init__(self, size=10):
        self.Q = []
        self.size = size  # 队列大小
        self.end = -1     # 队头位置
    
    def setSize(self, size):
        # 设置队列的大小
        self.size = size
    
    def inQueue(self, element):
        # 对象入队
        if self.end < self.size - 1:
            self.Q.append(element)
            self.end += 1
        else:
            raise QueueException('QueueFull')
    
    def outQueue(self):
        # 对象出队
        if self.end == -1:
            raise QueueException('QueueEmpty')
        else:
            element = self.Q[0]
            self.Q = self.Q[1:]
            self.end -= 1
            return element

if __name__ == '__main__':
    q = Queue()
    # 入队测试
    for i in range(10):
        q.inQueue(i)
    # 队列满测试
    try:
        q.inQueue(1)
    except Exception as e:
        print(e)
    # 出队测试
    for i in range(10):
        print(q.outQueue())
    # 队列空测试
    try:
        q.outQueue()
    except Exception as e:
        print(e)