iT邦幫忙

1

【小馬的資結演算法秘笈】(5) stack與queue

今天要再介紹兩種實用的資料結構- stack與queue

stack- 最緊急的事情優先做

stack是一種先進後出的結構,
我們稱為FILO(First In, Last Out)的結構

它就像你把棉被整整齊齊的疊在衣櫃一樣,
如果你想要把放在最下層的棉被拿出來,
必須要先把放在上層的棉被拿出來,
才有辦法把下層的棉被拿出來

即是說,最後放進去stack裡面的東西,是最優先被處理的
其實日常生活也有類似這種stack的情形,
人會最優先處理最後發生的事
做事做到一半時,突然一件更緊急的事發生,
這時便會先做緊急的事,再回頭做原來的事項

例如:

  • 小明讀書讀到一半,突然接到暗戀同學打的電話,就先去接電話再回來讀書
  • 小華打電動打到一半,突然很想上廁所,只好先去上廁所再回來打電動

讀者可以想一想,日常生活中有沒有什麼情況也是屬於stack呢?

stack的程式碼實作(以array實作)

我們會希望stack有三個函數pop, push, 與top
push就是往stack的最上面疊放資料,
pop就是把stack最上面的資料拿出來(如果沒資料則不做事),
top則是查看stack最上面的資料是多少

#include <iostream>
using namespace std;

class Stack{
private:
    const int max_sz; //預設stack的最大容量
    int currunt_sz = 0; //目前Stack裡有幾個元素
    int *arr;
public:
    Stack():max_sz(500){arr = new int[max_sz];};
    Stack(int sz):max_sz(sz){arr = new int[max_sz];};
    void push(int data);
    int pop();
    int top();
    int size();
    void Print(); //印出stack有幾個元素及最上層元素,用來debug
};

void Stack::push(int data){
    arr[currunt_sz]=data;
    currunt_sz++;
}


int Stack::pop(){
    int top = currunt_sz>0?arr[currunt_sz-1]:0;
    currunt_sz--;
    return top;
}

int Stack::top(){
    return currunt_sz>0?arr[currunt_sz-1]:0;
}

int Stack::size(){
    return currunt_sz;
}

void Stack::Print(){
    if(currunt_sz>0){
        std::cout << "stack大小: "<< size() << std::endl;
        std::cout << "stack最上面的元素為: "<< top() << std::endl;
    }
    else{
        std::cout << "stack現在是空的" << std::endl;
    }
}
    
int main()
{
    Stack s;
    s.Print();
    s.push(15);
    s.Print();
    s.push(26);
    s.Print();
    s.pop();
    s.Print();
    return 0;
}

queue- 按照事情的先後順序做

queue則是一種先進先出的結構,
我們稱為FIFO(First In, Fisrt Out)的結構

queue其實非常好理解,
queue就好比日常生活在大賣場排隊結帳,
隊伍第一個人服務員就會優先幫他結帳

最先放進去queue裡面的東西,是最優先被處理的,
在日常生活可能比較常見這種模式,例如:

  • 期限較近的考試優先準備

queue的程式碼實作(以array實作)

我們會希望queue有三個函數enqueue, dequeue, 與front
enqueue就是往queue的尾巴放資料,
dequeue就是把queue最前面的資料拿出來(如果沒資料則不做事),
front則是查看queue最前面的資料是多少

#include <iostream>
using namespace std;

class Queue{
private:
    const int max_sz; //預設Queue的最大容量(為了能判斷Queue為空的狀況,若max_sz=500,實際上最多容納499個元素)
    int head = 0, tail = 0; //目前隊伍頭和尾的編號,兩者相等Queue為空
    int *arr;
public:
    Queue():max_sz(500){arr = new int[max_sz];};
    Queue(int sz):max_sz(sz){arr = new int[max_sz];};
    void enqueue(int data);//放資料到queue的尾端,若queue已滿則不做事
    void dequeue();
    int front();
    int size();
    void Print(); //印出Queue裡面有幾個元素及最前方元素,再印出所有元素,用來debug
};


void Queue::enqueue(int data){
    if(size()==max_sz-1){
        std::cout << "警告: 嘗試添加數字但queue已達最大容量"<< std::endl;
        return;
    }
    arr[tail]=data;
    tail= (tail+1)%max_sz;
}

void Queue::dequeue(){
    if(head!= tail)
        head= (head+1)%max_sz;
}

int Queue::front(){
    return head!= tail? arr[head]:-1;
}

int Queue::size(){
    return (tail-head+max_sz)%max_sz;
}

void Queue::Print(){
    if(size()==0){
        std::cout << "queue現在是空的" << std::endl;
    }
    else{
        std::cout << "queue大小: "<< size() << ", queue最前方的元素為: "<< front() << std::endl;
        std::cout << "queue裡面的元素: ";
        for(int i=0; i<size(); i++){
            std::cout << arr[(head+i)%max_sz] <<" ";
        }
        std::cout << std::endl;
    }
}
 
int main()
{
    Queue q(20);//設置最大容量為19的queue
    q.Print();
    for(int i=1; i<=15;i++){
        q.enqueue(i); //測試放15個數進queue
    }
    q.Print();
    for(int i=0; i<5;i++){
        q.dequeue(); //測試拿5個數字出來
    }
    q.Print();
    for(int i=2; i<=20;i+=2){
        q.enqueue(i); //測試放10個數進queue
    }
    q.Print();
    return 0;
}

尚未有邦友留言

立即登入留言