---
tags: 資料結構,
---
# 資料結構 第三章 堆疊與佇列
## 一、堆疊抽象資料型態(The Stack Abstract Data Type)
### (一)定義堆疊操作
【變數設定】
for all stack belong to Stack, item belong to element, max_stack_size belong to positive integer

1、Stack Create(max_stack_size)：創造一個空的堆疊（容量為max_stack_size）。
2、Boolean IsFull(stack, max_stack_size)：判斷堆疊是否滿了，滿了回傳True，否則為False。
3、Boolean IsEmpty(stack)：判斷堆疊是否為空，空了回傳True（判斷可用空間＝最大空間），否則為False。
4、Stack Add(stack, item)：前提假設堆疊未滿，將Data插入堆疊最上端(Top)，前提假設不成立(代表堆疊已滿)則無法再插入Data並回傳堆疊已滿(Stack_Full)。
5、Element Delete(stack)：前提假設堆疊不為空，則將pop堆疊在上端的Data，前提假設不成立(堆疊為空)無資料刪除，故回傳Stack_Empty。
### (二)堆疊插入刪除圖式如下：

### (三)呼叫函式後系統使用堆疊(System stack after function call)
系統將紀錄參數值、區域變數、返回位址存入堆疊

### (四)程式碼(插入、刪除)
void add(int *top,element item)
{
if(*top >= Max_Stack_Size-1) //第一格index為零
{
stack_full();
return;
}
stack[++*top] = item;
}

void delete(int *top)
{
if(*top == -1) //若迴圈下無{}則只會執行一行
return stack_empty();
return stack[(*top)--];
}

## 二、佇列抽象資料型態(The Queue Abstract Data Type)
### (一)定義佇列操作
【變數設定】
for all queue belong to Queue, item belong to element, max_queue_size belong to positive integer

1、Queue CreateQ(max_queue_size)：創造一個佇列（容量為max_queue_size）。
2、Boolean IsFullQ(queue, max_queue_size)：判斷佇列是否滿了（資料個數＝最大空間），滿了回傳Queue_Full，否則回傳False。
3、Boolean IsEmptyQ(queue)：判斷佇列是否為空（可用空間＝最大空間），是則回傳True，否則回傳False。
4、Queue AddQ(queue, item)：前提假設佇列不為滿，則將Data由前端(front)加入佇列中，前提假設不成立則回傳Queue_Full。
5、Element DeleteQ(queue)：前提假設佇列不為空，則將Data由尾端(Rear)移出佇列。
### (二)佇列插入刪除圖式如下：

void addq(int *rear, element item)
{
if(*rear == Max_Queue_Size-1)
{
queue_full();
return;
}
queue[++*rear]= item;
}
element deleteq(int *front, int rear)
{
if(*front == rear)
return queue_empty();
return queue[++*front];
}
延伸問題：
當front = -1 時，代表queue為空尚有n個空間，當rear == n-1時，queue不一定就是滿的，若先執行n次插入再執行n次刪除(如下圖所示)。

### （三）佇列改善（環狀佇列）圖示如下：

#### 特色:
1.Full和empty條件相同
2.Queue[0...n-1]中有n格空間,但需要犧牲一格空間，故能使用空間只有n-1個

### (程式碼)
【環狀佇列】
void addq(int front, int *rear, element item)
{
*rear = (*rear+1) % Max_Queue_Size;
if (front == *rear)
{
queue_full(rear);
return;
}
queue[*rear] = item;
}
element deleteq(int *front, int rear)
{
element item;
if(*front == rear)
return queue_empty();
*front = (*front+1) % Max_Queue_Size;
return queue[*front];
}

## 三、迷宮問題(A Mazing Problem)
### (一)迷宮示意圖

將迷宮想像成矩陣，從起點(左上)走至終點(右下)，每次行走時要判斷往哪個方向走，如下圖所示可分成八個方位。


每次行走時記錄下位置，若走到死路無法繼續前進(則pop Stack)返回至原本的點，換其他路徑繼續前進。

### (二)程式碼

#define typedef
MAX-STACK-SIZE 100
struct
{
short int row;
short int col;
short int dir;
}
element;
element stack[MAX-STACK-SIZE];

initialize a stack to the maze's entrance coordinates and direction to north;

while (stack is not empty)
{
<row,col,dir> = delete from top of stack;
while((there are more moves from current position))
{
<next_row, next_col> = = coordinates of next move;
dir = direction of move;
if ( (next_row == EXIT_ROW) && (next_col == EXIT-COL))
success;
if((maze[next_row][next_col] == 0 && mark[next_row][next_col] == 0))
{
mark[next—row] [next—col] = 1;
add <row,col,dir> to the top of the stack;
row = next_row;
col = next_col;
dir = north;

}
}
}
## 四、值的表示方式(Evaluation of Expressions)
我們從小使用的運算皆是中置式，舉例如下：

中置式不論是要轉給電腦方便運算的後置式等，運算子的優先權高低(含左右結合表)如下圖：

### (一)後置式表示法(Evaluatng Postfix Expressions)
以上圖為例後置式表示對照圖如下:


補充：前置式

| Infix | Postfix
| -------- | --------|
| 2+3*4 | +2*34|
|a*b+5|+*ab5
|(1+2)*7|*+127|
|a*b/c|/*abc|
|((a/(b-c+d))*(e-a)*c)|**/a+ -bcd-eac
|a/b-c+d*e-a*c|-+ -/abc*ac

### (二)中置式轉後置式(Infix to Postfix)
中置式轉後置式，利用stack操作，下圖為stack轉換過程：


細分解:
將(a+b*c)轉成後置式

| 步驟 | step1 | step2 | step3 | step4 | step5 | step6 | step7 |
| -------- | ---------------------------------------------------------- | -------- |:-----------------------:| ----- | ----- | ----- | ----- |
| scan | scan"(" ：左括號在stack外優先權最高，但在stack內優先權最低 | scan"a" | scan"+"　優先權：+ > ( | sacn"b" | scan"*" | scan"c" | scan")" |
| 運作 | push "("置stack | print"a" |push"+"置stack | print"b" |push"*"置satck　優先權：* > + | print"c" | 遇到")"將stack 連續pop直到遇到"("並將pop出來的值印出 |
| 目前輸出 | | a | a | ab | ab |abc | abc*+|

【程式碼】
int eval(void)
{
precedence token;
char symbol;
int op1, op2;
int n = 0;
int top = -1;
token = get_token(&symbol, &n);
while(token != eos)
{
if (token== operand)
add(&top, symbol_'0')
else
{
return result to the stack
op2 = delete(&top);
op1 = delete(&top);
switch(token)
{
case "+":add(&top, op1+op2);
break;
case "-":add(&top, op1-op2);
break;
case "*":add(&top, op1*op2);
case "/":add(&top, op1/op2)
case "%":add(&top, op1%op2)
}
}
token = get_token(&symbol, &n);
}
return delete(&top);
}

precedence get_token(char *symbol, int *n)
{
*symbol = expr[(*n)++];
switch(*symbol)
{
case "(": return lparen;
case ")": return rparen;
case "+": return plus;
case "-": return minus;
case "/": return divide;
case "*": return times;
case "%": return mod;
case " ": return eos;
default : return operand;

}
}

## 五、多堆疊與佇列(Multiple Stacks And Queues)

### (一)使用stack製作Queue

1.create

createQ(n)
{
createS(n);
}
---

2.addQ

AddQ(Q, item)
{
if(isFull(s))
print "Queue滿";
else
push(s,item);
}

#概念:將Stack的Top視為Queue的rear
---

3.delete

Delete(Q)
{
if(isEmpty(s))
print "Queue為空";
else
{
T:stack;
while(Not Isempty(s))
{
y=pop(s);
push(T,y);
}
item = Pop(T);
while(Not Isempty(T))do
{
y=Pop(T);
push(S,y);
}
}
}
---
### (二)利用Queue製作Stack

1.create

create S(n)
{
create Q(n)
}
---
2.push

push(S, item)
{
if (is Full (Q))
return "stack已滿"
else
Add Q(Q,item)
}
---
3.pop

pop(s)
{
if (is empty(Q))
return "stack是空的"
else
{
n = rear-front+1;
for(i=1 n-1 )
{
y=DeleteQ(Q);
add Q(Q,y);
}
item = deleteQ(Q);
}
}

> 參考資料:Fundamentals of Data Structures in C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed