スタックは何通りの方法で実装できますか?

スタックには 3 つの実装方法があります。実装方法は次のとおりです: 1. 固定長の構造体が必要な静的配列スタック。長さはコンパイル時に決定する必要があります。2. 動的配列スタック。長さは実行時に決定できます。元の配列の長さを決定および変更します。3. チェーン構造スタック、オンラインでは長さなし、必要に応じてメモリ空間の割り当てを適用します。

スタックを実装するには 3 つの方法があります。実装方法は次のとおりです:

1. 静的array stack

静的配列スタックでは、STACK_SIZE はスタックに格納できる要素の最大値を表し、top_element が配列として使用されます。スタック内の要素を表す添え字。 top_element == -1 の場合はスタックが空であることを意味し、top_element == STACK_SIZE - 1 の場合はスタックがいっぱいであることを意味します。プッシュする場合、top_element は 1 ずつ増加します。top_element == 0 の場合、最初のスタック要素を表し、ポップする場合、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;  
}

結果は次のとおりです。

# 2. 動的配列stack

ヘッダー ファイルは引き続き 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;  
}

結果は次のとおりです。

3. チェーン タイプ stack

スタックの最上位要素のみにアクセスできるため、リンク スタックは単一リンク リストを使用して適切に実装でき、長さの制限はありません。要素をスタックにプッシュするには、リンクされたリストの先頭に要素を追加します。要素のポップは、リンクされたリストの先頭にある最初の要素を削除することによって実現されます。長さ制限がないため、

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 中国語 Web サイトの他の関連記事を参照してください。