---
# System prepended metadata

title: NTCU資料結構第三章考前複習
tags: [學業共筆]

---

## CH3

### 1. Stack (堆疊):

堆疊是一個先進後出（LIFO, Last-In-First-Out）的資料結構。它有一個指標(Top)指向最頂端的元素。常見的堆疊操作包括推入(push(add))和彈出(pop(delete))。
* 有順序的序列
* 先進後出
* 有一個pointer(Top)指向最頂端的元素

#### C程式碼範例:

```c=
#include <stdio.h>
#define MAX 10

int stack[MAX];
int top = -1;

void push(int value) {
    if(top < MAX - 1) {
        stack[++top] = value;
    } else {
        printf("Stack overflow\n");
    }
}

int pop() {
    if(top >= 0) {
        return stack[top--];
    } else {
        printf("Stack underflow\n");
        return -1;
    }
}

int main() {
    push(10);
    push(20);
    printf("%d\n", pop());  // Output: 20
    return 0;
}
```

### 2. Queue (佇列):

佇列是一個先進先出（FIFO, First-In-First-Out）的資料結構，類似於排隊。它有兩個指標(front, rear)，分別指向隊首和隊尾。

* 有順序的序列
* 先進先出(類似排隊)
* 有兩個pointer(front,rear)，分別指隊首和隊尾

#### C程式碼範例:

```c=
#include <stdio.h>
#define MAX 10

int queue[MAX];
int front = 0, rear = 0;

void enqueue(int value) {
    if(rear < MAX) {
        queue[rear++] = value;
    } else {
        printf("Queue overflow\n");
    }
}

int dequeue() {
    if(front < rear) {
        return queue[front++];
    } else {
        printf("Queue underflow\n");
        return -1;
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    printf("%d\n", dequeue());  // Output: 10
    return 0;
}
```

### 3. Circular Queue (循環佇列):

循環佇列是一種當隊尾指標到達陣列的最末端時，會從陣列的開頭重新開始的佇列。
* rear (pointer) 指向隊尾
* front (pointer) 指向隊首

#### C程式碼範例:

```c=
#include <stdio.h>
#define MAX 10

int cqueue[MAX];
int front = 0, rear = 0;

void enqueue(int value) {
    int newRear = (rear + 1) % MAX;
    if(newRear != front) {
        cqueue[rear] = value;
        rear = newRear;
    } else {
        printf("Circular Queue overflow\n");
    }
}

int dequeue() {
    if(front != rear) {
        int value = cqueue[front];
        front = (front + 1) % MAX;
        return value;
    } else {
        printf("Circular Queue underflow\n");
        return -1;
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    printf("%d\n", dequeue());  // Output: 10
    return 0;
}
```

