學(xué)習(xí)目標(biāo)

自考重點(diǎn)、期末考試必過(guò)指南，這篇文章讓你理解什么是棧、什么是隊(duì)列、什么是數(shù)組

掌握棧、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

掌握棧、隊(duì)列的基本操作在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)

掌握矩陣的壓縮存儲(chǔ)

今天核心咱們先把棧搞清楚

棧和隊(duì)列可以看做是特殊的線性表 。它們的特殊性表現(xiàn)在它們的基本運(yùn)算是線性表運(yùn)算的子集，它們是運(yùn)算受限的線性表

棧

棧（Stack）是運(yùn)算受限的線性表，這種線性表上的插入和刪除操作限定在表的一端進(jìn)行

基本概念

棧頂：允許插入和刪除的一端 棧尾：另一端 空棧：不含任何數(shù)據(jù)元素的棧 棧頂元素：處于棧頂位置的數(shù)據(jù)元素

書(shū)中的例子比較形象

洗盤(pán)子，放盤(pán)子，每次只能從這一摞盤(pán)子的最上面拿走，這就是棧的基本操作

看重點(diǎn)：棧---> ==后進(jìn)先出（Last In First Out） LIFO 原則 ==

所以棧被稱(chēng)作 后進(jìn)先出線性表 （后進(jìn)先出表）

棧的插入和刪除運(yùn)算 分為成為 進(jìn)棧和 出棧

棧的基本運(yùn)算

• 初始化 InitStack(S) 構(gòu)造一個(gè)空棧 S
• 判斷?？?EmptyStack(S) 若棧為空，返回 1，否則返回 0
• 進(jìn)棧 Push(S,x) 將元素 x 插入棧 S 中
• 出棧 Pop(S) 刪除棧頂元素
• 取棧頂 GetTop(S) 返回棧頂元素

棧的順序?qū)崿F(xiàn)

這里面有兩個(gè)小知識(shí)點(diǎn)在寫(xiě)代碼之前需要掌握

空棧做出棧操作，會(huì)出現(xiàn)問(wèn)題，叫做“下溢” 滿棧做進(jìn)棧操作，會(huì)出現(xiàn)問(wèn)題，叫做“上溢”

接下來(lái)我們就用 C 語(yǔ)言實(shí)現(xiàn)一下

初始化一個(gè)空棧

#include <stdio.h>
#include <stdlib.h>
// 聲明順序棧的容量
const int maxsize = 6;
struct seqtack{
    int *data;  //存儲(chǔ)棧中元素的數(shù)組
    int top;  // 棧頂下標(biāo)
};

typedef struct seqtack Seq;

// 初始化操作
Seq init(Seq s){
    printf("初始化函數(shù)運(yùn)行\(zhòng)n");
    s.data = (int*)malloc(maxsize*sizeof(int));//動(dòng)態(tài)分配存儲(chǔ)空間
    if(!s.data){
        printf("初始化失敗");
        exit(0);
    }
    s.top = 0;
    return s;
}

注意事項(xiàng)

初始化需要?jiǎng)討B(tài)分配空間，并且需要讓 top 值等于 0

判斷?？?/p>

//判斷棧空
int empty(Seq s){
    printf("判斷?？誠(chéng)n");
    if(s.top == 0){
        return 1;
    }
    return 0;
}

這個(gè)比較簡(jiǎn)單了，只需要判斷 s.top 值就可以了

進(jìn)棧操作

//進(jìn)棧操作
Seq push(Seq s,int x){
    printf("進(jìn)棧操作\n");
    // 判斷棧是否滿了

    if(s.top==maxsize-1){
        printf("棧滿");
        return s;
    }
    else{

        printf("正在插入數(shù)據(jù)%d\n",x);
        s.data[s.top] = x;
        s.top++;
        return s;
    }

}

出棧操作

//出棧操作
Seq pop(Seq s,int *e){
    if(empty(s)){
        printf("棧空\(chéng)n");
        exit(0);
    }
    else{
        *e = s.data[s.top-1];
        s.top--;
        return s;
    }
}

進(jìn)棧和出棧，這部分內(nèi)容一定要好好的理解，其實(shí)也是比較簡(jiǎn)單的，就是添加元素和刪除元素

打印棧中元素與獲取棧頂元素

// 打印棧中元素
void display(Seq s){
    if(empty(s)){
        printf("?？誠(chéng)n");
        exit(0);
    }
    else{
        printf("開(kāi)始打印\n");
        int num = 0;
        while(num < s.top){
            printf("現(xiàn)在的元素是:%d\n",s.data[num++]);
        }
    }
}
// 獲取棧頂元素
int gettop(Seq s){
    if(empty(s)){
        exit("棧空\(chéng)n");
    }
    else{
        return s.data[s.top-1];
    }
}

主函數(shù)測(cè)試代碼

int main()
{
    printf("代碼運(yùn)行中\(zhòng)n");
    Seq s ;
    s = init(s);

    //插入兩個(gè)元素
    s = push(s,1);
    s = push(s,2);

    display(s);
    int e;
    s = pop(s,&e);
    printf("刪除的元素是:%d\n",e);

    display(s);

    return 0;
}

雙棧

書(shū)中還提到了雙棧，不過(guò)這個(gè)不是重點(diǎn)了，你要知道的是，雙棧的兩個(gè)棧底分別設(shè)置在數(shù)組的兩端，棧頂分為是 top1,top2

兩個(gè)棧頂在中間相遇，條件為 （top1+1=top2）發(fā)生上溢

判斷?？諚l件呢？ 一個(gè)是 top=0 另一個(gè)是 top = maxsize -1 這個(gè)要注意一下即可

棧的鏈接實(shí)現(xiàn)

棧的鏈接實(shí)現(xiàn)稱(chēng)為==鏈棧==。鏈棧 可以用帶頭結(jié)點(diǎn)的單鏈表來(lái)實(shí)現(xiàn)，鏈棧不用預(yù)先考慮容量的大小

鏈棧將鏈表頭部作為棧頂?shù)囊欢?，可以避免在?shí)現(xiàn)數(shù)據(jù)“入棧”和“出棧”操作時(shí)做大量遍歷鏈表的耗時(shí)操作

鏈表的頭部作為棧頂，有如下的好處

• 入棧 操作時(shí)，只需要將數(shù)據(jù)從鏈表的頭部插入即可
• 出棧 操作時(shí)，只需要?jiǎng)h除鏈表頭部的首結(jié)點(diǎn)即可

結(jié)論：鏈表實(shí)際上就是一個(gè)只能采用頭插法插入或刪除的鏈表

例子：將元素 1，2，3，4 依次入棧，等價(jià)于將各元素采用頭插法依次添加到鏈表中

圖片來(lái)源網(wǎng)絡(luò)

完整代碼如下

由于比較簡(jiǎn)單，直接貼上了

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int data;   //數(shù)據(jù)域
    struct node *next;   //鏈域
} LkStk;

//初始化
void init(LkStk *ls){
    printf("初始化操作\n");
    ls = (LkStk *)malloc(sizeof(LkStk));
    ls->next = NULL;
}

// 進(jìn)棧
void push(LkStk *ls,int x){
    printf("進(jìn)棧操作\n");
    LkStk *temp;
    temp = (LkStk*)malloc(sizeof(LkStk));//給temp新申請(qǐng)一塊空間
    temp->data = x;
    temp->next = ls->next;
    ls->next = temp;
    printf("%d進(jìn)棧成功\n",x);
}
int empty(LkStk *ls){
    if(ls->next ==NULL){
        return 1;
    }
    else return 0;
}

// 出棧
int pop(LkStk *ls){
    LkStk *temp;
    //判斷棧是否為空
    if(!empty(ls)){
        temp= ls->next;  // 準(zhǔn)備出棧的元素指向ls的下一結(jié)點(diǎn)
        ls->next = temp->next;   // 原棧頂?shù)南乱粋€(gè)結(jié)點(diǎn)稱(chēng)為新的棧頂
        printf("棧頂元素：%d\n",temp->data);
        free(temp); //釋放原棧頂?shù)慕Y(jié)點(diǎn)空間
        return 1;
    }
    return 0;
}

int main()
{
    LkStk ls;
    init(&ls);

    push(&ls,1);
    push(&ls,2);

    pop(&ls);
    pop(&ls);

    return 0;
}

這就是鏈棧的基本進(jìn)棧和出棧了，當(dāng)然，我們還可以獲取一下棧頂元素

考試要點(diǎn)

在自考或者期末考試中，容易出現(xiàn)的一種題是手寫(xiě)入棧和出棧 例如

設(shè)一個(gè)鏈棧的輸入序列為 A、B、C，試寫(xiě)出所得到的所有可能的輸出序列，即輸出出棧操作的數(shù)據(jù)元素序列

寫(xiě)答案的時(shí)候，記住先進(jìn)后出原則

從 A 開(kāi)始寫(xiě) A 進(jìn)，A 出，B 進(jìn)，B 出，C 進(jìn)，C 出 A 進(jìn)，B 進(jìn)，B 出，C 進(jìn)，C 出，A 出 ... ... 繼續(xù)寫(xiě)下去就可以了，一定不要出現(xiàn) A 進(jìn)，B 進(jìn)，B 出，C 進(jìn)，==A 出== 注意，A 出不去，A 前面有 C 呢

在來(lái)一個(gè)例題

如圖所示，在棧的輸入端元素的輸入順序?yàn)?A，B，C，D，進(jìn)棧過(guò)程中可以退棧，寫(xiě)出在棧的輸出端以 A 開(kāi)頭和以 B 開(kāi)頭的所有輸出序列。

這個(gè)就是把 A 開(kāi)頭和 B 開(kāi)頭的都寫(xiě)出來(lái)

• ABCD、ABDC、ACBD、ACDB、ADCB
• BACD、BADC、BCAD、BCDA、BDCA

主要仔細(xì)，就能寫(xiě)對(duì)，套路就是，先進(jìn)后出

小結(jié)

棧是只能在一端（棧頂）進(jìn)行插入和刪除運(yùn)算的線性表，具有后進(jìn)先出特征。

以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧稱(chēng)為順序棧，以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧稱(chēng)為鏈棧。

順序棧需要預(yù)先定義棧的大小，在難以估計(jì)棧的大小時(shí)，可以采用鏈棧，鏈棧是用單鏈表實(shí)現(xiàn)。一般地，將棧頂設(shè)在鏈表的表頭一端，棧底設(shè)置在鏈表的表尾。棧適合與具有后進(jìn)先出特征的問(wèn)題。

到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)不掛科指南之棧&隊(duì)列&數(shù)組詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言棧 隊(duì)列 數(shù)組內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論