Python数据结构算法(03)栈队列

Python数据结构&算法(03) 栈和队列

3.1 栈

栈可以理解为只允许在表尾进行插入或删除的线性表&＃xff0c;对栈而言&＃xff0c;其表尾称为栈顶&＃xff0c;相应的其表头端称为栈底&＃xff0c;不含元素的空表称为空栈。

假设栈 S &＃61; (a1, a2, ..., an) &＃xff0c;则称 a1 为栈底元素&＃xff0c;an 为栈顶元素。栈中元素是按照 a1, a2, ..., an 的顺序依次进栈的&＃xff0c;退栈的第一个元素应为栈顶元素&＃xff0c;因此栈可以被称为 后进先出&＃xff08;LIFO&＃xff09; 结构的线性表。

3.1.1 栈的基本操作

栈的抽象数据类型定义如下所示&＃xff1a;

ADT Stack{数据对象&＃xff1a;D &＃61; {ai | ai ∈ ElemSet, i &＃61; 1, 2, ..., n, n >&＃61; 0}数据关系&＃xff1a;R &＃61; { | ai-1, ai ∈ D&＃xff0c; i &＃61; 2, ..., n}约定 an 为栈顶&＃xff0c;a1 为栈底。基本操作&＃xff1a;初始化栈插入元素删除元素清空栈判断栈是否为空返回栈中元素个数返回栈顶元素的值遍历栈
}


在python中&＃xff0c;列表很好的实现了栈的功能&＃xff0c;使用相关函数即可实现出栈和入栈的操作。

list.append() # 将元素添加至末尾list.pop([index&＃61;-1]) # 删除指定位置的元素&＃xff0c;若为空则删除末尾元素


3.1.2 链式栈

如果使用链表实现栈则可以使用尾插法模拟入栈操作&＃xff0c;指定删除最后一个元素即可实现出栈操作。

class Node:def __init__(self, elem&＃61;None):self.elem &＃61; elemself.next &＃61; Noneclass Stack:def __init__(self):self.__base &＃61; Node(-1)self.__top &＃61; self.__basedef push(self, elem):newNode &＃61; Node(elem)self.__top.next &＃61; newNodeself.__top &＃61; newNodedef pop(self):if self.__base.next &＃61;&＃61; None:print("Error!")return 0else:nowNode &＃61; self.__basewhile nowNode.next.next !&＃61; None:nowNode &＃61; nowNode.nextnowNode.next &＃61; Noneself.__top &＃61; nowNodedef clear(self):self.__base.next &＃61; Noneself.__top &＃61; self.__basedef isEmpty(self):return self.__base.elem &＃61;&＃61; self.__top.elemdef num(self):num &＃61; 0nowNode &＃61; self.__basewhile nowNode.next !&＃61; None:nowNode &＃61; nowNode.nextnum &＃61; num &＃43; 1return numdef getTop(self):return self.__top.elemdef printStack(self):nowNode &＃61; self.__base.nextwhile nowNode !&＃61; None:print(nowNode.elem)nowNode &＃61; nowNode.nextif __name__ &＃61;&＃61; "__main__":S &＃61; Stack()for i in range(1, 10):S.push(i)S.printStack()


3.2 队列

队列与栈相反&＃xff0c;是一种先进先出&＃xff08;FIFO&＃xff09;的线性表&＃xff0c;它只允许在表的一端进行插入&＃xff0c;而在另一端删除元素。在队列中&＃xff0c;允许插入的一端叫做队尾&＃xff0c;允许删除的一端叫做队头。

3.2.1 队列的基本操作

队列的操作与栈的操作类似&＃xff0c;不同之处在于删除是在表的头部&＃xff08;队头&＃xff09;进行的。

ADT Queue{数据对象&＃xff1a;D &＃61; {ai | ai ∈ ElemSet, i &＃61; 1, 2, ..., n, n >&＃61; 0}数据关系&＃xff1a;R &＃61; { | ai-1, ai ∈ D, i &＃61; 2, ..., n}基本操作&＃xff1a;初始化队列插入元素删除元素清空队列判断队列是否为空返回队列中元素个数返回队头元素的值遍历队列
}


3.2.2 链式队列

用链表表示的队列简称为链队列&＃xff0c;一个链队列需要两个分别指示队头和队尾的指针。

class Node:def __init__(self, elem&＃61;None):self.elem &＃61; elemself.next &＃61; Noneclass Queue:def __init__(self):self.__front &＃61; Node(-1)self.__rear &＃61; self.__frontdef enQueue(self, elem):newNode &＃61; Node(elem)self.__rear.next &＃61; newNodeself.__rear &＃61; newNodedef deQueue(self):if self.__front.next &＃61;&＃61; None:print("Error!")return 0else:self.__front.next &＃61; self.__front.next.nextdef clear(self):self.__front.next &＃61; Noneself.__rear &＃61; self.__frontdef isEmpty(self):return self.__front &＃61;&＃61; self.__reardef num(self):num &＃61; 0nowNode &＃61; self.__frontwhile nowNode.next !&＃61; None:nowNode &＃61; nowNode.nextnum &＃61; num &＃43; 1return numdef getHead(self):if self.__front.next &＃61;&＃61; None:print("Error!")return 0else:return self.__front.next.elemdef printQueue(self):nowNode &＃61; self.__front.nextwhile nowNode !&＃61; None:print(nowNode.elem)nowNode &＃61; nowNode.nextif __name__ &＃61;&＃61; "__main__":Q &＃61; Queue()for i in range(1, 10):Q.enQueue(i)Q.printQueue()


3.3.3 循环队列

循环队列需要给队列指定一个最大长度&＃xff0c;整体逻辑结构如同一个环&＃xff0c;这里实现采用顺序表示&＃xff08;用一组地址连续的存储单元依次存储元素&＃xff09;。

class CircularQueue:def __init__(self, maxSize):self.queue &＃61; [None] * maxSizeself.maxSize &＃61; maxSizeself.__front &＃61; 0self.__rear &＃61; 0def num(self):if self.queue[self.__rear] &＃61;&＃61; None:return (self.__rear - self.__front &＃43; self.maxSize) % self.maxSizeelse:return self.maxSizedef enQueue(self, elem):if (self.__rear &＃43; 1) % self.maxSize &＃61;&＃61; self.__front:if self.queue[self.__rear] &＃61;&＃61; None:self.queue[self.__rear] &＃61; elemelse:print("FULL QUEUE!")else:self.queue[self.__rear] &＃61; elemself.__rear &＃61; (self.__rear &＃43; 1) % self.maxSizedef deQueue(self):if self.__front &＃61;&＃61; self.__rear:print("EMPTY QUEUE!")return 0else:self.queue[self.__front] &＃61; Noneif (self.__rear &＃43; 1) % self.maxSize &＃61;&＃61; self.__front:self.__rear &＃61; (self.__rear &＃43; 1) % self.maxSizeself.__front &＃61; (self.__front &＃43; 1) % self.maxSizedef printCircularQueue(self):for i in range(self.maxSize):print(self.queue[i])if __name__ &＃61;&＃61; "__main__":CQ &＃61; CircularQueue(9)for i in range(1, 10):CQ.enQueue(i)CQ.printCircularQueue()