當前位置:成語大全網 - 新華字典 - 單棧排序與雙棧排序

單棧排序與雙棧排序

單棧排序

Tom最近在研究壹個有趣的排序問題:有壹個1~n的輸入序列和1個棧S,Tom希望借助以下2種操作實現將輸入序列升序排序。

操作a:如果輸入序列不為空,將第壹個元素壓入棧S1

操作b:如果棧S1不為空,將S1棧頂元素彈出至輸出序列

如果壹個1-n的排列P可以通過壹系列操作使得輸出序列為1,2,…,(n-1),n,Tom就稱P是壹個“可單棧排序排列”。

輸入第壹行是壹個整數n。第二行有n個用空格隔開的正整數,構成壹個1~n的排列。

輸出輸出文件***壹行,如果輸入的排列不是“可單棧排序排列”,輸出數字0;否則輸出字典序最小的操作序列,每兩個操作之間用空格隔開,行尾沒有空格。

------------------------------

定理:考慮對於任意兩個數q[i]和q[j],它們不能壓入同壹個棧中的充要條件: 存在壹個k,使得i<j<k且q[k]<q[i]<q[j]。

充分性證明:即如果滿足上述條件,那麽q[i]和q[j]壹定不能壓入同壹個棧:

反證法:假設這兩個數壓入了同壹個棧,那麽在壓入q[k]的時候棧內情況如下:

+----+

|q[j] |

+----+

|... |

+----+

|q[i] |

+----+

因為q[k]比q[i]和q[j]都小,所以很顯然,當q[k]沒有被彈出的時候,另兩個數也都不能被彈出(否則輸出序列的數字順序就不是1,2,3,…,n了)。而之後,無論其它的數字在什麽時候被彈出,q[j]總是會在q[i]之前彈出,而q[j]>q[i],這顯然是不正確的.

必要性證明:如果兩個數不可以壓入同壹個棧,那麽它們壹定滿足上述條件。

證明逆否命題:也就是"如果不滿足上述條件,那麽這兩個數壹定可以壓入同壹個棧." 不滿足上述條件有兩種情況:

情況1:對於任意i<j<k且q[i]<q[j],q[k]>q[i];

情況2:對於任意i<j,q[i]>q[j].

第壹種情況:在q[k]被壓入棧的時候,q[i]已經被彈出棧。那麽,q[k]不會對q[j]產生任何影響(這裏可能有點亂,因為看起來,q[j]<q[k]的時候是會有影響的,但實際上,這還需要另壹個數r,滿足j<k<r且 q[r]<q[j]<q[k],也就是證明充分性的時候所說的情況…而事實上我們現在並不考慮這個r,所以說q[k]對q[j]沒有影響)。 第二種情況:可以發現這其實就是壹個降序序列,所以所有數字都可以壓入同壹個棧. 這樣,原命題的逆否命題得證,所以原命題得證。

由此得出有解的判斷方法:對所有的數對(i,j)滿足1≤i<j≤n,檢查是否存在i<j<k滿足q[k]<q[i]。

var

n,top,i,j,k:longint;{序列長度為n,棧指針為top}

ans:string;{操作序列}

st:array [1..1000000] of longint;{棧}

begin

read(n);{讀序列長度}

top:=0;j:=1;ans:='';{棧和輸出序列空,從1開始輸出}

for i:=1 to n do{依次處理每個數字}

begin

read(k);ans:=ans+'a ';inc(top);st[top]:=k;{讀當前數字,進行a操作,該數字入棧}

while st[top]=j do {若棧頂滿足遞增要求,則出棧(進行b操作),下壹個輸出數字應+1,這壹過程反復進行,直至不滿足條件為止}

begin dec(top);inc(j);ans:=ans+'b 'end end;

if j<=n {若未輸出1¨n,則失敗退出;否則輸出操作序列}

then writeln(0)

else writeln(copy(ans,1,length(ans)-1))

end.

================================================================

雙棧排序

問題描述Tom最近在研究壹個有趣的排序問題。如圖所示,通過2個棧S1和S2,Tom希望借助以下4種操作實現將輸入序列升序排序。

操作a:如果輸入序列不為空,將第壹個元素壓入棧S1

操作b:如果棧S1不為空,將S1棧頂元素彈出至輸出序列

操作c:如果輸入序列不為空,將第壹個元素壓入棧S2

操作d:如果棧S2不為空,將S2棧頂元素彈出至輸出序列

+--------------------

s1 |

+--------------------

+--------------------

s2 |

+--------------------

如果壹個1~n的排列P可以通過壹系列操作使得輸出序列為1,2,…,(n-1),n,Tom就稱P是壹個“可雙棧排序排列”。

例如(1,3,2,4)就是壹個“可雙棧排序序列”,而(2,3,4,1)不是。下圖描述了壹個將(1,3,2,4)排序的操作序列:<a,c,c,b,a,d,d,b>

(這個圖網上有,妳自己找找吧)

當然,這樣的操作序列有可能有幾個,對於上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外壹個可行的操作序列。Tom希望知道其中字典序最小的操作序列是什麽。

輸入輸入文件twostack.in的第壹行是壹個整數n。第二行有n個用空格隔開的正整數,構成壹個1~n的排列。

輸出輸出文件twostack.out***壹行,如果輸入的排列不是“可雙棧排序排列”,輸出數字0;否則輸出字典序最小的操作序列,每兩個操作之間用空格隔開,行尾沒有空格。

========================================

簡述題意

有兩個隊列和兩個棧,分別命名為隊列1(q1),隊列2(q2),棧1(s1)和棧2(s2)。最初的時候,q2,s1和s2都為空,而q1中有n個數(n≤1000),為1~n的某個排列.現在支持如下四種操作: a操作,將 q1的首元素提取出並加入s1的棧頂; b操作,將s1的棧頂元素彈出並加入q2的隊列尾;

c操作,將 q1的首元素提取出並加入s2的棧頂; d操作,將s2的棧頂元素彈出並加入q2的隊列尾;請判斷,是否可以經過壹系列操作之後,使得q2中依次存儲著1,2,3,…,n.如果可以,求出字典序最小的壹個操作序列.

1、判斷是否有解和任意兩個數能否壓入同壹個棧

⑴、對任意兩個數q[i]和q[j],若存在壹個k,使得i<j<k且q[k]<q[i]<q[j],則這兩個數分別入s1棧和s2棧

⑵、將s1棧和s2棧中的數字組合成兩個頂點子集,同壹頂點子集內不會出現任何連邊,即不能壓入同壹個棧的所有數字被分到了兩個棧中。任兩個不在同壹棧的數字間連邊。此時我們只考慮檢查是否有解,所以只要化O(n)時間檢查這個圖是不是二分圖,就可以得知是否有解了。

======================================================

二分圖及二分圖的匹配

二分圖是壹種特殊類型的圖:圖中的頂點集被劃分成X與Y兩個子集,圖中每條邊的兩個端點壹定是壹個屬於X而另壹個屬於Y。二分圖的匹配是求邊的壹個子集,該子集中的任意兩條邊都沒有公***的端點。

======================================================

找字典序最小的解

1、確定每個數字入哪個棧,即構造二分圖

把二分圖染成1和2兩種顏色,染色為1的結點被壓入s1棧, 染色為2結點被壓入s2棧。為了字典序盡量小,我們希望讓編號小的結點優先壓入s1棧。 由於二分圖的不同連通分量之間的染色是互不影響的,所以可以每次選取壹個未染色的編號最小的結點,將它染色為1,並從它開始DFS染色,直到所有結點都被染色為止。這樣,我們就得到了每個結點應該壓入哪個棧中。

2、從數字1開始,按照目標序列的遞增順序構造操作序列

先處理入棧:按照搜索遞增順序每個頂點:若頂點i的顏色為1,則進行a操作,q1[i]入s1棧;若頂點i的顏色為2,則進行c操作,q1[i]入s2棧。

後處理出棧:若s1棧的棧頂元素為目標序列的當前數字k,則進行b操作,數字k出s1棧;若s2棧的棧頂元素為目標序列的當前數字k,則進行d操作,數字k出s2棧。

然後k+1,繼續模擬,直至k為n為止。

==========================================================

數據結構

var

a,b,head,next,point,color:array[0..2001]of longint;{初始序列為a(對應q1),後綴的最小值序列為b,其中b[i]=min{a[k]}(i<=k<=n);鄰接表的表首頂點為head,後繼指針為next,頂點序列為point,頂點的塗色序列為color}

s:array[1..2,0..1000]of longint;{s[1]棧,棧首指針為s[1,0];s[2]棧, 棧首指針為s[2,0]}

n,p,i,j,last:longint;{序列長度為n,當前應取數字為last}

procedure badend;{輸出失敗信息}

begin

writeln(0);close(output);halt;

end;

procedure addedge(a,b:longint);{(a,b)進入鄰接表}

var t:longint;

begin

inc(p);point[p]:=b;{增加頂點b}

if head[a]=0 {(a,b)進入鄰接表}

then head[a]:=p

else begin

t:=head[a];

while next[t]<>0 do t:=next[t];

next[t]:=p;

end;

end;

procedure dfs(now:longint);

var t:longint;

begin

t:=head[now];{搜索與頂點now相鄰的所有頂點}

while t<>0 do

begin

if color[point[t]]=0{若頂點now相鄰的頂點point[t]未塗色,則該頂點塗互補色,沿該頂點遞歸下去}

then begin

color[point[t]]:=3-color[now];dfs(point[t]);

end;

if color[point[t]]=color[now] then badend;{若頂點now與相鄰頂點point[t]塗相同色,則失敗退出}

t:=next[t];{訪問與頂點now相鄰的下壹個頂點}

end;

end;

begin

assign(input,'twostack.in');reset(input);{輸入文件讀準備}

assign(output,'twostack.out');rewrite(output);{輸出文件寫準備}

fillchar(s,sizeof(s),0);fillchar(a,sizeof(a),0);{兩棧空}

readln(n);{讀入排列}

for i:=1 to n do read(a[i]);

b[n+1]:=maxlongint;p:=0;

for i:=n downto 1 do{計算b[i]= }

begin

b[i]:=b[i+1];

if a[i]<b[i] then b[i]:=a[i];

end;

for i:=1 to n do

for j:=i+1 to n do

if (b[j+1]<a[i])and(a[i]<a[j]) {若a[i]和a[j]不能不能壓入同壹個棧,則(i,j)和(j,i)進入鄰接表}

then begin addedge(i,j);addedge(j,i);end;

for i:=1 to n do{所有未塗色的頂點塗顏色1,遞歸}

if color[i]=0 then begin color[i]:=1;dfs(i);end;

last:=1;{目標序列初始化}

for i:=1 to n do{模擬輸出序列}

begin

if color[i]=1 {a[i]入s[1]或s[2]棧}

then write('a ')

else write('c ');

inc(s[color[i],0]);s[color[i],s[color[i],0]]:=a[i];

while (s[1,s[1,0]]=last)or(s[2,s[2,0]]=last) do

begin{將s[1]或s[2]棧頂的數字last取出}

if s[1,s[1,0]]=last then begin write('b ');dec(s[1,0]);end;{將s[1]棧頂的last取出}

if s[2,s[2,0]]=last then begin write('d ');dec(s[2,0]);end;{將s[2]棧頂的last取出}

inc(last);{按遞增要求取下壹個數字}

end;

end;

close(input);close(output);{關閉輸入輸出文件}

end.