Python程序员面试分类真题3

Python程序员面试分类真题31.

实现一个栈的数据结构，使其具有以下方法：压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。正确答案：栈的实现有两种方法，分别为采用数组来实现和采用链表（江南博哥）来实现。下面分别详细介绍这两种方法。

方法一：数组实现

在采用数组来实现栈的时候，栈空间是一段连续的空间。实现思路如下图所示。

从上图中可以看出，可以把数组的首元素当做栈底，同时记录栈中元素的个数size，假设数组首地址为arr，从上图可以看出，压栈的操作其实是把待压栈的元素放到数组arr[size]中，然后执行size+操作；同理，弹栈操作其实是取数组arr[size-1]元素，然后执行size-操作。根据这个原理可以非常容易实现栈，示例代码如下：

classMyStack:

#模拟栈

def__init__(self):

self.items=[]

#撑判断栈是否为空

defisEmpty(self):

returnlen(self.items)==0

#返回栈的大小

defsize(self):

returnlen(self.items)

#返回栈顶元素

deftop(self):

ifnotself.isEmpty():

returnelf.items[len(self.items)-1]

else:

returnNone

#弹栈

defpop(self):

iflen(self.items)＞0:

returnself.items.pop()

else:

print"栈已经为空"

returnNone

#压栈

defpush(self,item):

self.items.append(item)

if__name__=="__main__":

s=MyStack()

s.push(4)

print"栈顶元素为:"+str(s.top())

print"栈大小为:"+str(s.size())

s.pop()

prmt"弹栈成功"

s.pop()

方法二：链表实现

在创建链表的时候经常采用一种从头结点插入新结点的方法，可以采用这种方法来实现栈，最好使用带头结点的链表，这样可以保证对每个结点的操作都是相同的，实现思路如下图所示。

在上图中，在进行压栈操作的时候，首先需要创建新的结点，把待压栈的元素放到新结点的数据域中，然后只需要(1)和(2)两步就实现了压栈操作(把新结点加到了链表首部)。同理，在弹栈的时候，只需要进行(3)的操作就可以删除链表的第一个元素，从而实现弹栈操作。实现代码如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

classMyStack:

def__init__(self):

#pHead=LNode()

self.data=None

self.nexFNone

#判断stack是否为空,如果为空返回true,否则返回false

defempty(self):

ifself.next==None:

returnTrue

else:

returnFalse

#获取栈中元素的个数

defsize(self):

size=0

p=self.next

whilep!=None:

p=p.next

size+=1

returnsize

#入栈:把e放到栈顶

defpush(self,e):

p=LNode

p.data=e

p.next=self.next

self.next=p

#出栈,同时返回栈顶元素

defpop(self):

tmp=self.next

iftmp!=None:

self.next=tmp.next

returntmp.data

print"栈已经为空"

returnNone

#取得栈顶元素

deftop(self):

ifself.next!=None:

returnself.next.data

print"栈已经为空"

returnNone

if__name__=="__main__":

stack=MyStack()

stack.push(1)

print"栈顶元素为:"+str(stack.top())

print"栈大小为:"+str(stack.size())

stack.pop()

print"弹栈成功"

stack.pop()

程序的运行结果为：

栈顶元素为：1

栈大小为：1

弹栈成功

栈已经为空

两种方法的对比：

采用数组实现栈的优点是：一个元素值占用一个存储空间；它的缺点为：如果初始化申请的存储空间太大，会造成空间的浪费，如果申请的存储空间太小，后期会经常需要扩充存储空间，扩充存储空间是个费时的操作，这样会造成性能的下降。

采用链表实现栈的优点是：使用灵活方便，只有在需要的时候才会申请空间。它的缺点为：除了要存储元素外，还需要额外的存储空间存储指针信息。

算法性能分析：

这两种方法压栈与弹栈的时间复杂度都为O(1)。[考点]如何实现栈

2.

实现一个队列的数据结构，使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。正确答案：与实现栈的方法类似，队列的实现也有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。

方法一：数组实现

下图给出了一种最简单的实现方式，用front来记录队列首元素的位置，用rear来记录队列尾元素往后一个位置。入队列的时候只需要将待入队列的元素放到数组下标为rear的位置，同时执行rear+，出队列的时候只需要执行front+即可。

示例代码如下：

classMyQueue:

def__init__(self):

self.arr=[]

self.front=0#队列头

self.rear=0#队列尾

#判断队列是否为空

defisEmpty(self):

returnself.front==self.rear

#返回队列的大小

defsize(self):

returnself.rear-self.front

#返回队列首元素

defgetFront(self):

ifself.isEmpty():

returnNone

returnself.arr[self.front]

#返回队列尾元素

defgetBack(self):

ifself.isEmpty():

returnNone

returnself.arr[self.rear-1]

#删除队列头元素

defdeQueue(self):

ifself.rear＞self.front:

self.front+=1

else:

print"队列已经为空"

#把新元素加入队列尾

defenQueue(self,item):

self.arr.append(item)

self.rear+=1

if__name__=="__main__":

queue=MyQueue()

queue.enQueue(1)

queue.enQueue(2)

print"队列头元素为:"+str(queue.getFront())

print"队列尾元素为:"+str(queue.getBack())

print"队列大小为:"+str(queue.size())

程序的运行结果为：

队列头元素为：1

队列尾元素为：2

队列大小为：2

以上这种实现方法最大的缺点为：出队列后数组前半部分的空间不能被充分地利用，解决这个问题的方法为把数组看成一个环状的空间(循环队列)。当数组最后一个位置被占用后，可以从数组首位置开始循环利用，具体实现方法可以参考数据结构的课本。

方法二：链表实现

采用链表实现队列的方法与实现栈的方法类似，分别用两个指针指向队列的首元素与尾元素，如下图所示。用pHead来指向队列的首元素，用pEnd来指向队列的尾元素。

在上图中，刚开始队列中只有元素1、2和3，当新元素4要进队列的时候，只需要上图中(1)和(2)两步，就可以把新结点连接到链表的尾部，同时修改pEnd指针指向新增加的结点。出队列的时候只需要步骤(3)，改变pHead指针使其指向pHead.next，此外也需要考虑结点所占空间释放的问题。在入队列与出队列的操作中也需要考虑队列尾空的时候的特殊操作，实现代码如下所示：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

classMyQueue:

#分配头结点

def__init__(self):

self.pHead=None

self.pEnd=None

#判断队列是否为空,如果为空返回true,否则返回false

defempty(self):

ifself.pHead=None:

returnTrue

else:

returnFalse

#获取栈中元素的个数

defsize(self):

size=()

p=self.pHead

whilep!=None:

p=p.next

size+=1

returnsize

#入队列:把元素e加到队列尾

defenQueue(self,e):

p=LNode()

p.data=e

p.next=None

ifself.pHead==None:

self.pHead=self.pEnd=p

else:

self.pEnd.next=p

selfpEnd=p

#出队列,删除队列首元素

defdeQueue(self):

ifself.pHead==None:

print"出队列失败,队列已经为空"

self.pHead=self.pHead.next

ifself.pHead==None:

self.pEnd=None

#取得队列首元素

defgetFront(self):

ifself.pHead==None:

print"获取队列首元素失败,队列已经为空"

returnNone

returnself.pHead.data

#取得队列尾元素

defgetBack(self):

ifself.pEnd==None:

print"获取队列尾元素失败,队列已经为空"

returnNone

returnself.pEnd.data

if__name__="__main__":

queue=MyQueue()

queue.enQueue(1)

queue.enQueue(2)

print"队列头元素为:"+str(queue.getFront())

print"队列尾元素为:"+str(queue.getBack())

print"队列大小为:"+str(queue.size())

程序的运行结果为：

队列头元素为：1

队列尾元素为：2

队列大小为：2

显然用链表来实现队列有更好的灵活性，与数组的实现方法相比，它多了用来存储结点关系的指针空间。此外，也可以用循环链表来实现队列，这样只需要一个指向链表最后一个元素的指针即可，因为通过指向链表尾元素可以非常容易地找到链表的首结点。[考点]如何实现队列

3.

翻转(也叫颠倒)栈的所有元素，例如输入栈{1，2，3，4，5}，其中，1处在栈顶，翻转之后的栈为{5，4，3，2，1}，其中，5处在栈顶。正确答案：最容易想到的办法是申请一个额外的队列，先把栈中的元素依次出栈放到队列里，然后把队列里的元素按照出队列顺序入栈，这样就可以实现栈的翻转，这种方法的缺点是需要申请额外的空间存储队列，因此，空间复杂度较高。下面介绍一种空间复杂度较低的递归的方法。

递归程序有两个关键因素需要注意：递归定义和递归终止条件。经过分析后，很容易得到该问题的递归定义和递归终止条件。递归定义：将当前栈的最底元素移到栈顶，其他元素顺次下移一位，然后对不包含栈顶元素的子栈进行同样的操作。终止条件：递归下去，直到栈为空。递归的调用过程如下图所示：

在上图中，对于栈{1，2，3，4，5}，进行翻转的操作为：首先把栈底元素移动到栈顶得到栈{5，1，2，3，4}，然后对不包含栈顶元素的子栈进行递归调用(对子栈元素进行翻转)，子栈{1，2，3，4}翻转的结果为{4，3，2，l}，因此，最终得到翻转后的栈为{5，4，3，2，1}。

此外，由于栈的后进先出的特点，使得只能取栈顶的元素，因此，要把栈底的元素移动到栈顶也需要递归调用才能完成，主要思路为：把不包含该栈顶元素的子栈的栈底的元素移动到子栈的栈顶，然后把栈顶的元素与子栈栈顶的元素(其实就是与栈顶相邻的元素)进行交换。

为了更容易理解递归调用，可以认为在进行递归调用的时候，子栈已经把栈底元素移动到了栈顶，在上图中，为了把栈{1，2，3，4，5}的栈底元素5移动到栈顶，首先对子栈{2，3，4，5}，进行递归调用，调用的结果为{5，2，3，4}，然后对子栈顶元素5，与栈顶元素1进行交换得到栈{5，1，2，3，4)，实现了把栈底元素移动到栈顶。

实现代码如下：

#Python中没有栈的模块,所以先新建一个栈类

classStack:

#模拟栈

def__init__(self):

self.items=[]

#判断栈是否为空

defempty(self):

returnlen(self.items)==0

#返回栈的大小

defsize(self):

returnlen(self.items)

#返回栈顶元素

defpeek(self):

ifnotself.empty():

returnself.items[len(self.items)-1]

else:

returnNone

#弹栈

defpop(self):

iflen(self.items)＞0:

returnself.items.pop()

else:

priiit"栈已经为空"

returnNone

#压栈

defpush(self,item):

self.items.append(item)

"""

方法功能:把栈底元素移动到栈顶

参数:s栈的引用

"""

defmoveBottomToTop(s):

ifs.empty():

return

top1=s.peek()

s.pop()#弹出栈项元素

ifnots.empty():

#递归处理不包含栈顶元素的子栈

moveBottomToTop(s)

top2=s.peek()

s.pop()

#交换栈顶元素与予栈栈顶元素

s.push(top1)

s.push(top2)

else:

s.push(top1)

defreverse_stack(s):

ifs.empty():

return

#把栈底元素移动到栈顶

moveBottomToTop(s)

top=s.peek()

s.pop()

#递归处理子栈

reverse_stack(s)

s.push(top)

if__name__=="__main__":

s=Stack()

s.push(5)

s.push(4)

s.push(3)

s.push(2)

s.push(1)

reverse_stack(s)

print"翻转后出栈顺序为:",

whilenots.empty():

prints.peek(),

s.pop()

程序的运行结果为：

翻转后出栈顺序为：54321

算法性能分析：

把栈底元素移动到栈顶操作的时间复杂度为O(N)，在翻转操作中对每个子栈都进行了把栈底元素移动到栈顶的操作，因此，翻转算法的时间复杂度为O(N2)。[考点]如何翻转栈的所有元素

4.

输入两个整数序列，其中一个序列表示栈的push(入)顺序，判断另一个序列有没有可能是对应的pop(出)顺序。正确答案：假如输入的push序列是1、2、3、4、5，那么3、2、5、4、1就有可能是一个pop序列，但5、3、4、1、2就不可能是它的一个pop序列。

主要思路是使用一个栈来模拟入栈顺序，具体步骤如下：

(1)把push序列依次入栈，直到栈顶元素等于pop序列的第一个元素，然后栈顶元素出栈，pop序列移动到第二个元素；

(2)如果栈顶继续等于pop序列现在的元素，则继续出栈并pop后移；否则对push序列继续入栈。

(3)如果push序列已经全部入栈，但是pop序列未全部遍历，而且栈顶元素不等于当前pop元素，那么这个序列不是一个可能的出栈序列。如果栈为空，而且pop序列也全部被遍历过，则说明这是一个可能的pop序列。下图给出一个合理的pop序列的判断过程。

在上图中，(1)～(3)三步，由于栈顶元素不等于pop序列第一个元素3，因此，1，2，3依次入栈，当3入栈后，栈顶元素等于pop序列的第一个元素3，因此，第(4)步执行3出栈，接下来指向第二个pop序列2，且栈顶元素等于pop序列的当前元素，因此，第(5)步执行2出栈；接着由于栈顶元素4不等于当前pop序列5，因此，接下来(6)和(7)两步分别执行4和5入栈；接着由于栈顶元素5等于pop序列的当前值，因此，第(8)步执行5出栈，接下来(9)和(10)两步栈项元素都等于当前pop序列的元素，因此，都执行出栈操作。最后由于栈为空，同时pop序列都完成了遍历，因此，{3，2，5，4，1}是一个合理的出栈序列。

实现代码如下：

classStack:

#模拟栈

def__init__(self):

selfitems=[]

#判断栈是否为空

defempty(self):

returnlen(self.items)==0

#返回栈的大小

defsize(self):

returnlen(self.items)

#返回栈顶元素

defpeek(self):

ifnotself.empty():

returnself.items[len(self.items)-1]

else:

returnNone

#弹栈

defpop(self):

iflen(self.items)＞0:

returnself.items.pop()

else:

print"栈已经为空"

returnNone

#压栈

defpush(self,item):

self.items.append(item)

defisPopSerial(push,pop):

ifpush==Noneorpop==None:

returnFalse

pushLen=len(push)

popLen=len(pop)

ifpushLen!=popLen:

returnFalse

pushIndex=0

popIndex=0

stack=Stack()

whilepushIndex＜pushLen:

#把push序列依次入栈,直到栈顶元素等于pop序列的第一个元素

stack.push(push[pushIndex])

pushIndex+=1

#栈顶元素出栈,pop序列移动到下一个元素

while(notstack.empty())andstack.peek()==pop[popIndex]:

stack.pop()

popIndex+=1

#栈为空,且pop序列中元素都被遍历过

returnstack.empty()andpopIndex==popLen

if__name__=="__main__":

push="12345"

pop="32541"

ifisPopSerial(push,pop):

printpop+"是"+push+"的一个pop序列"

else:

printpop+"不是"+push+"的一个pop序列"

程序的运行结果为：

32541是12345的一个pop序列

算法性能分析：

这种方法在处理一个合理的pop序列的时候需要操作的次数最多，即把push序列进行一次压栈和出栈操作，操作次数为2N，因此，时间复杂度为O(N)，此外，这种方法使用了额外的栈空间，因此，空间复杂度为O(N)。[考点]如何根据入栈序列判断可能的出栈序列

5.

如何用O(1)的时间复杂度求栈中最小元素正确答案：由于栈具有后进先出的特点，因此，push和pop只需要对栈顶元素进行操作。如果使用上述的实现方式，只能访问到栈顶的元素，无法得到栈中最小的元素。当然，可以用另外一个变量来记录栈底的位置，通过遍历栈中所有的元素找出最小值，但是这种方法的时间复杂度为O(N)，那么如何才能用O(1)的时间复杂度求出栈中最小的元素呢?

在算法设计中，经常会采用空间换取时间的方式来提高时间复杂度，也就是说，采用额外的存储空间来降低操作的时间复杂度。具体而言，在实现的时候使用两个栈结构，一个栈用来存储数据，另外一个栈用来存储栈的最小元素。实现思路如下：如果当前入栈的元素比原来栈中的最小值还小，则把这个值压入保存最小元素的栈中；在出栈的时候，如果当前出栈的元素恰好为当前栈中的最小值，保存最小值的栈顶元素也出栈，使得当前最小值变为当前最小值入栈之前的那个最小值。为了简单起见，可以在栈中保存int类型。

实现代码如下：

#模拟栈

classStack:

def__init__(self):

self.items=[]

#判断栈是否为空

defempty(self):

returnlen(self.items)==0

#返回栈的大小

defsize(self):

returnlen(setf.items)

#返回栈顶元素

defpeek(self):

ifnotself.empty():

returnself.items[len(self.items)-1]

else:

returnNone

#弹栈

defpop(self):

iflen(self.