在不考慮空間大小的前提下，你可以隨意的 push 一些東西進去 stack 當中；而在 stack 裡有東西的情況下，你也可以隨意的 pop 一些東西出來；那麼，如果給你那「一些東西」，讓你依序的 push 進 stack，並隨意的在 stack 不空的時候 pop 出來，直到所有東西都被 push 與 pop 各一次，則是否能製造出某些特定順序，又有某些順序不可能出現呢？

要做這個檢查其實非常的簡單，為了方便稱呼，以下稱讓你依序 push 進去的序列是 S_push，而等待被檢測是否可由這一連串 push/pop 的操作製造出來的序列為 S_pop；並且，以下敘述僅考慮所有元素皆不相同的狀況。

首先，由於若 S_pop 真的可以被這一連串 push/pop 的操作製造出來，則其首個元素 S_pop[0] 一定是最先被 pop 出來的；因此我們需先將 S_push 依次的 push 進 stack，直到看到與 S_pop[0] 相等的元素為止，然後將它 pop 出來。

接著，由於若 S_pop 真的可以被這一連串 push/pop 的操作製造出來，則 S_pop[1] 只可能出現在 stack 頂端，或者 S_push 當中還沒被 push 進去的部分；如果是前者的話，我們就從 stack pop 一個元素出來；如果是後者的話，就跟前一步一樣繼續把 S_push 依次的 push 進 stack，直到看到與 S_pop[1] 相等的元素為止，然後將它 pop 出來。後續的步驟可以依此類推，當然若你發現前述兩種情況都不符合，則代表 S_pop 無法經由對 S_push 做最一連串的 push/pop 來得到。

上述的步驟的實作如下，為了方便，範例中會把 S_push 固定為「ABCDE」，但此演算法不論 S_push 是否遵守特定順序，皆能正常運作，你也可以試著修改，或者直接將 S_push 變成函式的參數：

def is_spop_valid(s_pop):
	s_push = 'ABCDE'
	stack = []
	i_push = 0
	n = len(s_push)
	for i_pop in range(n):
		while i_push < n and (len(stack) == 0 or stack[-1] != s_pop[i_pop]):
			stack.append(s_push[i_push])
			i_push += 1
			if i_push == n:
				break
		if stack[-1] == s_pop[i_pop]:
			stack.pop()
		else:
			return False
	return True


if __name__ == '__main__':
	print(is_spop_valid('CABDE'))

Note: 請自己在 for 迴圈的開頭或某處加入一些 print，來確認迴圈每一輪的 stack 內容。

雖然 for 跟 while 搭配起來，像是巢狀迴圈的 O(n²)，但由於每個元素只會被 push 和 pop 最多各一遍，而 push 及 pop 都是 O(1)，因此演算法整體的時間複雜度是 O(n)。此外，你如果想對這個問題做更多的嘗試，也可以參考 LeetCode 的 946. Validate Stack Sequences。