stack queue

stack:LIFO(last in first out,後進先出)
說明:一種有序串列,但限制插入運作和刪除運作而在top(頂端)進行,也就是最後插入的資料會先被移走
應用:副程式的呼叫與返回,遞迴副程式的處理,運算式的計算...
主要運作:宣告一個空堆疊,插入,取出,判別是否為空,回傳頂端資料...
ps:若將佇列的插入運作和刪除運作都發生在尾端,及可達到堆疊的效果

鏈結表示的運作
void push(int x){
 struct node *temp;
 temp=(struct node *)malloc(sizeof(struct node)); //產生新節點
 temp->data=x;
 temp->next=top; //將新節點指向top所指節點
 top=temp; //將top變數改成指向新節點
}
int pop(void){
 int x; struct node *temp;
 if(top==null){ printf(stack is empty); } //判斷是否為空
 else{
  temp=top; //將temp指向top所指節點
  top=temp->next; //將top節點變成的指向下一個節點
  x=temp->data;
  free(temp); //歸還temp所指節點
 }
 return(x);
}

前序,中序,後序轉換及計算
中序轉後序
ex:a+e*c/d-e
1, ((a+((e*c)/d))-e) //依運算順序加括號
2 , aec*d/+e- //將各運算子移到對應的右括號

中序轉前序演算法
1,將中序運算式先反轉,達到由後向前處理的順序
2,在尾端放上一結束符號
3,將值取出一直到碰到結束符號
4,假如值=數字,則將數字放入result的堆疊中
假如值=運算符號,則將運算符號放入expr的堆疊中


................


queue:FIFO(first in first out,先進先出)
說明:一種有序串列,但限制插入運作在rear(尾端),而刪除運作在front(前端),也就是第一個插入的資料會先被移走
應用:工作元的規畫,輸入輸出要求的處理,電腦模擬系統的執行

ps:
priority queue
在fifo中在增加一個priority元素
用途:提供insert,delete,search運作

用循序表示法來表示一個佇列
事先宣告:
datatype queue[1-n]; //宣告能存放n個資料的陣列
int front=1; //指向要取出資料的位置
int rear=1; //指向要插入資料的位置
使用線性佇列時:
rear=rear+1 //插入資料時+1
front=front+1 //取出資料時+1
當front=rear時表empty
而rear=n時表示己滿,若左邊有空間則將資料左移,但這方法十分沒效率
使用環狀佇列circular時:
rear=(rear mod n)+1 //插入資料時+1,但當rear為n時,下一個插入資料的位置就會在最左邊
front=(front mod n)+1 //取出資料時+1,但front的值到n後會自動變回1
當front=rear時表empty
判斷是否有滿的方法:
1,只允許n-1個資料放入佇列,也就是(rear mod n)+1==front時則表示滿
2,加入count變數,表示目前佇列內資料個數

queue循序表示法
插入資料
void insert(int x){
 temp=(rear mod n)+1; //1將rear除n取餘數+1
 if(temp==front){printf("queue is full");} //2,判斷是否己滿,若滿則實際資料只有n-1個,並且不要將rear加1(因為取資料時會被誤判為空)
 else{
  rear=temp; //若沒滿才可將rear加1
  queue[rear]=x; //3將資料存放到rear存指位置
 }
}

取出資料
void delete(){
 if(rear==front){printr("queue is empty");} //1判斷是否為空
 else{
  front=(front mod n)+1; //2將front除n取餘數+1
  return(queue[front]); //3取出資料
 }
}

//環狀queue的加入資料,p指最晚加入節點,因為是環狀所以p->link則指到第一個加入的節點
void add(int x){
 struct node *temp;
 temp=(struct node *)malloc(sizeof(struct node)); //產生新節點
 temp->data=x;
 if(p==nil){ temp->link=temp;} //若queue為空,則指向自己
 else{
  temp->link=p->link; //讓新節點temp指到第一個加入的節點
  p->link=temp; //讓原本最晚加入的節點指到新節點
 }
 p=temp; //記住最後一個節點
}

//環狀queue刪除或取出資料
int delete(){
 struct node *temp;int x;
 if(p==nil){print("the quese is empty") ;}
 else{
  temp=p->link; //把最前面的節點給temp節點
  x=temp->data; //若要回傳資料則加
  if(temp==p){p=nil;} //若只有一個節點,等下就會消失
  else{
   p->link=temp->link; //將最前面節點的下個節點位置給最後節點
   free(temp);
   return(x); //若要回傳資料則加
  }
 }
}


2007-03-05 18:56:12發表 0000-00-00 00:00:00修改   

數據分析
程式開發
計算機組織與結構
資料結構與演算法

Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統
數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net