Python程序員面試分類真題3

Python程序員面試分類真題31.

實現(xiàn)一個棧的數(shù)據(jù)結(jié)構(gòu)，使其具有以下方法：壓棧、彈棧、取棧頂元素、判斷棧是否為空以及獲取棧中元素個數(shù)。正確答案：棧的實現(xiàn)有兩種方法，分別為采用數(shù)組來實現(xiàn)和采用鏈表（江南博哥）來實現(xiàn)。下面分別詳細介紹這兩種方法。

方法一：數(shù)組實現(xiàn)

在采用數(shù)組來實現(xiàn)棧的時候，?？臻g是一段連續(xù)的空間。實現(xiàn)思路如下圖所示。

從上圖中可以看出，可以把數(shù)組的首元素當做棧底，同時記錄棧中元素的個數(shù)size，假設(shè)數(shù)組首地址為arr，從上圖可以看出，壓棧的操作其實是把待壓棧的元素放到數(shù)組arr[size]中，然后執(zhí)行size+操作；同理，彈棧操作其實是取數(shù)組arr[size-1]元素，然后執(zhí)行size-操作。根據(jù)這個原理可以非常容易實現(xiàn)棧，示例代碼如下：

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"棧已經(jīng)為空"

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()

方法二：鏈表實現(xiàn)

在創(chuàng)建鏈表的時候經(jīng)常采用一種從頭結(jié)點插入新結(jié)點的方法，可以采用這種方法來實現(xiàn)棧，最好使用帶頭結(jié)點的鏈表，這樣可以保證對每個結(jié)點的操作都是相同的，實現(xiàn)思路如下圖所示。

在上圖中，在進行壓棧操作的時候，首先需要創(chuàng)建新的結(jié)點，把待壓棧的元素放到新結(jié)點的數(shù)據(jù)域中，然后只需要(1)和(2)兩步就實現(xiàn)了壓棧操作(把新結(jié)點加到了鏈表首部)。同理，在彈棧的時候，只需要進行(3)的操作就可以刪除鏈表的第一個元素，從而實現(xiàn)彈棧操作。實現(xiàn)代碼如下：

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

#獲取棧中元素的個數(shù)

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"棧已經(jīng)為空"

returnNone

#取得棧頂元素

deftop(self):

ifself.next!=None:

returnself.next.data

print"棧已經(jīng)為空"

returnNone

if__name__=="__main__":

stack=MyStack()

stack.push(1)

print"棧頂元素為:"+str(stack.top())

print"棧大小為:"+str(stack.size())

stack.pop()

print"彈棧成功"

stack.pop()

程序的運行結(jié)果為：

棧頂元素為：1

棧大小為：1

彈棧成功

棧已經(jīng)為空

兩種方法的對比：

采用數(shù)組實現(xiàn)棧的優(yōu)點是：一個元素值占用一個存儲空間；它的缺點為：如果初始化申請的存儲空間太大，會造成空間的浪費，如果申請的存儲空間太小，后期會經(jīng)常需要擴充存儲空間，擴充存儲空間是個費時的操作，這樣會造成性能的下降。

采用鏈表實現(xiàn)棧的優(yōu)點是：使用靈活方便，只有在需要的時候才會申請空間。它的缺點為：除了要存儲元素外，還需要額外的存儲空間存儲指針信息。

算法性能分析：

這兩種方法壓棧與彈棧的時間復雜度都為O(1)。[考點]如何實現(xiàn)棧

2.

實現(xiàn)一個隊列的數(shù)據(jù)結(jié)構(gòu)，使其具有入隊列、出隊列、查看隊列首尾元素、查看隊列大小等功能。正確答案：與實現(xiàn)棧的方法類似，隊列的實現(xiàn)也有兩種方法，分別為采用數(shù)組來實現(xiàn)和采用鏈表來實現(xiàn)。下面分別詳細介紹這兩種方法。

方法一：數(shù)組實現(xiàn)

下圖給出了一種最簡單的實現(xiàn)方式，用front來記錄隊列首元素的位置，用rear來記錄隊列尾元素往后一個位置。入隊列的時候只需要將待入隊列的元素放到數(shù)組下標為rear的位置，同時執(zhí)行rear+，出隊列的時候只需要執(zhí)行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"隊列已經(jīng)為空"

#把新元素加入隊列尾

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())

程序的運行結(jié)果為：

隊列頭元素為：1

隊列尾元素為：2

隊列大小為：2

以上這種實現(xiàn)方法最大的缺點為：出隊列后數(shù)組前半部分的空間不能被充分地利用，解決這個問題的方法為把數(shù)組看成一個環(huán)狀的空間(循環(huán)隊列)。當數(shù)組最后一個位置被占用后，可以從數(shù)組首位置開始循環(huán)利用，具體實現(xiàn)方法可以參考數(shù)據(jù)結(jié)構(gòu)的課本。

方法二：鏈表實現(xiàn)

采用鏈表實現(xiàn)隊列的方法與實現(xiàn)棧的方法類似，分別用兩個指針指向隊列的首元素與尾元素，如下圖所示。用pHead來指向隊列的首元素，用pEnd來指向隊列的尾元素。

在上圖中，剛開始隊列中只有元素1、2和3，當新元素4要進隊列的時候，只需要上圖中(1)和(2)兩步，就可以把新結(jié)點連接到鏈表的尾部，同時修改pEnd指針指向新增加的結(jié)點。出隊列的時候只需要步驟(3)，改變pHead指針使其指向pHead.next，此外也需要考慮結(jié)點所占空間釋放的問題。在入隊列與出隊列的操作中也需要考慮隊列尾空的時候的特殊操作，實現(xiàn)代碼如下所示：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

classMyQueue:

#分配頭結(jié)點

def__init__(self):

self.pHead=None

self.pEnd=None

#判斷隊列是否為空,如果為空返回true,否則返回false

defempty(self):

ifself.pHead=None:

returnTrue

else:

returnFalse

#獲取棧中元素的個數(shù)

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"出隊列失敗,隊列已經(jīng)為空"

self.pHead=self.pHead.next

ifself.pHead==None:

self.pEnd=None

#取得隊列首元素

defgetFront(self):

ifself.pHead==None:

print"獲取隊列首元素失敗,隊列已經(jīng)為空"

returnNone

returnself.pHead.data

#取得隊列尾元素

defgetBack(self):

ifself.pEnd==None:

print"獲取隊列尾元素失敗,隊列已經(jīng)為空"

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())

程序的運行結(jié)果為：

隊列頭元素為：1

隊列尾元素為：2

隊列大小為：2

顯然用鏈表來實現(xiàn)隊列有更好的靈活性，與數(shù)組的實現(xiàn)方法相比，它多了用來存儲結(jié)點關(guān)系的指針空間。此外，也可以用循環(huán)鏈表來實現(xiàn)隊列，這樣只需要一個指向鏈表最后一個元素的指針即可，因為通過指向鏈表尾元素可以非常容易地找到鏈表的首結(jié)點。[考點]如何實現(xiàn)隊列

3.

翻轉(zhuǎn)(也叫顛倒)棧的所有元素，例如輸入棧{1，2，3，4，5}，其中，1處在棧頂，翻轉(zhuǎn)之后的棧為{5，4，3，2，1}，其中，5處在棧頂。正確答案：最容易想到的辦法是申請一個額外的隊列，先把棧中的元素依次出棧放到隊列里，然后把隊列里的元素按照出隊列順序入棧，這樣就可以實現(xiàn)棧的翻轉(zhuǎn)，這種方法的缺點是需要申請額外的空間存儲隊列，因此，空間復雜度較高。下面介紹一種空間復雜度較低的遞歸的方法。

遞歸程序有兩個關(guān)鍵因素需要注意：遞歸定義和遞歸終止條件。經(jīng)過分析后，很容易得到該問題的遞歸定義和遞歸終止條件。遞歸定義：將當前棧的最底元素移到棧頂，其他元素順次下移一位，然后對不包含棧頂元素的子棧進行同樣的操作。終止條件：遞歸下去，直到棧為空。遞歸的調(diào)用過程如下圖所示：

在上圖中，對于棧{1，2，3，4，5}，進行翻轉(zhuǎn)的操作為：首先把棧底元素移動到棧頂?shù)玫綏5，1，2，3，4}，然后對不包含棧頂元素的子棧進行遞歸調(diào)用(對子棧元素進行翻轉(zhuǎn))，子棧{1，2，3，4}翻轉(zhuǎn)的結(jié)果為{4，3，2，l}，因此，最終得到翻轉(zhuǎn)后的棧為{5，4，3，2，1}。

此外，由于棧的后進先出的特點，使得只能取棧頂?shù)脑?，因此，要把棧底的元素移動到棧頂也需要遞歸調(diào)用才能完成，主要思路為：把不包含該棧頂元素的子棧的棧底的元素移動到子棧的棧頂，然后把棧頂?shù)脑嘏c子棧棧頂?shù)脑?其實就是與棧頂相鄰的元素)進行交換。

為了更容易理解遞歸調(diào)用，可以認為在進行遞歸調(diào)用的時候，子棧已經(jīng)把棧底元素移動到了棧頂，在上圖中，為了把棧{1，2，3，4，5}的棧底元素5移動到棧頂，首先對子棧{2，3，4，5}，進行遞歸調(diào)用，調(diào)用的結(jié)果為{5，2，3，4}，然后對子棧頂元素5，與棧頂元素1進行交換得到棧{5，1，2，3，4)，實現(xiàn)了把棧底元素移動到棧頂。

實現(xiàn)代碼如下：

#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"棧已經(jīng)為空"

returnNone

#壓棧

defpush(self,item):

self.items.append(item)

"""

方法功能:把棧底元素移動到棧頂

參數(shù):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"翻轉(zhuǎn)后出棧順序為:",

whilenots.empty():

prints.peek(),

s.pop()

程序的運行結(jié)果為：

翻轉(zhuǎn)后出棧順序為：54321

算法性能分析：

把棧底元素移動到棧頂操作的時間復雜度為O(N)，在翻轉(zhuǎn)操作中對每個子棧都進行了把棧底元素移動到棧頂?shù)牟僮?，因此，翻轉(zhuǎn)算法的時間復雜度為O(N2)。[考點]如何翻轉(zhuǎn)棧的所有元素

4.

輸入兩個整數(shù)序列，其中一個序列表示棧的push(入)順序，判斷另一個序列有沒有可能是對應(yīng)的pop(出)順序。正確答案：假如輸入的push序列是1、2、3、4、5，那么3、2、5、4、1就有可能是一個pop序列，但5、3、4、1、2就不可能是它的一個pop序列。

主要思路是使用一個棧來模擬入棧順序，具體步驟如下：

(1)把push序列依次入棧，直到棧頂元素等于pop序列的第一個元素，然后棧頂元素出棧，pop序列移動到第二個元素；

(2)如果棧頂繼續(xù)等于pop序列現(xiàn)在的元素，則繼續(xù)出棧并pop后移；否則對push序列繼續(xù)入棧。

(3)如果push序列已經(jīng)全部入棧，但是pop序列未全部遍歷，而且棧頂元素不等于當前pop元素，那么這個序列不是一個可能的出棧序列。如果棧為空，而且pop序列也全部被遍歷過，則說明這是一個可能的pop序列。下圖給出一個合理的pop序列的判斷過程。

在上圖中，(1)～(3)三步，由于棧頂元素不等于pop序列第一個元素3，因此，1，2，3依次入棧，當3入棧后，棧頂元素等于pop序列的第一個元素3，因此，第(4)步執(zhí)行3出棧，接下來指向第二個pop序列2，且棧頂元素等于pop序列的當前元素，因此，第(5)步執(zhí)行2出棧；接著由于棧頂元素4不等于當前pop序列5，因此，接下來(6)和(7)兩步分別執(zhí)行4和5入棧；接著由于棧頂元素5等于pop序列的當前值，因此，第(8)步執(zhí)行5出棧，接下來(9)和(10)兩步棧項元素都等于當前pop序列的元素，因此，都執(zhí)行出棧操作。最后由于棧為空，同時pop序列都完成了遍歷，因此，{3，2，5，4，1}是一個合理的出棧序列。

實現(xiàn)代碼如下：

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"棧已經(jīng)為空"

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序列"

程序的運行結(jié)果為：

32541是12345的一個pop序列

算法性能分析：

這種方法在處理一個合理的pop序列的時候需要操作的次數(shù)最多，即把push序列進行一次壓棧和出棧操作，操作次數(shù)為2N，因此，時間復雜度為O(N)，此外，這種方法使用了額外的?？臻g，因此，空間復雜度為O(N)。[考點]如何根據(jù)入棧序列判斷可能的出棧序列

5.

如何用O(1)的時間復雜度求棧中最小元素正確答案：由于棧具有后進先出的特點，因此，push和pop只需要對棧頂元素進行操作。如果使用上述的實現(xiàn)方式，只能訪問到棧頂?shù)脑?，無法得到棧中最小的元素。當然，可以用另外一個變量來記錄棧底的位置，通過遍歷棧中所有的元素找出最小值，但是這種方法的時間復雜度為O(N)，那么如何才能用O(1)的時間復雜度求出棧中最小的元素呢?

在算法設(shè)計中，經(jīng)常會采用空間換取時間的方式來提高時間復雜度，也就是說，采用額外的存儲空間來降低操作的時間復雜度。具體而言，在實現(xiàn)的時候使用兩個棧結(jié)構(gòu)，一個棧用來存儲數(shù)據(jù)，另外一個棧用來存儲棧的最小元素。實現(xiàn)思路如下：如果當前入棧的元素比原來棧中的最小值還小，則把這個值壓入保存最小元素的棧中；在出棧的時候，如果當前出棧的元素恰好為當前棧中的最小值，保存最小值的棧頂元素也出棧，使得當前最小值變?yōu)楫斍白钚≈等霔Ｖ暗哪莻€最小值。為了簡單起見，可以在棧中保存int類型。

實現(xiàn)代碼如下：

#模擬棧

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.