# 資結 第三章:stack與Queue
[toc]
## stack定義、應用、製作
### 定義
是一個具有LIFO(Last-In-First-Out)性質之有序串列

### 製作
* Create
* IsFull
* IsEmpty
* push
* pop

### 製作方法
1.利用array製作
宣告:
(1)S: array[1...n] of items;
(2)Top: int=0;

push(s,item)
{
    if(top == n) then return "full";
    else
    {
        Top = Top + 1;
        S[Top] = item;
    }

}

pop(s)
{
    if(isempty(s)) then return "empty";
    else
    {
        item = S[Top];
        Top = Top - 1;
        return item;
    }
}

<font color="red">不管是push還是pop,時間都是花O(n)</font>

2.利用link list製作
(1) Node structure如下:
|Data|Link|
|---|---|
Data欄:存資料
Link欄:pointer(指標)指向下一個Node位置

Push(s,item)
{
    new(t);
    t->Data = item;
    t->Link = Top;
    Top = t;
}

Pop(s)
{
    if(Top == "Nil") return "empty";
    else
    {
        t = Top;            //指向最上層的空間,因top要往下指,需要一個人去接住沒人指的地方
        item = Top->Data;
        Top = Top->Link;
        free(t);
    }
}

<font color="red">不管是push還是pop,時間都是花O(1)</font>

## stack permutation
### 定義
將n個Data,依序push入stack中,但在過程中,可以穿插執行合法的pop,輸出Data,則n個Data輸出之排列組合,稱之

例如:a,b,c三個data之stack permutation為五種,cab不行

<font color="red">算法=$\dfrac{1}{n+1}{2n\choose n}$</font>

|n|數目|
|--|--|
|3|5|
|4|14|
|5|42|
|6|132|

同義:
[1] n個nodes可以形成的不同Binary tree結構
[2] n個"("及n個")"的合法配對數
[3] <font color="red">n+1</font>個矩陣相乘之乘法配對組合順序

### infix,postfix,prefix之轉接
* infix:中序
缺點:compiler不易直接求算infix之值,需考量優先權,結合性,導致可能來回多次式子掃描

* postfix:後序
優點:compiler只須由左而右掃描式子一次,即可求出結果

* prefix:前序
優點:compiler只須由右而左掃描式子一次,即可求出成果
缺點:infix轉prefix需要<font color="red">2</font>個stacks支持,但infix轉postfix只需一個stack支持

### 計算題型
* infix轉postfix
* infix轉prefix
* postfix轉infix
* prefix轉infix
* infix轉posfix之algorithm
* postfix evaluation algorithm
* prefix evaluation algorithm(少考)
* infix轉prefix algorithm(少考)

### compiler之parsing using stack
* ()是否正確
* 輸入字串是否符合回文
* 判斷輸入字串是否符合a^n^b^n^(少考)

## Queue(佇列)
### 定義
是一個具有FIFO性質的有序串列

### 應用
* os中各種queue
* buffer設計
* 系統效能評估模擬
* 圖形的BFS
* Binary tree的level-order traversal
* 日常中排隊行為

### 製作
一、利用array
* 利用linear array
方法很爛，很浪費空間
* 利用circular array
最多利用n-1格
* 利用circular array
最多利用n格

法二:

Enqueue(Q,item)
{
    rear = (rear+1)%n;
    if(rear == front) then return "full";
    else
    {
        item = Q[rear];
    }
}

Dequeue(Q)
{
    if(front == rear) then return "empty";
    else
    {
        front = (front+1)%n;
        item = Q[front];
        return item;
    }
}

法三:

Enqueue(Q,item)
{
    if(rear == front)and(Tag==True)then return "Q滿"
    else
    {
        rear = (rear+1)%n;
        Q[rear] = item;
        if(rear == front) then Tag = True;
    }
}

Dequeue(Q)
{
    if(rear == front)and(Tag==False)then return "Q空"
    else
    {
        front = (front+1)%n;
        item = Q[front];
        if(rear == front) then Tag = False;
        return item;
    }
}

<font color=red>front下的那一格不用,因此每次要pop都要先加一</font>

二、利用link list製作
* single link list

Enqueue(Q,item)
{
    new(t);
    t -> data = item;
    if(Front == Nil) then Front = t;
    else
    {
        Rear->link = t;
    }
    Rear = t;
}

Dequeue(item)
{
    if(front == Nil)then return "Q空";
    else
    {
        t = Front;
        item = Front->Data;
        Front = Front->link;
        if(front == Nil) then Rear=Nil;
        Free(t);
        return item;        
    }
}

* circular link list(環狀串列)做Queue

Enqueue(Q,item)
{
    new(t);
    t->Data = item;
    if(rear == Nil) then rear = t;
    else
    {
        t->link = rear->link;
        rear->link = t;
    }
    rear = t;
}

Dequeue(Q)
{
    if(rear == Nil) then return "Q空";
    else
    {
        if(rear->link == rear)
        {
            t = rear;
            item = rear->Data;
            rear = Nil;
            free(t);
            return item;
        }
        else
        {
            t = rear->link;
            item = (rear->link)->Data;
            rear->link = (rear->link)->link;
            free(t);
            return item;
        }
    }
}

### Queue的種類
* FIFO Queue
* Priority Queue
* Double-ended Queue
* Double-ended priority Queue
* 製作此Queue的最合適data structure有:
[1]min-max heap
[2]Deap
[3]SMMH

## Stack與Queue之相互製作
一、使用stack製作Queue
做法:利用2個stacks:S與I

Enqueue(Q,item)
{
    push(S,item);
}

Dequeue(item)
{
    if(Isempty(T)then)
        if(Isempty(S))then
            return "Q空"
        else
        {
            while(NOT Isempty(S))
            {
                x=pop(S);
                push(T,x);  //全部在倒入另一個袋子裡
            }
        }
    item=pop(T);
    return item;
}

<font color=red>Enqueue Time:O(1)</font>
Dequeue Time:
大部分情況(T不等於空)是O(1)
少部份情況(T等於空,S不等於空)是O(n)
<font color=red>以amortized Time(cost)=>O(1)</font>

二、利用Queue做stack

push(s,item)
{
    Enqueue(Q,item);
}

pop(s)
{
    if(Isempty(Q)then return "S空");
    else
    {
        n=Queue中元素個數;
        for i=1 to (n-1) do
        {
            x=Dequeue(Q);
            Enqueue(Q,x);
        }
        item=Dequeue(Q);
        return item;
    }
}

將queue中所有元素取出來重新加入=>爛方法

## 額外queue問題
假設Queue是用circular Array製作(最多利用n-1格)
如何以front,rear,n表示Queue中元素個數?
=><font color=red>(rear-front+n)%n</font>

###### tags: `data structure` `chp3` `stack` `queue`