腳本之家服務器常用軟件

快捷導航

C語言數(shù)據(jù)結構不掛科指南之棧&隊列&數(shù)組詳解

更新時間：2022年09月27日 14:32:56 作者：夢想橡皮擦

自考重點、期末考試必過指南，這篇文章讓你理解什么是棧、什么是隊列、什么是數(shù)組。文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下

學習目標

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

掌握棧、隊列的順序存儲結構和鏈式存儲結構

掌握棧、隊列的基本操作在順序存儲結構和鏈式存儲結構上的實現(xiàn)

掌握矩陣的壓縮存儲

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

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

棧

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

基本概念

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

書中的例子比較形象

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

看重點：棧---> ==后進先出（Last In First Out） LIFO 原則 ==

所以棧被稱作后進先出線性表（后進先出表）

棧的插入和刪除運算分為成為進棧和出棧

棧的基本運算

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

棧的順序實現(xiàn)

這里面有兩個小知識點在寫代碼之前需要掌握

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

接下來我們就用 C 語言實現(xiàn)一下

初始化一個空棧

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

typedef struct seqtack Seq;

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

注意事項

初始化需要動態(tài)分配空間，并且需要讓 top 值等于 0

判斷棧空

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

這個比較簡單了，只需要判斷 s.top 值就可以了

進棧操作

//進棧操作
Seq push(Seq s,int x){
    printf("進棧操作\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("?？誠n");
        exit(0);
    }
    else{
        *e = s.data[s.top-1];
        s.top--;
        return s;
    }
}

進棧和出棧，這部分內容一定要好好的理解，其實也是比較簡單的，就是添加元素和刪除元素

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

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

主函數(shù)測試代碼

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

    //插入兩個元素
    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ù)組的兩端，棧頂分為是 top1,top2

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

判斷棧空條件呢？一個是 top=0 另一個是 top = maxsize -1 這個要注意一下即可

棧的鏈接實現(xiàn)

棧的鏈接實現(xiàn)稱為==鏈棧==。鏈棧可以用帶頭結點的單鏈表來實現(xiàn)，鏈棧不用預先考慮容量的大小

鏈棧將鏈表頭部作為棧頂?shù)囊欢耍梢员苊庠趯崿F(xiàn)數(shù)據(jù)“入棧”和“出棧”操作時做大量遍歷鏈表的耗時操作

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

入棧操作時，只需要將數(shù)據(jù)從鏈表的頭部插入即可
出棧操作時，只需要刪除鏈表頭部的首結點即可

結論：鏈表實際上就是一個只能采用頭插法插入或刪除的鏈表

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

圖片來源網(wǎng)絡

完整代碼如下

由于比較簡單，直接貼上了

#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;
}

// 進棧
void push(LkStk *ls,int x){
    printf("進棧操作\n");
    LkStk *temp;
    temp = (LkStk*)malloc(sizeof(LkStk));//給temp新申請一塊空間
    temp->data = x;
    temp->next = ls->next;
    ls->next = temp;
    printf("%d進棧成功\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;  // 準備出棧的元素指向ls的下一結點
        ls->next = temp->next;   // 原棧頂?shù)南乱粋€結點稱為新的棧頂
        printf("棧頂元素：%d\n",temp->data);
        free(temp); //釋放原棧頂?shù)慕Y點空間
        return 1;
    }
    return 0;
}

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

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

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

    return 0;
}

這就是鏈棧的基本進棧和出棧了，當然，我們還可以獲取一下棧頂元素