棧和隊列

棧：棧上的Insert操作稱為壓入（PUSH），Delete操作稱為彈出（POP）。

可以用一個數組S[1..n]來實現一個最多可容納n個元素的棧。該數組有一個屬性S.top，它指向最新插入的元素。棧中包含的元素為S[1..S.top]，其中S[1]是棧底元素，S[S.top]是棧頂元素。當S.top=0時，棧中不包含任何元素，棧空。當S.top=n時，棧滿。

Stack-empty(S)if S.top == 0 return Trueelse return False

Push(S,x)S.top = S.top + 1S[S.top] = x

Pop(S)if Stack-empty(S) error underflowelse S.top = S.top - 1 return S[S.top + 1]

隊列：隊列上的Insert操作稱為入隊列（EnQueue），delete操作稱為出隊列（DeQueue）。

可以用數組Q[1..n]來實現一個最多容納n-1個元素的隊列，該隊列有一個屬性Q.head指向隊頭元素，屬性Q.tail指向下一個新元素將要插入的位置。當Q.head = Q.tail時，隊列為空。當Q.head = Q.tail + 1時，隊列為滿。隊列中的元素存放在位置，Q.head，Q.head+1，Q.head+2...Q.tail-1，並在最後的位置環繞。

EnQueue(Q,x)Q[Q.tail] = xif Q.tail == Q.length Q.tail = 1else Q.tail = Q.tail + 1

DeQueue(Q)x = Q[Q.head]if Q.head = Q.length Q.head = 1else Q.head = Q.head + 1return x

推薦閱讀：