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); //若要回傳資料則加
}
}
}