堆疊有3種實作方式,實作方式為:1、靜態數組堆棧,要求結構的長度固定,長度在編譯時候就得確定;2、動態數組堆棧,長度可以在運行時候才確定以及可以更改原來數組的長度;3、鍊式結構堆棧,無長度上線,需要的時候再申請分配記憶體空間。
堆疊有3種實作方式,實作方式為:
一、靜態陣列堆疊
在靜態數組堆疊中,STACK_SIZE
表示堆疊所能儲存的元素的最大值,用top_element
作為數組下標來表示堆疊裡面的元素,當top_element == -1
的時候表示堆疊為空;當top_element == STACK_SIZE - 1
的時候表示堆疊為滿。 push的時候top_element
加1,top_element == 0
時表示第一個堆疊元素;pop的時候top_element
減1。
a_stack.c 原始碼如下:
[cpp] view plain copy /* ** ** 静态数组实现堆栈程序 a_stack.c ,数组长度由#define确定 */ #include"stack.h" #include<assert.h> #include<stdio.h> #define STACK_SIZE 100 /* 堆栈最大容纳元素数量 */ /* ** 存储堆栈中的数组和一个指向堆栈顶部元素的指针 */ static STACK_TYPE stack[STACK_SIZE]; static int top_element = -1; /* push */ void push(STACK_TYPE value) { assert(!is_full()); /* 压入堆栈之前先判断是否堆栈已满*/ top_element += 1; stack[top_element] = value; } /* pop */ void pop(void) { assert(!is_empty()); /* 弹出堆栈之前先判断是否堆栈已空 */ top_element -= 1; } /* top */ STACK_TYPE top(void) { assert(!is_empty()); return stack[top_element]; } /* is_empty */ int is_empty(void) { return top_element == -1; } /* is_full */ int is_full(void) { return top_element == STACK_SIZE - 1; } /* ** 定义一个print函数,用来打印堆栈里面的元素。 */ void print(void) { int i; i = top_element; printf("打印出静态数组堆栈里面的值: "); if(i == -1) printf("这是个空堆栈\n"); while(i!= -1) printf("%d ",stack[i--]); printf("\n"); } int main(void) { print(); push(10); push(9); push(7); push(6); push(5); push(4); push(3); push(2); push(1); push(0); printf("push压入数值后:\n"); print(); printf("\n"); pop(); pop(); printf("经过pop弹出几个元素后的堆栈元素:\n"); print(); printf("\n"); printf("top()调用出来的值: %d\n",top()); return 1; }
結果如下圖:
二、動態陣列堆疊
頭檔還是用stack.h
,改動的並不是很多,增加了stack_size
變數取代STACK_SIZE
來保存堆疊的長度,數組由一個指標來代替,在全域變數下預設為0。
create_stack
函數首先檢查堆疊是否已經創建,然後才分配所需數量的記憶體並檢查分配是否成功。 destroy_stack
函數先檢查堆疊是否存在,已經釋放記憶體之後把長度和指標變數重新設定為零。 is_empty
和 is_full
函數中加入了一條斷言,防止任何堆疊函數在堆疊被建立之前就被呼叫。
d_stack.c
原始程式碼如下:
[cpp] view plain copy /* ** 动态分配数组实现的堆栈程序 d_stack.c ** 堆栈的长度在创建堆栈的函数被调用时候给出,该函数必须在任何其他操作堆栈的函数被调用之前条用。 */ #include"stack.h" #include<stdio.h> #include<malloc.h> #include<assert.h> /* ** 用于存储堆栈元素的数组和指向堆栈顶部元素的指针 */ static STACK_TYPE *stack; static int stack_size; static int top_element = -1; /* create_stack */ void create_stack(size_t size) { assert(stack_size == 0); stack_size = size; stack = (STACK_TYPE *)malloc(stack_size * sizeof(STACK_TYPE)); if(stack == NULL) perror("malloc分配失败"); } /* destroy */ void destroy_stack(void) { assert(stack_size > 0); stack_size = 0; free(stack); stack = NULL; } /* push */ void push(STACK_TYPE value) { assert(!is_full()); top_element += 1; stack[top_element] = value; } /* pop */ void pop(void) { assert(!is_empty()); top_element -= 1; } /* top */ STACK_TYPE top(void) { assert(!is_empty()); return stack[top_element]; } /* is_empty */ int is_empty(void) { assert(stack_size > 0); return top_element == -1; } /* is_full */ int is_full(void) { assert(stack_size > 0); return top_element == stack_size - 1; } /* ** 定义一个print函数,用来打印堆栈里面的元素。 */ void print(void) { int i; i = top_element; printf("打印出动态数组堆栈里面的值: "); if(i == -1) printf("这是个空堆栈\n"); while(i!= -1) printf("%d ",stack[i--]); printf("\n"); } int main(void) { create_stack(50); print(); push(10); push(9); push(7); push(6); push(5); push(4); push(3); push(2); push(1); push(0); printf("push压入数值后:\n"); print(); printf("\n"); pop(); pop(); printf("经过pop弹出几个元素后的堆栈元素:\n"); print(); printf("\n"); printf("top()调用出来的值: %d\n",top()); destroy_stack(); return 1; }
結果如下圖:
#三、鏈式堆疊
由於只有堆疊頂部元素才可以被訪問,因此適用單鍊錶可以很好實現鍊式堆疊,而且無長度限制。把一個元素壓入堆疊是透過在鍊錶頭部添加一個元素來實現。彈出一個元素是透過刪除鍊錶頭部第一個元素來實現。由於沒有長度限制,故不需要create_stack
函數,需要destroy_stack
進行釋放記憶體以避免記憶體洩漏。
頭檔stack.h
不變,l_stack.c
原始程式碼如下:
[cpp] view plain copy /* ** 单链表实现堆栈,没有长度限制 */ #include"stack.h" #include<stdio.h> #include<malloc.h> #include<assert.h> #define FALSE 0 /* ** 定义一个结构以存储堆栈元素。 */ typedef struct STACK_NODE { STACK_TYPE value; struct STACK_NODE *next; } StackNode; /* 指向堆栈中第一个节点的指针 */ static StackNode *stack; /* create_stack */ void create_stack(size_t size) {} /* destroy_stack */ void destroy_stack(void) { while(!is_empty()) pop(); /* 逐个弹出元素,逐个释放节点内存 */ } /* push */ void push(STACK_TYPE value) { StackNode *new_node; new_node = (StackNode *)malloc(sizeof(StackNode)); if(new_node == NULL) perror("malloc fail"); new_node->value = value; new_node->next = stack; /* 新元素插入链表头部 */ stack = new_node; /* stack 重新指向链表头部 */ } /* pop */ void pop(void) { StackNode *first_node; assert(!is_empty()); first_node = stack; stack = first_node->next; free(first_node); } /* top */ STACK_TYPE top(void) { assert(!is_empty()); return stack->value; } /* is_empty */ int is_empty(void) { return stack == NULL; } /* is_full */ int is_full(void) { return FALSE; } /* ** 定义一个print函数,用来打印堆栈里面的元素。 */ void print(void) { StackNode *p_node; p_node = stack; printf("打印出链式堆栈里面的值: "); if(p_node == NULL) printf("堆栈为空\n"); while(p_node != NULL) { printf("%d ", p_node->value); p_node = p_node->next; } printf("\n"); } int main(void) { print(); push(10); push(9); push(7); push(6); push(5); push(4); push(3); push(2); push(1); push(0); printf("push压入数值后:\n"); print(); printf("\n"); pop(); pop(); printf("经过pop弹出几个元素后的堆栈元素:\n"); print(); printf("\n"); printf("top()调用出来的值: %d\n",top()); destroy_stack(); return 1; }
結果如下圖:
推薦教學:《java影片教學》
以上是堆疊有幾種實作方式?的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本文討論了使用Maven和Gradle進行Java項目管理,構建自動化和依賴性解決方案,以比較其方法和優化策略。

本文使用Maven和Gradle之類的工具討論了具有適當的版本控制和依賴關係管理的自定義Java庫(JAR文件)的創建和使用。

本文討論了使用咖啡因和Guava緩存在Java中實施多層緩存以提高應用程序性能。它涵蓋設置,集成和績效優勢,以及配置和驅逐政策管理最佳PRA

本文討論了使用JPA進行對象相關映射,並具有高級功能,例如緩存和懶惰加載。它涵蓋了設置,實體映射和優化性能的最佳實踐,同時突出潛在的陷阱。[159個字符]

Java的類上載涉及使用帶有引導,擴展程序和應用程序類負載器的分層系統加載,鏈接和初始化類。父代授權模型確保首先加載核心類別,從而影響自定義類LOA


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

Atom編輯器mac版下載
最受歡迎的的開源編輯器

PhpStorm Mac 版本
最新(2018.2.1 )專業的PHP整合開發工具

禪工作室 13.0.1
強大的PHP整合開發環境

WebStorm Mac版
好用的JavaScript開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)