切換
舊版
前往
大廳
主題

ZeroJudge - e447: queue 練習 解題心得

Not In My Back Yard | 2019-10-06 23:28:17 | 巴幣 0 | 人氣 646

題目連結:


題目大意:
有三種指令:
1 x ,在隊伍尾端加入整數 x 。(1 ≦ x ≦ 10 ^ 9)
2,輸出最前端的元素。隊伍中沒有任何元素的話,輸出「-1」。
3,刪除最前端的元素。隊伍中沒有任何元素的話,請無視該指令。

給定一正整數 N (1 ≦ N ≦ 10 ^ 5),代表接著有 N 列的輸入,每列都是上面三種指令的其中一種。請實作一個可支援這三種指令的資料結構(即實作 Queue,佇列)。



範例輸入:
13
1 1
1 2
1 3
2
3
3
2
1 4
3
2
3
3
2


範例輸出:
1
3
4
-1


解題思維:
一個佇列(Queue)需要兩個指標。一個是 front,負責指向最前面的元素;另一個是 rear,負責指向最後面的元素。且每個節點各自還需要有可以指向「下一個」節點的指標。

當 front = rear = 空指標時,代表這個佇列沒有元素。

插入元素到空佇列時,需要先新增一個節點,再讓 front 、 rear 過去指;如果佇列有元素,那就新增一個節點讓原本的 rear 指到的節點之指標指過去這個新節點,最後再讓 rear 指過去。

輸出只要判斷是不是空的。如果不是就輸出 front 指到的節點之數值;反之,忽略這個指令。

刪除最前面的元素,也要先判斷是否為空。為空就忽略此指令;不然,就讓 front 指向原本 front 指到的節點的「下一個」並釋放掉原本的節點之儲存空間。而當 front 變成空指標(下一個節點為空),代表這個佇列空了,所以 rear 也要設成空指標。

以上就是實作的方法、細節。

當然,C++ 的話也可以直接用內建的 queue 直接完成這題的要求。只是失去了本題的意義。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作