“编程的本质来自算法，算法的本质来自数学，编程就是把数学问题码出来。”不易掌握的知识。栈和队列都是用来存储数据的。不管底层是数组还是链表实现，基本原理都是一样的，就是栈的特性是先进后出，队列的特性是先进先出-先出。栈（Stack）是一种后进先出（lastinfirstoff，LIFO）的数据结构。线性表是用数组实现的。对于栈这样的线性表，只能在一端进行插入和删除，下标为0的数组的一端（栈底不变，只需要跟踪栈顶）用作堆栈。底部更合适。列表封装的这些方法使得栈的常用数据结构的实现变得更加容易。栈是一种特殊的链表，只能在链表的一端进出。pop方式完美实现：In[1]:stack=[1,3,5]In[2]:stack.append(0)#pushelement0toEnd,无需指定indexIn[3]:stackOut[3]:[1,3,5,0]In[4]:stack.pop()#pop元素，不用指定index，此时移出endElementOut[4]:0In[5]:stackOut[5]:[1,3,5]可以看出，Python列表作为栈使用，完全没有问题，push和pop操作的时间复杂度为O(1)队列(Queue）是一种先进先出（fisrtinfirstout，FIFO）结构。使用顺序表存储队列时，队列元素的出队在队头，即下标为0的地方。当一个元素出队时，出队元素后面的所有元素都需要移动forward保证队头始终在下标为0的位置，这样会大大增加时间复杂度。使用列表模拟队列需要在Python的collections模块中实现双端队列deque。先进先出和后进后出模拟队列如下：In[1]:fromcollectionsimportdequeIn[2]:queue=[1,3,5]In[3]:deq=deque(queue)In[4]:deq.append(0)In[5]:deqOut[5]:deque([1,3,5,0])#插入队列尾部In[6]:deq.popleft()Out[6]:1In[7]:deqOut[7]:deque([3,5,0])#先进先出LeetCode第225题：用队列实现栈#使用队列实现一个栈#使用队列实现对一个栈的如下操作：#push(x)--元素x入栈#pop()--取出栈顶元素#top()--获取栈顶元素#empty()--返回栈是否为空#注意：#只能使用队列的基本操作--即pushtoback、peek/popfromfront、size、isempty都是合法的.#你使用的语言可能不支持队列。可以使用list或者deque（双端队列）来模拟一个队列，只要是标准的队列操作即可。#您可以假设所有操作都是有效的（例如，不会在空堆栈上调用pop或top操作）。#RelatedTopics栈设计根据题意，只能使用队列的基本操作。因为队列是先进先出的，所以需要实现一个先进后出的栈。要么用队列实现栈，要么用栈实现队列。一个常见的解决方案是使用两个队列或两个堆栈。假设有两个队列，q1和q2，我们首先初始化队列。fromcollectionsimportdequeclassMyStack:def__init__(self):"""Initializeyourdatastructurehere."""self.q1=deque()self.q2=deque()push(x):当元素x入栈时，和添加元素一样到队列。当入栈时，它被添加到q1的末尾，那么q1末尾的元素就是栈顶元素。所以只需要append(x)。defpush(self,x:int)->None:"""Pushelementxontostack."""self.q1.append(x)pop删除元素，我们可以用q2保存q1最后一个元素之前的元素，和然后q1元素被删除，最后两个队列交换。我们需要弹出栈顶元素，即q1的最后一个元素。队列只能先进先出。我们必须使用q2来存储由q1出队的元素。最后一个出队元素是堆栈的顶部元素。所以代码需要判断q1的长度。如果q1的长度大于1，则将q1的头元素添加到q2，直到q1只有最后一个元素。defpop(self)->int:"""移除堆栈顶部的元素并返回该元素。"""whilelen(self.q1)>1:self.q2.append(self.q1.popleft())tmp=self.q1.popleft()self.q2,self.q1=self.q1,self.q2returntmp判断是否为空，只需要判断q1的队列是否为空即可。defense(self)->bool:"""Returnswhetherthestackisempty."""returnnotbool(self.q1)取栈顶元素。这个其实可以巧妙的解决。我们直接调用pop方法删除，pop删除时用一个变量保存，需要重新插入元素。deftop(self)->int:ans=self.pop()self.q1.append(ans)returns以下是实现带队列的栈的完整代码fromcollectionsimportdequeclassMyStack:def__init__(self):"""Initializeyourdatastructurehere."""self.q1=deque()self.q2=deque()defpush(self,x:int)->None:"""Pushelementxontostack."""self.q1.append(x)defpop(self)->int:"""移除堆栈顶部的元素并返回该元素。"""whilelen(self.q1)>1:self.q2.append(self.q1.popleft())tmp=self.q1.popleft()self.q2,self.q1=self.q1,self.q2returntmpdeftop(self)->int:"""Getthetopelement."""ans=self.pop()self.q1.append(ans)returnansdefempty(self)->bool:"""Returnswhetherthackisempty."""returnnotbool(self.q1)LeetCode第232题：用栈实现队列#pop()--从队列头部移除元素。#peek()--返回队列头部的元素。#empty()--返回队列是否为空。#示例：#MyQueuequeue=newMyQueue();#queue.push(1);#queue.push(2);#queue.peek();//Return1#queue.pop();//Return1#queue.empty();//返回false#说明:#只能使用标准栈操作——即只有pushtotop、peek/popfromtop、size、isempty操作是合法的。#您使用的语言可能不支持堆栈。可以用list或者deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。#假设所有操作都是有效的（例如，空队列不会调用pop或peek操作）。#RelatedTopics设计一个栈最简单的方法就是用一个list来表示一个栈，而且只能使用栈的相关方法，比如append(),pop(),s[-1]，分别是add元素到栈顶，删除栈顶元素，取出栈顶元素..classMyQueue:def__init__(self):self.s=[]defpush(self,x:int)->None:self.s.append(x)defpop(self)->int:returnsself.s.pop(0)defpeek(self)->int:returnsself.s[0]defempty(self)->bool:returnnotbool(self.s)当然也可以用两个栈，这个是比较复杂的操作，《不过也是常用算法测试点》（1）初始化两个栈结构，s1为主栈，s2为辅助堆栈。(2)push在s1的末尾添加元素，可以使用append来实现。(3)出栈时，先把s1的元素传给s2，知道s1只剩下一个元素（这是我们要返回的队列的第一个元素），然后我们把2中的元素传回s1.(4)返回队头元素，与步骤(3)中的操作类似，唯一不同的是这里需要先将元素添加回stack2，然后再将stack2的元素传回stack1，因为peek操作不需要删除队头元素(5)空可以判断stack1的大小。dequeue操作首先判断缓存栈s2中是否有元素，如果有则直接移除s2的栈顶元素；如果s2为空，s1中有元素，则将s1中的元素全部转移到s2中，然后移除s2的栈顶元素，即可以模拟队列的出队操作；本例中并没有出现s2和s1都为空的情况。classMyQueue:def__init__(self):"""在这里初始化你的数据结构。"""self.s1=[]self.s2=[]defpush(self,x:int)->None:"""Pushelementxtothebackofqueue."""self.s1.append(x)defpop(self)->int:"""从队列中移除元素并返回那个元素。"""ifself.s2:returnself.s2.pop()else:ifself.s1:whileself.s1:self.s2.append(self.s1.pop())returnsself.s2.pop()defpeek(self)->int:"""Getthefrontelement."""ifself.s2:returnsself.s2[-1]else:ifself.s1:whileself.s1:self.s2.append(self.s1.pop())returnself.s2[-1]defempty(self)->bool:"""Returnswhetherthequeueisempty."""ifself.s1orself.s2:returnFalseelse:returnTrue#YourMyQueueobjectwillbeinstantiatedandcalledassuch:#obj=MyQueue()#obj.push(x)#param_2=obj.pop()#param_3=obj.peek()#param_4=obj.empty()本文已收录GitHub：https://github.com/MaoliRUNsen/runsenlearnpy100
