# 資訊一乙 20210527 考試
## Description
你是一個單身多年即將轉職魔法師的 29 歲的資深工程師，今天收到學妹 Julia 的求助。

老師要請她從這串指令中判斷這個結構屬於 Stack（後進先出）, Queue（先進先出） 還是兩個都不是。

程式的指令如下：

1 x：把 x 這個元素放進去結構。

2 x：從結構中拿出 x 這個元素。

看在學妹很漂亮而且願意跟你出去吃飯的份上，寫一支程式救救她吧！

＊請使用鏈結串列或是陣列模擬 Stack 跟 Queue，請勿直接使用數字判斷結構。
### Input
有多筆測資，每筆測資的第一行為 n（0 < n <= 1000），代表接下來有 n 行指令。

每行指令有兩個數字，第一個數字為 1 或 2，代表的內容於題目所述。

第二個數字為成功取出（without error）或成功放入的元素。此數字小於 100（數字 < 100）。

以 EOF 作為結束。
### Output
針對每筆測資，輸出對應的資料結構。

stack：100% 就是 stack

queue：100% 就是 queue

impossible：兩個都不是
___
### Sample Input 1

6
1 1
1 2
1 3
2 1
2 2
2 3
2
1 1
2 2
4
1 2
1 1
2 1
2 2

### Sample Output 1

queue
impossible
stack

___
## 我的做法
### 基礎操作
第一個就是node的結構

typedef struct node{
    int val;
    struct node* next;
} NODE;

|
|
接下來就是~~一如既往的~~makenode

NODE* makenode(int val){
    NODE* new = malloc(sizeof(NODE));
    new->val = val;
    new->next = NULL;
    return new;
}

|
|
把東西加進linked list裡面，我是addAtHead啦

void push(NODE* obj, int val){
    NODE* new = makenode(val);
    new->next = obj->next;
    obj->next = new;
}

|
|
可以return最後一項的指標的~~韓式~~炸雞

NODE* getTailPtr(NODE* obj){
    NODE* current = obj;
    while (current->next){
        current = current->next;
    }
    return current;
}

|
|
當這個linked list被當作stack來操作的時候，用這個~~炸雞~~來取得top的值

int stackTop(NODE* obj){
    if (obj->next){
        return obj->next->val;
    }
    return 100;
}

|
|
當這個linked list被當作stack來操作的時候，用這個來刪除top節點

void stackPop(NODE* obj){
    if (obj->next){
        NODE* temp = obj->next;
        obj->next = obj->next->next;
        free(temp);
    }
}

|
|
當這個linked list被當作queue來操作的時候，用這個來取得queue的最後一項的值 ~~(是叫rear嗎)~~

int queTail(NODE* obj){
    NODE* tail = getTailPtr(obj);
    if (tail != obj){
        return tail->val;
    }
    return 100;
}

|
|
當這個linked list被當作queue來操作的時候，用這個來刪除queue的最後一項

void quePop(NODE* obj){
    NODE* tail = getTailPtr(obj);
    if (tail == obj){
        return;
    }
    NODE* current = obj;
    while (current->next != tail){
        current = current->next;
    }
    current->next = NULL;
    free(tail);
}

|
|
刪除 linked list

void dList(NODE* obj){
    while (obj->next){
        NODE* temp = obj->next;
        obj->next = obj->next->next;
        free(temp);
    }
    free (obj);
}

上面港節有點ㄉㄛ
___
### main韓式

int main(){
    while(1){
        //times是看這輪有幾個測資
        int times = 0;
        if (scanf ("%d", &times) == EOF){
            break;
        }
        /*
         我也不知道他到底會是"queue"還是"stack"還是"窩不知道"
         而且stack跟queue刪節點的方式不一樣
         所以我就建了兩個linked list
         一個檢查queue，一個檢查stack
         */
        NODE* myListStack = makenode(0);
        NODE* myListQueue = makenode(0);
        
        //type=1 is stack, type=2 is queue
        //一開始都先預設他們同時是stack和queue
        //(上上個註解不用理他，那是我最開始的想法，後來改了)
        /*
        stype==1就是stack
        qtype==1就是queue
        */
        int qtype = 1;
        int stype = 1;

        //input decla
        /*
         inputType就是1的話push，不然就就從結構裡取值pop
         input就是...這次的input
         */ 
        int inputType = 0;
        int input = 0;
        
        //times是看這輪有幾個測資
        for (int i=0; i<times; ++i){
            scanf ("%d %d", &inputType, &input);
            
            //1的狀況很簡單，push就完事了
            if (inputType==1){
                push(myListStack, input);
                push(myListQueue, input);
                continue;
            }
            //___以下這是非1的情況(就是2的情況啦)___
            
            //在input == stack的top，而且還沒變成"非stack"的時候
            if (input == stackTop(myListStack) && stype == 1){
                //stype = 1;
                
                //其實就刪除就好
                stackPop(myListStack);
            }
            
            //值不一樣就代表他不符合stack，標為"非stack"
            else if (input != stackTop(myListStack)){
                stype = 0;
            }
            
            //在input == queue的tail，而且還沒變成"非queue"的時候
            if (input == queTail(myListQueue) && qtype == 1){
                //qtype = 1
                
                //其實也是刪除就好
                quePop(myListQueue);
            }
            
            //值不一樣就代表他不符合queue，標為"非queue"
            else if (input != queTail(myListQueue)){
                qtype = 0;
            }
            //標成"非"的的linked list沒刪完的不用裡他，後面我們會一起刪
        }
        
        //100%的stack
        if (stype == 1 && qtype == 0){
            printf ("stack\n");
        }
        
        //100%的queue
        else if (stype == 0 && qtype == 1){
            printf ("queue\n");   
        }
        
        /*
         (stype==1 && qtype==1)並非100%stack 或 100%queue
         所以也是impossible
         */
        else{
            printf("impossible\n");
        }
        
        /*
         我一開始其實沒加這項的
         但沒刪會"Memory Limit Exceeded"
         所以還是刪了 XD
         */
        dList(myListQueue);
        dList(myListStack);
    }
}

好啦其實在跑的時候可以用一個變數來存queTail之類的東東
這樣這些函式才不會這樣一直跑
尤其有一些函式是一直跑迴圈到linked list的尾巴 ~~(待改進)~~