日韩V欧美V中文在线 ,亚洲gay片在线gv网站,4hu44四虎www在线影院麻豆

公告

淺談基礎算法之堆棧（五）

　我一直在想一個問題，我怎么能把一件事情說的明白呢？尤其是程序方面的知識點。思路清楚是非常重要的（只有思路清楚，表達清楚了，才能一目了然），這個清楚的思路怎么表現出來？我努力去做這件事情。這篇主要圍繞堆棧來展開話題。

　　序

　　堆棧是什么？

　　實現方式

　　　　靜態數組堆棧

　　　　動態數組堆棧

　　　　鏈式堆棧

　　總結

序

堆棧是什么？

實現方式

靜態數組堆棧

1、先把你要做的事情準備好。

/* ===========數據 */
#define STACK_INIT_MAXSIZE 100
char stack[STACK_INIT_MAXSIZE];
int top = -1;


/* ===========操作  */
void push(){
}

void pop(){
}

char get_top(){
}

int is_empty(){
}

int is_full(){
}

　　這么一羅列，一下就明朗了！

2、開始逐步實現每一個函數。

/* 
 * 用一個靜態數組實現堆棧
 *
 * (C) Copyright 2013 Chuan Shanjia
 */
#include <stdio.h>
#include <assert.h>


#define STACK_INIT_MAXSIZE 100
char stack[STACK_INIT_MAXSIZE];
int top = -1;


/* ===========基本操作  */
void push(char *value) {
    assert(!is_full());
    stack[++top] = *value;
}

void pop() {
    assert(!is_empty());
    top--;
}
char get_top() {
    assert(!is_empty());
    return stack[top];
}

/* ===========額外操作 */
int is_empty(){
    return top == -1;
}
int is_full(){
    return top == STACK_INIT_MAXSIZE - 1;
}

top存儲堆棧頂部元素的下標值。開始由于沒有頂部元素，所以初始值為-1，提示堆棧為空。

pop函數不需要從數組中刪除元素，只減少頂部元素的下標值就足矣。

3、現在測試一下上面的堆棧的正確性（在上面的代碼文件中，添加如下代碼）。

void print_stack(){
    int i = top;
    for(; i >= 0; i--){
        printf("%c ", stack[i]);
    }

    printf("\t");
    printf("棧頂元素:%c", get_top());
}

int main() {
    char c;
    scanf("%c", &c);
    while(c != '#'){
        if(c != '\n')
            push(&c);
        scanf("%c", &c);
    }

    printf("========打印堆棧\n");
    print_stack();
    printf("\n");

    printf("========出棧一次,打印堆棧\n");
    pop();
    print_stack();
    printf("\n");
    return 0;
}

打印結果如下：

動態數組堆棧

動態數組的特點：運行時才決定數組大小。——故需在原有的操作上，添加幾個操作。

1、先把你要做的事情準備好。

/* ===========數據 */
char *stack;
int stack_size;
int top = -1;


/* ===========操作  */
void create_stack(){
}   

void destroy_stack(){
}   

void push(){
}

void pop(){
}

char get_top(){
}

int is_empty(){
}

int is_full(){
}

2、開始逐步實現每一個函數。

#include <stdio.h>
#include <assert.h>
#include <malloc.h>

/* ===========數據 */
char *stack;
int stack_size;
int top = -1;


/* ===========操作  */
void create_stack(int size){
    assert(size > 0); 
    stack_size = size;
    stack = (char *)malloc(stack_size * sizeof(char));
    assert(stack != NULL);
}

void destroy_stack(){
    assert(stack_size > 0); 
    free(stack);
    stack_size = 0;
    stack = NULL;
}

void push(char *value){
    assert(!is_full());
    stack[++top] = *value;
}

void pop(){
    assert(!is_empty());
    --top;
}

char get_top(){
    assert(!is_empty());
    return stack[top];
}

int is_empty(){
    assert(stack_size > 0);
    return top == -1;
}

int is_full(){
    assert(stack_size > 0);
    return top == stack_size - 1;
}

3、現在測試一下上面的堆棧的正確性（在上面的代碼文件中，添加如下代碼）。

void print_stack(){
    int i = top;
    for(; i >= 0; i--){
        printf("%c ", stack[i]);
    }

    printf("\t");
    printf("棧頂元素:%c", get_top());
}

int main() {
    char c;
    create_stack(100);

    scanf("%c", &c);
    while(c != '#'){
        if(c != '\n')
            push(&c);
        scanf("%c", &c);
    }

    printf("========打印堆棧\n");
    print_stack();
    printf("\n");

    printf("========出棧一次,打印堆棧\n");
    pop();
    print_stack();
    printf("\n");

    destroy_stack();
    return 0;

}

打印結果如下：

動態分配的鏈式結構堆棧（又名鏈式堆棧）

push和pop我們可以這樣考慮，就是移動最后一個節點上的指針。push就把最后一個節點指針向后移動一位，pop就把指針向前移動一位。

1、先把你要做的事情準備好。

struct stack_node{
    char data;
    struct stack_node *prev;
};

struct stack_node *current;

/* ===========基本操作  */
void push(){
}

void pop(){
}

char get_top(){
}

/* ===========額外操作 */
int is_empty(){
}
void destroy(){
}

2、開始逐步實現每一個函數。

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

struct stack_node{
    char data;
    struct stack_node *prev;
};

struct stack_node *current;

/* ===========基本操作  */
void push(char *value){
    struct stack_node *new = (struct stack_node *)malloc(sizeof(struct stack_node));
    assert(new != NULL);
    new->data = *value;
    new->prev = current;
    current = new;
}

void pop(){
    assert(!is_empty());
    struct stack_node *last_node = current;
    current = current->prev;
    free(last_node);
}   

char get_top(){
    assert(!is_empty());
    return current->data;
}

/* ===========額外操作 */
int is_empty(){
    return current == NULL;
}   

void destroy(){
    while(!is_empty()){
        pop();
    }
}

3、現在測試一下上面的堆棧的正確性（在上面的代碼文件中，添加如下代碼）。

void print_stack(){
    struct stack_node *print_node = current;
    while(print_node != NULL){
        printf("%c ", print_node->data);
        print_node = print_node->prev;
    }

    printf("\t");
    printf("棧頂元素:%c", get_top());
}
    
int main() {
    char c;
    
    scanf("%c", &c);
    while(c != '#'){
        if(c != '\n')
            push(&c);
        scanf("%c", &c);
    }
    
    printf("========打印堆棧\n");
    print_stack();
    printf("\n");

    printf("========出棧一次,打印堆棧\n");
    pop(); 
    print_stack();
    printf("\n");

    destroy_stack();
    return 0;

}

打印結果如下：

總結

以上三種方案我們要找到它們的特點：

　　靜態數組堆棧要求結構的長度固定。而且這個要在編譯時確定（我們用define定義）。——此方案最簡單、最不容易出錯。

　　動態數組堆棧我們可以在運行時才決定數組的長度。——在復雜性和平衡性之間做權衡。

　　鏈式結構堆棧每個元素在需要時才單獨進行分配，這種方式對元素的數量幾乎沒有限制（排除考慮內存大小）。——最大程度的靈活性，需要消耗一定的內存，訪問特定元素的效率不如數組。

最后，希望我的這篇博文對你有所幫助。

川山甲

川山甲

公告