資料結構——棧：順序棧和鍊棧

順序棧(基于數組的順序棧)

#include<stdlib.h>
#include<stdio.h>
#include<windows.h>

typedef enum Status 
{
	error, success
} Status;

typedef int ElemType;

typedef struct SqStack 
{
	ElemType *elem;//存放棧元素(數組)
	int top;//存放棧頂元素的下标
	int size;//棧的長度
} SqStack;

//函數聲明
//基于數組的順序棧
Status initStack(SqStack *s, int sizes);//初始化棧
Status isEmptyStack(SqStack *s);//判斷棧是否為空
Status getTopStack(SqStack *s, ElemType *e); //得到棧頂元素
Status clearStack(SqStack *s);//清空棧
Status destroyStack(SqStack *s);//銷毀棧
Status stackLength(SqStack *s,int *length);//檢測棧長度
Status pushStack(SqStack *s, ElemType data);//入棧
Status popStack(SqStack *s, ElemType *data);//出棧
void show(void);//顯示視窗
int judge_int(void);//使使用者輸入整數

Status initStack(SqStack *s, int sizes)
{
    s->elem = (int *)malloc(sizeof(int) * sizes);
    s->size = sizes;
    s->top = -1;
    return success;
}

Status isEmptyStack(SqStack *s)
{
    if(s->top == -1)
    {
        return success;
    }
    else
    {
        return error;
    }
}

Status getTopStack(SqStack *s, ElemType *e)
{
    if(s->elem == NULL)
    {
        return error;
    }
    else 
    {
        if(s->top == -1)
        {
            printf("目前棧為空\n");
            return success;
        }
        else
        {
            *e = *s->elem + s->top;
            printf("目前棧頂元素是：%d\n", *e);
            return success;
        }
    }
}

Status clearStack(SqStack *s)
{
    if(s->elem == NULL)
    {
        return error;
    }
    else 
    {
        if(s->top == -1)
        {
            return success;
        }
        else 
        {
            s->top = -1;
            return success;
        }
    }
}

Status destroyStack(SqStack *s)
{
    if(s->elem == NULL)
    {
        return error;
    }
    else 
    {
        free(s->elem);
        s->elem = NULL;
        return success;
    }
}

Status stackLength(SqStack *s, int *length)
{
    if(s->elem == NULL)
    {
        return error;
    }
    else
    {
        length = &s->top;
        printf("目前棧的長度為%d\n", *length + 1);
        return success;
    }
    
}

Status pushStack(SqStack *s, ElemType data)
{
    s->top++;
    *(s->elem + s->top) = data;
    return success;
}

Status popStack(SqStack *s, ElemType *data)
{
    if(s->top == -1)
    {
        printf("棧為空\n");
        return error;
    }
    else
    {
        *data = *s->elem + s->top;
        s->top--;
        return success;
    }
}

void show(void)
{
    printf("\n\n\n\n        順序棧\n\n");
    printf("     1.初始化棧\n");
    printf("     2.判斷棧是否為空\n");
    printf("     3.得到棧頂元素\n");
    printf("     4.清空棧\n");
    printf("     5.銷毀棧\n");
    printf("     6.檢測棧的長度\n");
    printf("     7.入棧\n");
    printf("     8.出棧\n");
    printf("     9.退出\n\n");
    printf("請輸入對應的數字(1-9)：");
}

int judge_int(void)  //防止使用者亂輸入其他的字元
{
    int len, num = 0, arg = 1;
    char word[10];  
    int m, j= 1, k;
    while(j)
    {
        scanf("%s", word);
        len = strlen(word);
        for(m = 0;m<len;m++)
        {
            if(word[m]<'0' || word[m]>'9')  //檢驗是否有亂輸入其他字元
            {
                printf("請輸入整數：");
                break;
            }
            else
            {
                if(m == len-1)
                    j = 0;
            }
        }
    }
    j = len-1;
    for(m=0;m<len;m++)  // 将字元重新轉換為數字
    {
        for(k=0;k<j;k++)
            arg *= 10;
        num += (word[m]-'0')*arg;
        arg = 1;
        j--;
    }
    return num;
} 

int main(void)
{
    SqStack s;
    s.elem = NULL;
    int choice, size;
    ElemType data;
    ElemType *p = NULL;//用于檢測棧的長度
    ElemType temp;//用于擷取棧頂元素以及儲存出棧的元素

    do
    {
        show();
        choice = judge_int();
        system("cls");
        switch(choice)
        {
            case 1://初始化棧
            {
                printf("請輸入棧的長度：");
                scanf("%d", &size);
                if(initStack(&s, size))
                {
                    printf("初始化成功\n");
                }
                else 
                {
                    printf("初始化失敗\n");
                }
                break;
            }
            case 2://判斷棧是否為空
            {
                if(s.elem == NULL)
                {
                    printf("請先初始化棧\n");
                }
                else 
                {
                    if(isEmptyStack(&s))
                    {
                        printf("棧為空\n");
                    }
                    else 
                    {
                        printf("棧非空\n");
                    }
                }
                break;
            }
            case 3://得到棧頂元素
            {
                if(!getTopStack(&s, &temp))
                {
                    printf("請先初始化棧\n");
                }
                break;
            }
            case 4://清空棧
            {
                if(clearStack(&s))
                {
                    printf("清空完成\n");
                }
                else 
                {
                    printf("請先初始化棧\n");
                }
                break;
            }
            case 5://銷毀棧
            {
                if(destroyStack(&s))
                {
                    printf("棧銷毀完成\n");
                }
                else 
                {
                    printf("請先初始化棧\n");
                }
                break;
            }
            case 6://檢測棧的長度
            {
                if(!stackLength(&s, p))
                {
                    printf("請先初始化棧\n");
                }
                break;
            }
            case 7://入棧
            {
                if(s.elem == NULL)
                {
                    printf("請先初始化棧\n");
                }
                else if(s.top == s.size - 1)
                {
                    printf("棧滿\n");
                    printf("入棧失敗\n");
                }
                else 
                {
                    printf("請輸入資料：");
                    scanf("%d", &data);
                    if(!pushStack(&s, data))
                    {
                        printf("入棧失敗\n");
                    }
                    else 
                    {
                        printf("入棧完成\n");
                    }
                }
                break;
            }
            case 8://出棧
            {
                if(s.elem == NULL)
                {
                    printf("請先初始化棧\n");
                }
                else
                {
                    if(popStack(&s, &temp))
                    {
                        printf("出棧成功\n");
                    }
                    else 
                    {
                        printf("出棧失敗\n");
                    }
                }
                break;
            }
            case 9://退出程式
            {
                break;
            }
            default:
            {
                printf("請重新輸入數字！(1-9)\n");
                break;
            }
        }
    } while (choice != 9);

	system("pause");
    return 0;
}

鍊棧

#include<stdio.h>
#include<stdlib.h>
#include<windows.h>

#define STACK_H_INCLUDED

typedef enum Status 
{
    error, 
	success
} Status;

typedef int ElemType;

typedef struct StackNode
{
	ElemType data;
	struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack
{
	LinkStackPtr top;
	int	count;
}LinkStack;

//函數的聲明
//鍊棧
Status initLStack(LinkStack *s);//初始化棧
Status isEmptyLStack(LinkStack *s);//判斷棧是否為空
Status getTopLStack(LinkStack *s,ElemType *e);//得到棧頂元素
Status clearLStack(LinkStack *s);//清空棧
Status destroyLStack(LinkStack *s);//銷毀棧
Status LStackLength(LinkStack *s,int *length);//檢測棧長度
Status pushLStack(LinkStack *s,ElemType data);//入棧
Status popLStack(LinkStack *s,ElemType *data);//出棧
void show(void);//顯示界面
int judge_int(void);//使使用者輸入整數

Status initLStack(LinkStack *s)
{
    s->top = NULL;
    s->count = 0;
    return success;
}

Status isEmptyLStack(LinkStack *s)
{
    if(s->top == NULL)
    {
        return success;
    }
    else
    {
        return error;
    }
}

Status getTopLStack(LinkStack *s,ElemType *e)
{
    if(s->top == NULL)
    {
        printf("棧為空\n");
        return error;
    }
    else
    {
        *e = s->top->data;
        printf("棧頂元素為：%d\n", *e);
        return success;
    }
}

Status clearLStack(LinkStack *s)
{
    if(s->top == NULL)
    {
        printf("棧為空\n");
        return error;
    }
    else
    {
        s->top = NULL;
        return success;
    }
}

Status destroyLStack(LinkStack *s)
{
    while(!isEmptyLStack(s))
    {
        LinkStackPtr temp;
        temp = s->top;
        s->top = s->top->next;
        free(temp);
    }
    return success;
}

Status LStackLength(LinkStack *s,int *length)
{
    if(s->top == NULL)
    {
        return error;
    }
    else
    {
        length = &s->count;
        printf("目前棧的長度為%d\n", *length);
        return success;
    }
}

Status pushLStack(LinkStack *s,ElemType data)
{
    LinkStackPtr new = (LinkStackPtr)malloc(sizeof(StackNode));
    if(new == NULL)
    {
        printf("記憶體配置設定失敗\n");
        return error;
    }
    new->data = data;
    new->next = s->top;
    s->top = new;
    s->count++;
    return success;
}

Status popLStack(LinkStack *s,ElemType *data)
{
    if(s->top == NULL)
    {
        printf("棧為空\n");
        return error;
    }
    else
    {
        LinkStackPtr temp;
        *data = s->top->data;
        temp = s->top;
        s->top = s->top->next;
        free(temp);
        s->count--;
        return success;
    }
}

void show(void)
{
    printf("\n\n\n\n        鍊棧\n");
    printf("     (棧已初始化)\n\n");
    printf("     1.判斷棧是否為空\n");
    printf("     2.得到棧頂元素\n");
    printf("     3.清空棧\n");
    printf("     4.銷毀棧\n");
    printf("     5.檢測棧的長度\n");
    printf("     6.入棧\n");
    printf("     7.出棧\n");
    printf("     8.退出\n\n");
    printf("請輸入對應的數字(1-8)：");
}

int judge_int(void)  //防止使用者亂輸入其他的字元
{
    int len, num = 0, arg = 1;
    char word[10];  
    int m, j= 1, k;
    while(j)
    {
        scanf("%s", word);
        len = strlen(word);
        for(m = 0;m<len;m++)
        {
            if(word[m]<'0' || word[m]>'9')  //檢驗是否有亂輸入其他字元
            {
                printf("請輸入整數：");
                break;
            }
            else 
            {
                if(m == len-1)
                    j = 0;
            }
        }
    }
    j = len-1;
    for(m=0;m<len;m++)  // 将字元重新轉換為數字
    {
        for(k=0;k<j;k++)
            arg *= 10;
        num += (word[m]-'0')*arg;
        arg = 1;
        j--;
    }
    return num;
} 

int main(void)
{
    int choice;
    int *len = NULL;
    ElemType data;
    LinkStack s;
    ElemType temp;//用于擷取棧頂元素及儲存出棧的元素
    
    if(!initLStack(&s))
    {
        printf("棧初始化失敗\n");
    }

    do
    {
        show();
        choice = judge_int();
        system("cls");
        switch(choice)
        {
            case 1://判斷棧是否為空
            {
                if(isEmptyLStack(&s))
                {
                    printf("棧為空\n");
                }
                else
                {
                    printf("棧非空\n");
                }
                break;
            }
            case 2://得到棧頂元素
            {
                if(!getTopLStack(&s, &temp))
                {
                    printf("擷取失敗\n");
                }
                break;
            }
            case 3://清空棧
            {
                if(clearLStack(&s))
                {
                    printf("清空完成\n");
                }
                else
                {
                    printf("清空失敗\n");
                }
                break;
            }
            case 4://銷毀棧
            {
                if(destroyLStack(&s))
                {
                    printf("銷毀完成\n");
                }
                else
                {
                    printf("銷毀失敗\n");
                }
                break;
            }
            case 5://檢測棧的長度
            {
                if(!LStackLength(&s, len))
                {
                    printf("棧為空\n");
                }
                break;
            }
            case 6://入棧
            {
                printf("請輸入資料：");
                scanf("%d", &data);
                if(!pushLStack(&s, data))
                {
                    printf("入棧失敗\n");
                }
                break;
            }
            case 7://出棧
            {
                if(popLStack(&s, &temp))
                {
                    printf("出棧完成\n");
                }
                else
                {
                    printf("出棧失敗\n");
                }
                break;
            }
            case 8://退出程式
            {
                break;
            }
            default:
            {
                printf("請重新輸入數字！(1-8)\n");
                break;
            }
        }
    } while (choice != 8);

	system("pause");
    return 0;
}

學習鍊棧後，可以利用鍊棧實作逆波蘭電腦(本部落客的另一篇文章)

資料結構——棧：順序棧和鍊棧

繼續閱讀

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

CRC32和CRC8校驗代碼，C語言版

241 Different Ways to Add Parentheses（C代碼版）

[轉]ISUP信令的IAM消息詳細内容

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

結構體：typedef與struct的差別

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希