java實現堆棧的方法

這篇文章將為大家詳細講解有關java實現堆棧的方法，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

在計算機領域，堆棧是一個不容忽視的概念，堆棧是一種數據結構。堆棧都是一種數據項按序排列的數據結構，只能在一端(稱為棧頂(top))對數據項進行插入和刪除。

堆棧有3種實現方式，實現方式為：

一、動態數組堆棧

　　頭文件還是用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;  
}

　　結果如下圖：

二、靜態數組堆棧

　　在靜態數組堆棧中，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;  
}

　　結果如下圖：

三、鏈式堆棧

　　由于只有堆棧頂部元素才可以被訪問，因此適用單鏈表可以很好實現鏈式堆棧，而且無長度限制。把一個元素壓入堆棧是通過在鏈表頭部添加一個元素實現。彈出一個元素是通過刪除鏈表頭部第一個元素實現。由于沒有長度限制，故不需要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實現堆棧的方法就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。