搜尋
首頁Javajava教程堆疊有幾種實作方式?

堆疊有幾種實作方式?

Jun 28, 2020 am 11:42 AM
堆疊實現方式

堆疊有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_emptyis_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中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
如何將Maven或Gradle用於高級Java項目管理,構建自動化和依賴性解決方案?如何將Maven或Gradle用於高級Java項目管理,構建自動化和依賴性解決方案?Mar 17, 2025 pm 05:46 PM

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

如何使用適當的版本控制和依賴項管理創建和使用自定義Java庫(JAR文件)?如何使用適當的版本控制和依賴項管理創建和使用自定義Java庫(JAR文件)?Mar 17, 2025 pm 05:45 PM

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

如何使用咖啡因或Guava Cache等庫在Java應用程序中實現多層緩存?如何使用咖啡因或Guava Cache等庫在Java應用程序中實現多層緩存?Mar 17, 2025 pm 05:44 PM

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

如何將JPA(Java持久性API)用於具有高級功能(例如緩存和懶惰加載)的對象相關映射?如何將JPA(Java持久性API)用於具有高級功能(例如緩存和懶惰加載)的對象相關映射?Mar 17, 2025 pm 05:43 PM

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

Java的類負載機制如何起作用,包括不同的類載荷及其委託模型?Java的類負載機制如何起作用,包括不同的類載荷及其委託模型?Mar 17, 2025 pm 05:35 PM

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

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 個月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
1 個月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
1 個月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.聊天命令以及如何使用它們
1 個月前By尊渡假赌尊渡假赌尊渡假赌

熱工具

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )專業的PHP整合開發工具

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

WebStorm Mac版

WebStorm Mac版

好用的JavaScript開發工具

SublimeText3 Mac版

SublimeText3 Mac版

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