---
# System prepended metadata

title: Data Struct - Hw2
tags: [Data Struct]

---

# Data Struct - Hw2  

###### tags: `Data Struct`



## 一 . 題目要求

### (一) . 題目要求 - 輸入 ： 題目有四種input
1. ```PUSH X``` : 將X的值存放到stack中。
2. ```POP``` : 將stack輸出最後一個。
3. ```ENQUEUE X``` : 將上一個pop出stack的存放到X列。
4. ```ENQUEUE X``` : 將X列的人pop出一個，並對應輸出。

### (二). 對策 - 輸出 ： 四種對應輸出
1. ```PUSH X``` : 不用輸出，加入stack即可。
2. ```POP``` : 將stack輸出最後一個。
   - stack的pop需回傳值。
4. ```ENQUEUE X``` : 將上一個pop出stack的存放到X列。
   - 問題一 ： 題目沒有說```pop```後必接```ENQUEUE X``` 。
     - stack回傳將被暫存在```wait_queue```中。 
     - 將```wait_queue```最前面的值輸入到X列。
     - ```wait_queue```也是一個```queue```。
   - 問題二 ： 沒有限制```queue```數。
      - 可能隨時有新增的queue。
      - queue非一個，動態的。  
6. ```DEQUEUE X``` : 將X列的人pop出一個，並對應輸出。
   - ```queue x``` pop出值，並輸出。

## 二 . Stack和Queue的資料結構
```c=
typedef struct{
    int* arr;
    int top;
    int length;

}Stack;

void InitStack(Stack* stack);

void isFullStack(Stack* stack);
int  isEmputy(Stack* stack);

void StackPush(Stack* stack, int num);
int  StackPop(Stack* stack);

void PrintStack(Stack* stack);
```
```c=
typedef struct Node{
   int val;
   struct Node* next;
}Node;

typedef struct{
   Node* head;
   Node* tail;
}Queue;

void InitQueue(Queue* q);

void QueuePush(Queue* q, int num);
int QueuePop(Queue* q);

void PrintQueue(Queue* q );
```

## 三 . 程式結構
### (一) . 主架構
#### 1. 目的 ： 先讀取指令，並分類 
![](https://i.imgur.com/99jswj8.png)



#### 2. 使用的變數 ： 只列出主要的變數
   - ```s``` : 存放盤子的stack。
   - ```qarr``` : 存放所有的queue。
   - ```wait_q``` : 存放暫存的人，即拿了盤子還沒排隊的。
   - 變數的設計好像沒有很符合流程圖，下面畫了一個抽象的圖。(可以看看前面```一 . 題目要求```的```(二) . 輸出```時所提到的題目分析)
![](https://i.imgur.com/uUmchmL.png)


### (二) . 四個指令的處理

#### 1.  PUSH 
![](https://i.imgur.com/gX6eSQY.png)

1. 因為我的Stack的實作中，若長度不夠，會自動增加長度，所以沒有先辨別stack是否滿。
2. 基本上就一直擷取字串，和push即可。
```c=
StackPush(s,num);
```


#### 2. POP 
![](https://i.imgur.com/38D72e4.png)
1. 我設計取出queue值得函式，若沒有值可以回傳，則會回傳-1，因此-1應該代表queue為空。
```c=
num=StackPop(s);
if(num==-1)
{
  printf("Plate stack is emputy!!");
}
else
{
    QueuePush(wait_q,num);
}
```

#### 3.ENQUEUE指令
![](https://i.imgur.com/TufAsqX.png)



