熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第三章 答案[21]

2013-11-15 15:00:15  來源: 數據結構 

  [題目分析]棧的特點是後進先出隊列的特點是先進先出所以用兩個棧s和s模擬一個隊列時s作輸入棧逐個元素壓棧以此模擬隊列元素的入隊當需要出隊時將棧s退棧並逐個壓入棧ss中最先入棧的元素在s中處於棧頂s退棧相當於隊列的出隊實現了先進先出顯然只有棧s為空且s也為空才算是隊列空

  () int enqueue(stack selemtp x)
  //s是容量為n的棧棧中元素類型是elemtp本算法將x入棧若入棧成功返回否則返回
  {if(top==n && !Sempty(s))       //top是棧s的棧頂指針是全局變量
  {printf(棧滿);return();}  //s滿s非空這時s不能再入棧
  if(top==n && Sempty(s))        //若s為空先將s退棧元素再壓棧到s
  {while(!Sempty(s)) {POP(sx);PUSH(sx);}
  PUSH(sx); return();  //x入棧實現了隊列元素的入隊
  }

  () void dequeue(stack ss)
  //s是輸出棧本算法將s棧頂元素退棧實現隊列元素的出隊
  {if(!Sempty(s))        //棧s不空則直接出隊
  {POP(sx);   printf(出隊元素為x);  }
  else                   //處理s空棧
  if(Sempty(s)) {printf(隊列空);exit();}//若輸入棧也為空則判定隊空
  else                 //先將棧s倒入s再作出隊操作
  {while(!Sempty(s)) {POP(sx);PUSH(sx);}
  POP(sx);        //s退棧相當隊列出隊
  printf(出隊元素x);
  }
  }//結束算法dequue

  () int queue_empty()
  //本算法判用棧s和s模擬的隊列是否為空
  {if(Sempty(s)&&Sempty(s))  return();//隊列空
  else return();                       //隊列不空
  }

  [算法討論]算法中假定棧s和棧s容量相同出隊從棧s當s為空時若s不空則將s倒入s再出棧入隊在s當s滿後若s則將s倒入s之後再入隊因此隊列的容量為兩棧容量之和元素從棧s倒入s必須在s空的情況下才能進行即在要求出隊操作時若s則不論s元素多少(只要不空)就要全部倒入s

  類似本題敘述的其它題的解答

  該題同上面題本質相同只有敘述不同請參考上題答案

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/22700.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.