數據結構4-棧、隊列

摘要：本文系統介紹了棧和隊列兩種基礎數據結構。棧采用"先進后出"原則，分為順序棧和鏈式棧，詳細說明了壓棧、出棧等基本操作及其實現方法。隊列遵循"先進先出"規則，同樣分為順序隊列和鏈式隊列，重點講解了循環隊列的判滿條件（犧牲一個存儲空間）和操作實現。最后通過編程練習展示了如何用鏈式棧（需兩次壓棧）和鏈式隊列（直接實現）來完成輸入輸出順序一致的功能，提供了完整的代碼實現方案。文章內容涵蓋數據結構基本概念、分類及具體實現。

一、棧

1、棧的概念：

????????1.?先進后出，后進先出
2. 棧頂：允許入棧和出棧的一端稱為棧頂
3. 棧底：不允許入棧和出棧的一端稱為棧底
4. 入棧（壓棧）：將元素放入棧頂位置
5. 出棧（彈棧）：將棧頂元素取出
6. 棧針：記錄棧頂位置的標記

2、棧的分類：

????????順序棧、鏈式棧

3、順序棧：

3.1 概念:

????????1. 增棧：棧的方向自低向高增長
2. 減棧：棧的方向自高向低增長
3. 空棧：棧針指向要入棧的位置
4. 滿棧：棧針指向棧頂元素的位置

3.2 順序棧的實現
3.2.1 節點的定義

3.2.2 順序棧的創建
  • 申請存放標簽的空間
  • 申請存放數據的空間

3.2.3?順序棧的銷毀：
  • 銷毀存放數據的空間
  • 銷毀存放標簽的空間

3.2.4判斷是否為空棧
  • 棧針為0即為空棧

3.2.5是否為滿棧
  • 棧針與tlen相同即為滿棧

3.2.6壓棧(輸入數據)

  • 將元素放入棧頂位置

  • 棧針位置++

3.2.7出棧
  • 棧針位置--
  • 將棧頂元素出棧

4、鏈式棧

4.1概念

  1. 使用鏈表的思想實現鏈式棧
  2. 參考單向鏈表節點定義
  3. 壓棧參考單向鏈表頭插法
  4. 出棧返回鏈表第一個有效節點的值，并刪除該節點
  5. 銷毀棧參考單向鏈表銷毀

4.2鏈式棧的實現

#include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"

//創建、判斷、插入頭插法、出棧、銷毀
linknode *create_empty_linkstack(void)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return NULL;
}
ptmpnode->pnext = NULL;

? ? return ptmpnode;?
}


int is_empty_linkstack(linknode *phead)
{
return NULL == phead->pnext; ? ??
}


int push_linkstack(linknode *phead,datatype tmpdata)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}
ptmpnode->data = tmpdata;
ptmpnode->pnext = phead->pnext;
phead->pnext = ptmpnode;

? ? return 0;
}


datatype pop_linkstack(linknode *phead)
{
linknode *ptmpnode = NULL;
datatype deledata;

? ? ptmpnode = phead->pnext;
deledata = ptmpnode->data;
phead->pnext = ptmpnode->pnext;
free(ptmpnode);
return deledata; ??

}


int destroy_linkstack(linknode **pphead)
{
linknode *ptmpnode = NULL;
linknode *pfreenode = NULL;

? ? ptmpnode = *pphead;
pfreenode = *pphead;
while (ptmpnode != NULL)
{
ptmpnode = ptmpnode->pnext;
free(pfreenode);
pfreenode = ptmpnode;
}
*pphead = NULL;

? ? return 0;

}

二、隊列

1、概念：

????????1. 先進先出，后進后出
2. 隊頭：出隊的一端
3. 隊尾：入隊的一端
4. 入隊：將元素放入隊列末尾
5. 出隊：將元素從隊頭中取出

2、分類：

? ? ? ? 順序隊列（循環隊列）、鏈式隊列

3、順序隊列

3.1基本類型

3.2順序隊列的實現
3.2.1順序隊列的創建

3.2.2順序隊列銷毀

3.2.3判斷順序隊列是否為空

3.2.4?判斷順序隊列是否為滿
  • 為避免循環隊列空與滿的條件沖突，犧牲一個存放數據的空間，將tail+1 == head作為判斷隊滿的條件
  • 循環隊列如果head或者tail下標超過tlen范圍，需要對tlen取余，保障head和tail的值在隊列下標范圍內變

3.2.5順序隊列入隊

3.2.6順序隊列出隊

4、鏈式隊列

4.1概念

  1. 使用鏈表的思想實現鏈式棧
  2. 參考單向鏈表節點定義
  3. 壓棧參考單向鏈表尾插法
  4. 出棧返回鏈表第一個有效節點的值，并刪除該節點
  5. 銷毀棧參考單向鏈表銷毀

4.2鏈式隊列的實現

#include "linkqueue.h"
#include <stdio.h>
#include <stdlib.h>

//創建、判斷、插入只能尾插法、出隊、銷毀
linknode *create_empty_linkqueue(void)
{?
//單向鏈表創建

? ? linknode *ptmpqueue = NULL;
ptmpqueue = malloc( sizeof(linknode));
if (NULL == ptmpqueue)
{
perror("fail to malloc");
return NULL;
}
ptmpqueue->pnext = NULL;
return ptmpqueue;

}

int is_empty_linkqueue(linknode *phead)
{
//鏈式隊判斷是否為NULL

? ? return NULL == phead->pnext;?

}

int enter_linkqueue(linknode *phead, datatype tmpdata)
{
//尾插法
linknode *ptmpqueue = NULL;
linknode *plastqueue = NULL;

? ? ptmpqueue = malloc(sizeof(linknode));
if (NULL == ptmpqueue)
{
perror("fail to malloc");
return -1;
}
ptmpqueue->data = tmpdata;
ptmpqueue->pnext = NULL;

? ? plastqueue = phead;
while (plastqueue->pnext != NULL)
{
plastqueue = plastqueue->pnext;
}
plastqueue->pnext = ptmpqueue;

? ? return 0;

}

datatype quit_linkqueue(linknode *phead)
{
//鏈式隊列的出隊
linknode *ptmpqueue = NULL;
datatype tmpdata;
if (is_empty_linkqueue(phead))
{
return -1;
}
ptmpqueue = phead->pnext;
phead->pnext = ptmpqueue->pnext;
tmpdata = ptmpqueue->data;
free(ptmpqueue);

? ? return tmpdata;
}

int destroy_linkqueue(linknode **pphead)
{
//單向隊表銷毀
linknode *ptmpqueue = NULL;
linknode *pfreequeue = NULL;

? ? ptmpqueue = pfreequeue = *pphead;
while (ptmpqueue != NULL)
{
ptmpqueue = ptmpqueue->pnext;
free(pfreequeue);
pfreequeue = ptmpqueue;
}
*pphead = NULL;
return 0;

}

三、練習

題目：???實現終端輸入若干個數（-1結束），輸入和輸出順序相同

eg：輸入：1? 2? 3? 4? 5? -1

? ? ? ??輸出：1? 2? 3? 4? 5? -1

1、利用鏈式棧實現?

（1）題目分析

????????鏈式棧只能使用頭插法實現，所以輸入：1 2 3 4 5 則輸出：5 4 3 2 1 要實現題目操作需得再壓棧一次再出棧一次便可以實現

（2）注意事項

? ? ? ? 1）實現終端接收數，在循環中利用scanf接受數據，用if條件語句結束循環

? ? ? ? 2)? 利用兩個鏈式棧實現壓棧—出棧—壓棧—出棧

????????????????兩個方法實現，寫一個函數實現，在main函數中調用

（3）代碼實現

????????linkstack.h

#ifndef __LINKSTACK_H__
#define __LINKSTACK_H__

typedef int datatype;
typedef struct node
{
datatype data;
struct node *pnext;
}linknode;

extern linknode *create_empty_linkstack(void);
extern int is_empty_linkstack(linknode *phead);
extern int push_linkstack(linknode *phead,datatype tmpdata);
extern datatype pop_linkstack(linknode *phead);
extern int chance_linkstack(linknode *phead,linknode *phead2);

#endif

????????linkstack.c

#include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"

linknode *create_empty_linkstack(void)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return NULL;
}
ptmpnode->pnext = NULL;

? ? return ptmpnode;
}

int is_empty_linkstack(linknode *phead)
{
return NULL == phead->pnext;
}

int push_linkstack(linknode *phead,datatype tmpdata)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}
ptmpnode->data = tmpdata;
ptmpnode->pnext = phead->pnext;
phead->pnext = ptmpnode;

? ? return 0;
}

datatype pop_linkstack(linknode *phead)
{
linknode *ptmpnode = NULL;
datatype tmpdata;

? ? if (is_empty_linkstack(phead))
{
return -1;
}
ptmpnode = phead->pnext;
tmpdata = ptmpnode->data;
phead->pnext = ptmpnode->pnext;
free(ptmpnode);
return tmpdata;

}

int chance_linkstack(linknode *phead,linknode *phead2)
{
linknode *ptmpnode = NULL;
linknode *ptmpnode1 = NULL;

? ? datatype tmpdata;

? ? if (is_empty_linkstack(phead))
{
return -1;
}

? ? ptmpnode = malloc(sizeof(linknode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return -1;
}
ptmpnode->pnext = phead2->pnext;
phead2->pnext = ptmpnode;?

? ? tmpdata = phead->pnext->data;
ptmpnode->data = tmpdata;

? ? return 0;
}

????????main.c

#include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"

int main(void)
{
linknode *plinkstack = NULL;
linknode *plinkstack2 = NULL;

plinkstack = create_empty_linkstack();
plinkstack2 = create_empty_linkstack();

? ? while (1)
{
scanf("%d",&plinkstack->data);
if (-1 == plinkstack->data)
{
break;
}
push_linkstack(plinkstack,plinkstack->data);
}


#if 0
//查看是否入棧成功
while (!is_empty_linkstack(plinkstack))
{
printf("%d ",pop_linkstack(plinkstack));
}
printf("\n");
#endif

#if 0
//難為版：自己創個函數
while (1)
{

? ? ? ? if (is_empty_linkstack(plinkstack))
{
break;
}

? ? ? ? chance_linkstack(plinkstack,plinkstack2);
pop_linkstack(plinkstack);

? ? }

? ? while (!is_empty_linkstack(plinkstack2))
{
printf("%d ",pop_linkstack(plinkstack2));
}
printf("\n");
#endif


? ? //靈活版：簡單快捷

? ? while (!is_empty_linkstack(plinkstack))
{

? ? ? ? push_linkstack(plinkstack2,pop_linkstack(plinkstack));
printf("%d ",pop_linkstack(plinkstack2));
}
printf("\n");


? ? return 0;
}

#if 0

? ? ? ? 中間內容可以注釋掉

#endif

2、鏈式隊列實現

（1）題目分析：

? ? ? ? 隊列采用的就是尾插法，只需要在鏈式隊列中加入接收數據。

（2）注意事項：

????????注意事項尾插法中的找最后一個節點的條件是while(ptmpqueue->pnext != NULL)

（3）代碼實現：

????????linkqueue.h

#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__

typedef int datatype;
typedef struct node?
{
datatype data;
struct node *pnext;
}linknode;

extern linknode *create_empty_linkqueue(void);
extern int is_empty_linkqueue(linknode *phead);
extern int enter_linkqueue(linknode *phead, datatype tmpdata);
extern datatype quit_linkqueue(linknode *phead);

#endif

????????linkqueue.c

#include "linkqueue.h"
#include <stdio.h>
#include <stdlib.h>

linknode *create_empty_linkqueue(void)
{
linknode *ptmpqueue = NULL;
ptmpqueue = malloc( sizeof(linknode));
if (NULL == ptmpqueue)
{
perror("fail to malloc");
return NULL;
}
ptmpqueue->pnext = NULL;
return ptmpqueue;
}


int is_empty_linkqueue(linknode *phead)
{
return NULL == phead->pnext;
}

int enter_linkqueue(linknode *phead, datatype tmpdata)
{
linknode *ptmpqueue = NULL;
linknode *plastqueue = NULL;

? ? ptmpqueue = malloc(sizeof(linknode));
if (NULL == ptmpqueue)
{
perror("fail to malloc");
return -1;
}

? ? ptmpqueue->data = tmpdata;
ptmpqueue->pnext = NULL;

? ? plastqueue = phead;
while (plastqueue->pnext != NULL)
{
plastqueue = plastqueue->pnext;
}
plastqueue->pnext = ptmpqueue;

? ? return 0;
}

datatype quit_linkqueue(linknode *phead)
{
linknode *ptmpqueue = NULL;
linknode *pfreequeue = NULL;
datatype tmpdata;

? ? if (is_empty_linkqueue(phead))
{
return -1;
}
ptmpqueue = phead->pnext;
phead->pnext = ptmpqueue->pnext;
tmpdata = ptmpqueue->data;
free(ptmpqueue);
return tmpdata;

}

????????main.c

#include <stdio.h>
#include <stdlib.h>
#include "linkqueue.h"

int main(void)
{
linknode *plinkqueue = NULL;

? ? plinkqueue = create_empty_linkqueue();

? ? while (1)
{
scanf("%d",&plinkqueue->data);

? ? ? ? if (-1 == plinkqueue->data)
{
break;
}
enter_linkqueue(plinkqueue,plinkqueue->data);
}

? ? while (!is_empty_linkqueue(plinkqueue))
{
printf("%d",quit_linkqueue(plinkqueue));
}
printf("\n");

? ? return 0;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/917924.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/917924.shtml
英文地址，請注明出處：http://en.pswp.cn/news/917924.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

大數據spark、hasdoop 深度學習、機器學習算法的音樂平臺用戶情感分析系統設計與實現

大數據spark、hasdoop 深度學習、機器學習算法的音樂平臺用戶情感分析系統設計與實現

大數據spark、hasdoop 深度學習、機器學習算法的音樂平臺用戶情感分析系統設計與實現
閱讀更多...
視頻匯聚系統EasyCVR調用設備錄像保活時視頻流不連貫問題解決方案

視頻匯聚系統EasyCVR調用設備錄像保活時視頻流不連貫問題解決方案

在使用EasyCVR過程中&#xff0c;有用戶反饋調用設備錄像保活功能時&#xff0c;出現視頻流不連貫的情況。針對這一問題&#xff0c;我們經過排查與測試&#xff0c;整理出如下解決步驟&#xff0c;供開發者參考&#xff1a;具體解決步驟1&#xff09;先調用登錄接口完成鑒權確…
閱讀更多...
【保姆級喂飯教程】python基于mysql-connector-python的數據庫操作通用封裝類（連接池版）

【保姆級喂飯教程】python基于mysql-connector-python的數據庫操作通用封裝類（連接池版）

目錄項目環境一、db_config.py二、mysql_executor.py三、test/main.py在使用mysql-connector-python連接MySQL數據庫的時候&#xff0c;如同Java中的jdbc一般&#xff0c;每條sql需要創建和刪除連接&#xff0c;很自然就想到寫一個抽象方法&#xff0c;但是找了找沒有官方標準的…
閱讀更多...
【MCP服務】藍耘元生代 | 藍耘MCP平臺來襲！DeepSeek MCP服務器玩轉大模型集成

【MCP服務】藍耘元生代 | 藍耘MCP平臺來襲！DeepSeek MCP服務器玩轉大模型集成

【作者主頁】Francek Chen 【專欄介紹】???人工智能與大模型應用??? 人工智能&#xff08;AI&#xff09;通過算法模擬人類智能&#xff0c;利用機器學習、深度學習等技術驅動醫療、金融等領域的智能化。大模型是千億參數的深度神經網絡&#xff08;如ChatGPT&#xff09…
閱讀更多...
Spring Boot 整合 Minio 實現高效文件存儲解決方案(本地和線上)

Spring Boot 整合 Minio 實現高效文件存儲解決方案(本地和線上)

文章目錄前言一、配置1.配置文件&#xff1a;application.yml2.配置類&#xff1a;MinioProperties3.工具類&#xff1a;MinioUtil3.1 初始化方法3.2 核心功能3.3 關鍵技術點二、使用示例1.控制器類&#xff1a;FileController2.服務類3.效果展示總結前言 Minio 是一個高性能的…
閱讀更多...
【Unity3D實例-功能-鏡頭】第三人稱視覺-鏡頭優化

【Unity3D實例-功能-鏡頭】第三人稱視覺-鏡頭優化

這一篇我們一起來調整一下Cinemachine的第三人稱視覺的鏡頭設置。一般用于ARPG角色扮演游戲的場景中。Unity里頭&#xff0c;這種視角簡直就是標配。來吧&#xff0c;咱們一起研究研究怎么調出這種視角效果&#xff01;目錄&#xff1a;1.調整虛擬攝像機的Y軸2.調整虛擬攝像機的…
閱讀更多...
二叉樹算法之【中序遍歷】

二叉樹算法之【中序遍歷】

目錄 LeetCode-94題 LeetCode-94題 給定一個二叉樹的根節點root&#xff0c;返回它的中序遍歷結果。 class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result new ArrayList<>();order(root, result);return res…
閱讀更多...
Android14的QS面板的加載解析

Android14的QS面板的加載解析

/frameworks/base/packages/SystemUI/src/com/android/systemui/statusbar/phone/CentralSurfacesImpl.java QS 面板的創建 getNotificationShadeWindowView()&#xff1a;整個systemui的最頂級的視圖容器&#xff08;super_notification_shade.xml&#xff09;R.id.qs_frame &…
閱讀更多...
解鎖webpack核心技能（二）：配置文件和devtool配置指南

解鎖webpack核心技能（二）：配置文件和devtool配置指南

一、配置文件webpack 提供的 cli 支持很多的參數&#xff0c;例如 --mode 。在我們平時的開發過程中&#xff0c;我們要學習很多的功能&#xff0c;這些很多都是可以用參數來完成的。那么后邊就會導致參數越來越多&#xff0c;我們使用命令特別的不方便&#xff0c;所以我們會使…
閱讀更多...
Gitlab+Jenkins+K8S+Registry 建立 CI/CD 流水線

Gitlab+Jenkins+K8S+Registry 建立 CI/CD 流水線

一、前言 DevOps是一種將開發&#xff08;Development&#xff09;和運維&#xff08;Operations&#xff09;相結合的軟件開發方法論。它通過自動化和持續交付的方式&#xff0c;將軟件開發、測試和部署等環節緊密集成&#xff0c;以提高效率和產品質量。在本篇博客中&#xf…
閱讀更多...
【Linux】特效爆滿的Vim的配置方法 and make/Makefile原理

【Linux】特效爆滿的Vim的配置方法 and make/Makefile原理

一、軟件包管理器 1、Linux下安裝軟件的常見方式&#xff1a; 1&#xff09;源代碼安裝——不推薦。 2&#xff09;rpm包安裝——不推薦。 3&#xff09;包管理器安裝——推薦 2、安裝軟件命令 # Centos$ sudo yum install -y lrzsz# Ubuntu$ sudo apt install -y lrzsz 3、卸…
閱讀更多...
Spring Boot Actuator 監控功能的簡介及禁用

Spring Boot Actuator 監控功能的簡介及禁用

Spring Boot Actuator: Production-ready Features 1. 添加依賴 <dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-actuator</artifactId></dependency> </dependencie…
閱讀更多...
Matlab（1）

Matlab（1）

一、基本操作1. matlab四則運算規則&#xff1a;先乘除后加減&#xff0c;從左到右2、對數和指數的表示sin(pi^0.5)log(tan(1))exp&#xff08;sin&#xff08;10&#xff09;&#xff09;3、類型&#xff1a;matlab變量默認為double4、who&whos&#xff1a;命令行輸入who&…
閱讀更多...
Kotlin Android 開發腳手架封裝

Kotlin Android 開發腳手架封裝

Kotlin Android 開發腳手架封裝&#xff08;模塊化版本&#xff09; 我將按照模塊化設計原則&#xff0c;將腳手架拆分為多個文件&#xff0c;每個文件負責特定功能領域&#xff1a; 1. 核心初始化模塊 文件路徑: core/AppScaffold.kt object AppScaffold {lateinit var contex…
閱讀更多...
Flutter 報錯解析：No TabController for TabBar 的完整解決方案

Flutter 報錯解析：No TabController for TabBar 的完整解決方案

目錄 Flutter 報錯解析&#xff1a;No TabController for TabBar 的完整解決方案 一、錯誤場景&#xff1a;當 TabBar 失去 "指揮官" 二、為什么 TabBar 必須依賴 Controller&#xff1f; 1. TabBar 與 TabController 的協作關系 2. 狀態管理的核心作用 3. 實戰…
閱讀更多...
【24】C++實戰篇——【 C++ 外部變量】 C++多個文件共用一個枚舉變量，外部變量 extern，枚舉外部變量 enum

【24】C++實戰篇——【 C++ 外部變量】 C++多個文件共用一個枚舉變量，外部變量 extern，枚舉外部變量 enum

文章目錄1 方法2 外部變量 應用2.1 普通外部全局變量2.2 枚舉外部全局變量 應用2.2.2 枚舉外部變量優化c多個文件中如何共用一個全局變量 c頭文件的使用和多個文件中如何共用一個全局變量 C共享枚舉類型給QML 1 方法 ①頭文件中 聲明外部全局變量&#xff1b; ②在頭文件對…
閱讀更多...
Linux SELinux 核心概念與管理

Linux SELinux 核心概念與管理

Linux SELinux 核心概念與管理一、SELinux 基本概念 SELinux 即安全增強型 Linux&#xff08;Security-Enhanced Linux&#xff09;&#xff0c;由美國國家安全局&#xff08;NSA&#xff09;開發&#xff0c;是一套基于強制訪問控制&#xff08;MAC&#xff09;的安全機制&…
閱讀更多...
Git 中**未暫存**和**未跟蹤**的區別：

Git 中**未暫存**和**未跟蹤**的區別：

文件狀態分類 Git 中的文件有以下幾種狀態&#xff1a; 工作區文件狀態&#xff1a; ├── 未跟蹤 (Untracked) ├── 已跟蹤 (Tracked)├── 未修改 (Unmodified) ├── 已修改未暫存 (Modified/Unstaged)└── 已暫存 (Staged)1. 未跟蹤 (Untracked) 定義&#xff1a;Gi…
閱讀更多...
前端1.0

前端1.0

目錄 一、 什么是前端 二、 HTML 1.0 概述 2.0 注釋 三、開發環境的搭建 1.0 插件 2.0 筆記 四、 常見標簽&#xff08;重點&#xff09; 四、案例展示&#xff08;圖片代碼&#xff09; 五、CSS引入 一、 什么是前端 web前端 用來直接給用戶呈現一個一個的網頁 …
閱讀更多...
Flutter鏡像替換

Flutter鏡像替換

一、核心鏡像替換&#xff08;針對 Maven 倉庫&#xff09; Flutter 依賴的 Google Maven 倉庫&#xff08;https://maven.google.com 或 https://dl.google.com/dl/android/maven2&#xff09;可替換為國內鏡像&#xff0c;常見的有&#xff1a;阿里云鏡像&#xff08;推薦&am…
閱讀更多...
最新文章

Copyright @ 2022~2023