From Gossip@caterpillar

Algorithm Gossip: 堆疊 - 使用陣列實作

說明

堆疊是一種先進後出的資料結構，就如同您將書本放入箱子，最先放進的書本在最後才能拿出來，所有資料的加入與刪除都在堆疊頂端完成。堆疊的使用很廣，遞迴 就是一種堆疊，在之前介紹中序式轉後序式時，也使用到堆疊的結構。

堆疊可以使用多種方式實作，其中使用陣列是最簡單的方法，也最不受使用的程式語言所限制。

解法

堆疊最重要的就是記錄頂端的位置，尤其是在堆疊空間固定的情況下，必須注意堆疊已滿或已空的判斷，當使用陣列實作堆疊時尤其重要。

堆疊的基本操作有五項：建立堆疊、傳回頂端元素、加入元素至堆疊、刪除元素至堆疊、顯示堆疊所有內容。為了方便，加入一個測試堆疊是否為空的方法，詳 細的演算並不難，直接列出程式實作。

實作

  • C 
#include <stdio.h> 
#include <stdlib.h> 
#define MAX 10 

int creates(int[]);         // 建立堆疊 
int isEmpty(int);           // 堆疊已空 
int stacktop(int[], int);   // 傳回頂端元素 
int add(int[], int, int);   // 插入元素 
int delete(int[], int);     // 刪除元素 
void list(int[], int);      // 顯示所有內容 

int main(void) { 
    int stack[MAX]; 
    int top; 
    int input, select; 

    top = creates(stack); 

    while(1) { 
        printf("\n\n請輸入選項(-1結束)："); 
        printf("\n(1)插入值至堆疊"); 
        printf("\n(2)顯示堆疊頂端"); 
        printf("\n(3)刪除頂端值"); 
        printf("\n(4)顯示所有內容"); 
        printf("\n$c>"); 
        scanf("%d", &select); 
        
        if(select == -1) 
            break; 

        switch(select) { 
            case 1: 
                printf("\n輸入值："); 
                scanf("%d", &input); 
                top = add(stack, top, input); 
                break; 
            case 2: 
                printf("\n頂端值：%d", stacktop(stack, top)); 
                break; 
            case 3: 
                top = delete(stack, top); 
                break; 
            case 4: 
                list(stack, top); 
                break; 
            default: 
                printf("\n選項錯誤！"); 
        } 
    } 

    printf("\n"); 

    return 0; 
} 

// 以下為堆疊操作的實作 
int creates(int stack[]) { 
    int i; 

    for(i = 0; i < MAX; i++) 
        stack[i] = 0; 

    return -1; 
} 

int isEmpty(int top) { 
    return (top == -1); 
} 

int stacktop(int stack[], int top) { 
    return stack[top]; 
} 

int add(int stack[], int top, int item) { 
    int t = top; 

    if(t >= MAX-1) { 
        printf("\n堆疊已滿！"); 
        return t; 
    } 

    stack[++t] = item; 

    return t; 
} 

int delete(int stack[], int top) { 
    int t = top; 

    if(isEmpty(t)) { 
        printf("\n堆疊已空！"); 
        return t; 
    } 

    return --t; 
} 

void list(int stack[], int top) { 
    int t = top; 

    printf("\n堆疊內容："); 
    while(!isEmpty(t)) { 
        printf("%d ", stack[t]); 
        t--; 
    } 
}