国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁(yè)
  2. >Toy博客

【腳踢數(shù)據(jù)結(jié)構(gòu)】深入理解棧

2年前作者：祐言QAQ分類：Toy博客閱讀(27)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【腳踢數(shù)據(jù)結(jié)構(gòu)】深入理解棧。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

  • (??? )，Hello我是祐言QAQ
  • 我的博客主頁(yè)：C/C++語(yǔ)言,Linux基礎(chǔ),ARM開發(fā)板，軟件配置等領(lǐng)域博主??
  • 快上??，一起學(xué)習(xí)，讓我們成為一個(gè)強(qiáng)大的攻城獅！
  • 送給自己和讀者的一句雞湯??：集中起來(lái)的意志可以擊穿頑石!
  • 作者水平很有限，如果發(fā)現(xiàn)錯(cuò)誤，可在評(píng)論區(qū)指正，感謝??

一、什么是棧？

????????棧是一種重要的數(shù)據(jù)結(jié)構(gòu)。它是一種特殊的線性表，特殊在它只允許在表的一端進(jìn)行插入和刪除操作，這一端被稱為棧頂，相對(duì)的，另一端被稱為棧底。在這篇博客中，我們將詳細(xì)地介紹棧的概念，包括順序棧和鏈棧的實(shí)現(xiàn)。? ?

【腳踢數(shù)據(jù)結(jié)構(gòu)】深入理解棧,腳踢數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,算法

?????????棧是一種線性數(shù)據(jù)結(jié)構(gòu)，它遵循 "先入后出"（Last-In-First-Out，LIFO）的原則。這意味著最后插入棧的元素將首先被移除，而最早插入的元素將最后被移除。就像如果1先進(jìn)入了棧底，你想再拿到它，那么就要先把 6 5 4 3 2依次拿出來(lái)才能拿到 1。

【腳踢數(shù)據(jù)結(jié)構(gòu)】深入理解棧,腳踢數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,算法

?二、順序棧

????????順序棧是棧的一種實(shí)現(xiàn)方式，它是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)棧中的元素，并需要一個(gè)棧頂指針 *top指出棧頂元素，初始化為-1，棧的大小?size則決定了最多可以放多少數(shù)據(jù)。

【腳踢數(shù)據(jù)結(jié)構(gòu)】深入理解棧,腳踢數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,算法

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??????順序棧結(jié)構(gòu)體

1.順序棧的管理結(jié)構(gòu)體

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

typedef int Datatype;

//順序棧結(jié)構(gòu)體
typedef struct Sequent_stack
{
	Datatype *stack;		//存放數(shù)據(jù)的位置
	int size;				//棧的大小
	int top;				//棧頂偏移
}S_stack;

2.初始化

//初始化順序棧
S_stack *init_stack(int size)
{
	S_stack *s1= malloc(sizeof(S_stack));
	if (s1 != NULL)
	{
		s1->stack = calloc(size, sizeof(Datatype));
		s1->size = size;
		s1->top = -1;
	}
	return s1;
}


3.判斷?？諚M

//是否棧空
bool isempty(S_stack *s)
{
	return (s->top == -1);
}

//是否棧滿
bool isfull(S_stack *s)
{
	return (s->top == s->size-1);
}

4.壓棧（入棧）

//壓棧
bool push(S_stack *s, Datatype data)
{
	if (isfull(s))
	{
		return false;
	}
	//將棧頂往上偏移一個(gè)
	s->top++;
	//將數(shù)據(jù)，放到棧頂指向的位置
	s->stack[s->top] = data;  //*(s->stack+s->top) = data;
	return true;
}

5.彈棧（出棧）

//彈棧
bool pop(S_stack *s, Datatype *data)
{
	if (isempty(s))
	{
		return false;
	}
	//先拿到棧頂指向的數(shù)據(jù)
	*data = s->stack[s->top];//data = *(s->stack+s->top);
	//棧頂在往下偏移一個(gè)
	s->top--;
	return true;
}

6.遍歷順序棧

//遍歷棧
void display(S_stack *s)
{
	for (int i = 0; i <= s->top; ++i)
	{
		printf("%d ", s->stack[i]);
	}
	printf("\n");
}

練習(xí)：

????????輸入一個(gè)大于零的十進(jìn)制數(shù)，轉(zhuǎn)化為八進(jìn)制，轉(zhuǎn)化過(guò)程中使用順序棧結(jié)構(gòu)來(lái)實(shí)現(xiàn)。輸入：?123? 輸出 ：轉(zhuǎn)化為八進(jìn)制是?0173。

【腳踢數(shù)據(jù)結(jié)構(gòu)】深入理解棧,腳踢數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,算法

?? ? ? ? 完整代碼：

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

typedef int Datatype;

//順序棧結(jié)構(gòu)體
typedef struct Secqune_stack
{
	Datatype *stack;		//存放數(shù)據(jù)的位置
	int size;				//棧的大小
	int top;				//棧頂偏移
}S_stack;

//初始化順序棧
S_stack *init_stack(int size)
{
	S_stack *s1= malloc(sizeof(S_stack));
	if (s1 != NULL)
	{
		s1->stack = calloc(size, sizeof(Datatype));
		s1->size = size;
		s1->top = -1;
	}
	return s1;
}

//?？?bool isempty(S_stack *s)
{
	return (s->top == -1);
}

//棧滿
bool isfull(S_stack *s)
{
	return (s->top == s->size-1);
}

//壓棧(入棧)
bool push(S_stack *s, Datatype data)
{
	if (isfull(s))
	{
		return false;
	}
	//將棧頂往上偏移一個(gè)
	s->top++;
	//將數(shù)據(jù)，放到棧頂指向的位置
	s->stack[s->top] = data;  //*(s->stack+s->top) = data;
	return true;
}

//彈棧(出棧)
bool pop(S_stack *s, Datatype *data)
{
	if (isempty(s))
	{
		return false;
	}
	//先拿到棧頂指向的數(shù)據(jù)
	*data = s->stack[s->top];//data = *(s->stack+s->top);
	//棧頂在往下偏移一個(gè)
	s->top--;
	return true;
}

int main(int argc, char const *argv[])
{
	//初始化順序棧
	S_stack *s = init_stack(22);
	int num;
	scanf("%d", &num);
	while(num)
	{
		push(s, num%8);
		num/=8;
	}
	printf("十進(jìn)制數(shù)轉(zhuǎn)為八進(jìn)制數(shù)等于：0");
	int data;
	while(!isempty(s))
	{
		pop(s, &data);
		printf("%d", data);
	}
	printf("\n");

	return 0;
}

三、鏈?zhǔn)綏?/h3>

????????鏈?zhǔn)綏Ｊ菞５牧硪环N常見(jiàn)實(shí)現(xiàn)方式，它通過(guò)鏈表來(lái)表示棧的結(jié)構(gòu)。鏈?zhǔn)綏Ｏ鄬?duì)于順序棧的一個(gè)主要優(yōu)勢(shì)是它可以動(dòng)態(tài)地調(diào)整大小，適用于棧容量需求不確定或需要頻繁的插入和刪除操作的情況。與之相對(duì)應(yīng)的是鏈?zhǔn)綏Ｒ残枰嗟膬?nèi)存空間用于存儲(chǔ)節(jié)點(diǎn)指針。

【腳踢數(shù)據(jù)結(jié)構(gòu)】深入理解棧,腳踢數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,算法

? ? ? ? 在具體的指針操作方面與單項(xiàng)鏈表相似。

1.鏈?zhǔn)綏５墓芾斫Y(jié)構(gòu)體


typedef int Datatype;

typedef struct Node
{
	Datatype data;			//數(shù)據(jù)
	struct Node *prev;		//指向上一個(gè)節(jié)點(diǎn)
}node;

//鏈?zhǔn)綏５墓?jié)點(diǎn)
typedef struct List_stack
{
	node *stack;		//每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)
	int size;			//長(zhǎng)度
}Lstack;

2.初始化

//初始化鏈?zhǔn)綏?Lstack *init_list_stack()
{
	Lstack *s = malloc(sizeof(Lstack));
	if (s!=NULL)
	{
		s->stack = NULL;
		s->size = 0;
	}
	return s;
}

3.判斷?？?/h4>

? ? ? ? 由于鏈?zhǔn)綏＊?dú)特的結(jié)構(gòu)使之不會(huì)出現(xiàn)棧滿的情況，而是根據(jù)需要隨時(shí)動(dòng)態(tài)調(diào)整棧容量，因此我們無(wú)需判斷鏈?zhǔn)綏Ｊ欠駰M。

//鏈?zhǔn)綏５臈？张袛?bool isempty(Lstack *s)
{
	return (s->size == 0);
}

4.壓棧

//壓棧（入棧）
bool push(Lstack *s, Datatype data)
{
	node *new = malloc(sizeof(node));
	if (new != NULL)
	{
		//如果new不為空
		new->data = data;
		//新節(jié)點(diǎn)的prev指向棧原來(lái)的尾部
		new->prev = s->stack;
		//新節(jié)點(diǎn)現(xiàn)在是不是就變?yōu)楝F(xiàn)在鏈?zhǔn)綏５奈膊?		s->stack = new;
		//棧的大小+1
		s->size++;
		return true;
	}
	else
	{
		return false;
	}
}

5.彈棧

//彈棧（出棧）
bool pop(Lstack *s, Datatype *data)
{
	//?？?	if (isempty(s))
	{
		return false;
	}
	//先將棧的尾部（棧頂）的節(jié)點(diǎn)的地址拿到
	*data = s->stack->data;
	//將尾部（棧頂）的節(jié)點(diǎn)往前挪一個(gè)
	s->stack = s->stack->prev;
	//鏈?zhǔn)綏５墓?jié)點(diǎn)個(gè)數(shù)-1
	s->size--;
	return true;
}

練習(xí)：

????????輸入一個(gè)大于零的十進(jìn)制數(shù)，轉(zhuǎn)化為十六進(jìn)制，轉(zhuǎn)化過(guò)程中使用鏈?zhǔn)綏＝Y(jié)構(gòu)來(lái)實(shí)現(xiàn)。輸入：?123? 輸出 ：轉(zhuǎn)化為八進(jìn)制是?0x7B。??

【腳踢數(shù)據(jù)結(jié)構(gòu)】深入理解棧,腳踢數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,算法

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

typedef int Datatype;

typedef struct Node
{
	Datatype data;			//數(shù)據(jù)
	struct Node *prev;		//指向上一個(gè)節(jié)點(diǎn)
}node;

//鏈?zhǔn)綏５墓?jié)點(diǎn)
typedef struct List_stack
{
	node *stack;		//每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)
	int size;			//長(zhǎng)度
}Lstack;

//初始化鏈?zhǔn)綏?Lstack *init_list_stack()
{
	Lstack *s = malloc(sizeof(Lstack));
	if (s!=NULL)
	{
		s->stack = NULL;
		s->size = 0;
	}
	return s;
}

//鏈?zhǔn)綏５臈？张袛?bool isempty(Lstack *s)
{
	return (s->size == 0);
}

//壓棧（入棧）
bool push(Lstack *s, Datatype data)
{
	node *new = malloc(sizeof(node));
	if (new != NULL)
	{
		//如果new不為空
		new->data = data;
		//新節(jié)點(diǎn)的prev指向棧原來(lái)的尾部
		new->prev = s->stack;
		//新節(jié)點(diǎn)現(xiàn)在是不是就變?yōu)楝F(xiàn)在鏈?zhǔn)綏５奈膊?		s->stack = new;
		//棧的大小+1
		s->size++;
		return true;
	}
	else
	{
		return false;
	}
}

//彈棧（出棧）
bool pop(Lstack *s, Datatype *data)
{
	//棧空
	if (isempty(s))
	{
		return false;
	}
	//先將棧的尾部（棧頂）的節(jié)點(diǎn)的地址拿到
	*data = s->stack->data;
	//將尾部（棧頂）的節(jié)點(diǎn)往前挪一個(gè)
	s->stack = s->stack->prev;
	//鏈?zhǔn)綏５墓?jié)點(diǎn)個(gè)數(shù)-1
	s->size--;
	return true;
}

int main(int argc, char const *argv[]) {
    Lstack *s = init_list_stack();
    int num;
    Datatype data;
    char hexDigits[] = "0123456789ABCDEF";  // 十六進(jìn)制字符表示
    printf("請(qǐng)輸入一個(gè)十進(jìn)制數(shù)：");
    scanf("%d", &num);

    while (num > 0) {
        int num1 = num % 16;
        push(s, num1);
        num /= 16;
    }

    printf("轉(zhuǎn)化為十六進(jìn)制是：0x");
    while (!isempty(s)) {
        pop(s, &data);
        printf("%c", hexDigits[data]);
    }
    printf("\n");

    // 釋放內(nèi)存
    while (pop(s, &data)) {
        free(s->stack);
        s->stack = s->stack->prev;
    }
    free(s);

    return 0;
}

四、順序棧和鏈棧的比較


????????順序棧和鏈棧是棧的兩種不同實(shí)現(xiàn)方式，它們各有優(yōu)點(diǎn)和缺點(diǎn)。

????????1.空間分配：順序棧需要一次性分配一整塊連續(xù)的內(nèi)存空間，可能導(dǎo)致空間浪費(fèi)。而鏈棧則可以動(dòng)態(tài)分配空間，用多少分配多少，因此在內(nèi)存利用上更有優(yōu)勢(shì)。

????????2.時(shí)間復(fù)雜度：由于順序棧是基于數(shù)組的，因此在訪問(wèn)元素時(shí)可以直接通過(guò)索引進(jìn)行訪問(wèn)，時(shí)間復(fù)雜度為O(1)。而鏈棧需要通過(guò)指針進(jìn)行遍歷，時(shí)間復(fù)雜度為O(n)。

????????3.插入和刪除：兩者在插入和刪除操作上都是O(1)的時(shí)間復(fù)雜度。順序棧通過(guò)改變棧頂指針位置進(jìn)行插入和刪除，鏈棧通過(guò)改變指針的指向進(jìn)行插入和刪除。

五、棧的應(yīng)用


????????棧在計(jì)算機(jī)科學(xué)和日常編程中扮演著重要的角色，以下是一些常見(jiàn)的使用場(chǎng)景：

????????1.函數(shù)調(diào)用：每當(dāng)程序調(diào)用一個(gè)函數(shù)時(shí)，系統(tǒng)會(huì)將返回地址和必要的信息存入系統(tǒng)棧中，待函數(shù)運(yùn)行完畢后再?gòu)臈Ｖ谢謴?fù)這些信息。

????????2.表達(dá)式求值：?？梢杂糜谒阈g(shù)或邏輯表達(dá)式的求值。例如，計(jì)算機(jī)程序通常使用兩個(gè)棧來(lái)處理數(shù)學(xué)表達(dá)式，一個(gè)棧用于存儲(chǔ)操作數(shù)，另一個(gè)棧用于存儲(chǔ)運(yùn)算符。

????????3.括號(hào)匹配：?？梢杂糜跈z查一段文本中的括號(hào)是否正確匹配。當(dāng)遇到一個(gè)開括號(hào)時(shí)，將其壓入棧中。當(dāng)遇到一個(gè)閉括號(hào)時(shí)，從棧頂彈出一個(gè)開括號(hào)，如果能夠匹配，則繼續(xù)處理，否則就是不匹配。

????????總的來(lái)說(shuō)，棧是一種非常實(shí)用的數(shù)據(jù)結(jié)構(gòu)，理解和掌握棧以及其操作對(duì)于深入理解計(jì)算機(jī)程序的運(yùn)行機(jī)制以及編寫高效的代碼有著重要的作用。

????????另外留一個(gè)括號(hào)匹配的題，代碼會(huì)放評(píng)論區(qū)。

【腳踢數(shù)據(jù)結(jié)構(gòu)】深入理解棧,腳踢數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,算法

?

六、總結(jié)

????????學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是一個(gè)漫長(zhǎng)的過(guò)程，但只要我們持續(xù)不斷地學(xué)習(xí)和實(shí)踐，就一定能夠掌握它。希望這篇文章能幫助你對(duì)棧有更深的理解和應(yīng)用。如果你有任何問(wèn)題或者想要討論的點(diǎn)，歡迎在下面的評(píng)論區(qū)留言。

? ? ? ?

????????更多C語(yǔ)言、Linux系統(tǒng)、ARM板實(shí)戰(zhàn)和數(shù)據(jù)結(jié)構(gòu)相關(guān)文章，關(guān)注專欄：

? ?手撕C語(yǔ)言

? ? ? ? ? ? 玩轉(zhuǎn)linux

????????????????????腳踢數(shù)據(jù)結(jié)構(gòu)

?? ? ? ? ? ? ? ? ?? ? ? ? ? 6818（ARM）開發(fā)板實(shí)戰(zhàn)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-642709.html

??寫在最后

  • 今天的分享就到這啦~
  • 覺(jué)得博主寫的還不錯(cuò)的煩勞?一鍵三連喔~
  • ??感謝關(guān)注??

到了這里，關(guān)于【腳踢數(shù)據(jù)結(jié)構(gòu)】深入理解棧的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來(lái)自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺(jué)得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包