\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2018年1月11日 星期四

[ Implement Queue using Stacks ] 用堆疊實作佇列

一般在C++ STL中queue都是用deque實作的,而deque用和vector類似的倍增法來實作(稍微多了一些操作導致常數有點大但是每次操作時間較為平均),雖然夠用但有些時候這不是一個好選擇。
大二資料結構期中考時,考了一題叫你用stack實作queue的方法,我那時候想了一下想了一個超帥的作法,需要用到兩個stack,我把它成為stack A和B。
  • push:
    push時直接把資料push進B中,$\ord{1}$
  • pop:
    這是個問題,我們把A的top當成是queue的front,所以直接把A pop就可以了,如果A是empty的話,就把B的資料依序pop然後push進A中,在進行該操作,均攤$\ord{1}$
  • front:
    如pop所述,把A的top當成是queue的front,如果A是empty再另做處理,$\ord{1}$
  • back:
    和front相反,把B的top當成是queue的back,如果B是empty再另做處理,$\ord{1}$
以下為實作過程,以c++ vector代替stack: