c - 使用数组在 C 中实现堆栈

Question

我正在尝试使用数组在 C 中实现堆栈，只是为了学习。

我正在就如何实现这一点做出一些决定(欢迎提出建议)，基本上我提出了一个包含数组和顶部元素的索引“t”的堆栈结构。 然后我有一个函数来创建堆栈，该堆栈根据用户定义的大小分配内存，这就是到目前为止的样子:

更新:我已经使用了您的一些建议，这就是 2.0 版到目前为止的样子。我还为任何感兴趣的人创建了 1.0 版在线文档 ( here )

stack.h

// Interface for a stack data structure using arrays

typedef struct Stack{
    int t;          // Index of the top element in st
    int maxSize;    // Max size, allows to be resized when full
    int* st;        // Changed from int[] to int*
}Stack;

void initStack(Stack* s, int length);   // Declare the initial length
void push(Stack* s, int elem);
int pop(Stack* s);
int top(Stack* s);
int size_s(Stack* s);
int isEmpty(Stack* s);
void print(Stack* s);                   // Visualize the stack

stack.c

#include <stdio.h>
#include "stack.h"
#include <malloc.h>


void initStack(Stack* s, int length){
    s->st = malloc(sizeof(int)*length);
    s->maxSize = length;    // Initial size (this could also have a default number since it would be able to grow)
    s->t = -1;              // Initialize the size (index) to -1 to indicate an empty stack
}

void push(Stack* s, int elem){
    int* tmp;
    int i;
    if(size_s(s) == s->maxSize){  // Resize to double the size if full...
        // WOULD IT BE POSSIBLE TO REPLACE ALL OF THIS USING REALLOC() ?
        s->maxSize = s->maxSize * 2;
        tmp = malloc(sizeof(int)*s->maxSize);
        for(i = 0; i < size_s(s); i++){
            tmp[i] = s->st[i];
        }
        free(s->st);
        s->st = tmp;
    }

    int t = s->t + 1;
    s->t = t;
    s->st[t] = elem;
}

int top(Stack* s){
    if(isEmpty(s)) return -1;   // Empty stack
    return s->st[s->t];
}

int pop(Stack* s){
    int element;
    if(isEmpty(s)) return -1;    // Empty stack
    element = s->st[s->t];

    //////////////////////////////////////
    s->st[s->t] = 0;            // Empty the previous location, what other value could I use?
                                // Would it make sense to use free() ? I would need to malloc() again right?
    //////////////////////////////////////

    s->t = s->t - 1;
    return element;
}

int size_s(Stack* s){
    return (s->t) + 1;
}

int isEmpty(Stack* s){
    if(s->t == -1){
        return 1;   // True
    }else{
        return 0;   // False
    }
}

void print(Stack* s){
    int len = size_s(s);
    printf("Length: %d\n",len);
    int i;
    for(i = 0; i < len; i++){
        printf("%d ",s->st[i]);
    }
}

我尚未测试所有功能，但这是我如何实现它们的基本结构。

OBS:推送操作仍然不安全，因为我没有检查堆栈是否已满。

我正在运行的测试代码是

ma​​in.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

int main()
{
    Stack* s = malloc(sizeof(Stack));
    int i = 0;
    initStack(s,10);    // Declare an initial size

    for(i = 0; i < 12; i++){
        push(s,i);
        printf("Size of stack: %d, MaxSize: %d\n",size_s(s),s->maxSize);
    }
    printf("Top element: %d\n",top(s));
    print(s);
    puts("");
    popped = pop(s);
    printf("Popped: %d\n",popped);
    print(s);
    puts("");
    return 0;
}

输出

Size of stack: 1, MaxSize: 10
Size of stack: 2, MaxSize: 10
Size of stack: 3, MaxSize: 10
Size of stack: 4, MaxSize: 10
Size of stack: 5, MaxSize: 10
Size of stack: 6, MaxSize: 10
Size of stack: 7, MaxSize: 10
Size of stack: 8, MaxSize: 10
Size of stack: 9, MaxSize: 10
Size of stack: 10, MaxSize: 10
Size of stack: 11, MaxSize: 20
Size of stack: 12, MaxSize: 20
Top element: 11
Length: 12
0 1 2 3 4 5 6 7 8 9 10 11
Popped: 11
Length: 11
0 1 2 3 4 5 6 7 8 9 10

程序有bug，我只测试3个功能:

• 新堆栈
• 推
• 打印

该程序没有编译或显式运行时错误，它只会崩溃，我不知道为什么。 我不完全确定 newStack() 方法，因为我以一种奇怪的方式分配内存，我发现( here )，因此 Stack 结构的 typedef 有一个未知大小的数组。

在我做的其他一些测试中，有时我会在数组的某些单元格中得到一些垃圾值。

谢谢，我将继续发布此实现的所有修复和更新。

我也很想听听您对实现的建议，即头文件等。

Answer 1

Stack* s = (Stack*)malloc(sizeof(Stack)+length); 

应该是:

Stack* s = malloc(sizeof(Stack)+length*sizeof(int)); 

此外，您应该在结构中保存长度以用于溢出检查。