реализация метода push стека в C-программировании

Question

разработчики!У меня вопрос о методе push () стека в C!

Я реализовал свой собственный метод push () в C!но я не могу понять результаты!

Мой код стека ниже

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

#define MAX_SIZE 10

int top = -1;
int array[MAX_SIZE];

void init(){
    top = -1;
}

void push(int array[], int data){

    if(top > MAX_SIZE-1)
        fprintf(stderr, "invalid top %d\n", top+1);
    else{
        array[++top] = data; // top == 9, ++top == 10
        printf("top: %d data: %d\n", top+1, array[top]); // top == 11, top == 10
    }
}
void pop(int array[]){

}
void peek(int array[]){

}

int main() {
   int data = 1;

   for (int i=0; i<MAX_SIZE; i++)
        push(array, data++);
   push(array, 100);
   push(array, 200); // invalid top
   push(array, 300); // invalid top
   return 0;
}

, а результат этого кода ниже

top: 1 data: 1
top: 2 data: 2
top: 3 data: 3
top: 4 data: 4
top: 5 data: 5
top: 6 data: 6
top: 7 data: 7
top: 8 data: 8
top: 9 data: 9
top: 10 data: 10
top: 11 data: 100
invalid top 11 
invalid top 11

То, что я наденуне понимаю, это .. в результатах, когда top: 11, на самом деле, это как top: top + 1.Если вы посмотрите на оператор else в моем методе push (), вы можете заметить его.

, но в выражении else, когда

printf("top: %d data: %d\n", 11, array[10]);
the result: top: 11 data: 100

, я думаю, что это должно быть ошибкой.потому что я объявил размер массива как 10, который является MAX_SIZE.поэтому размер индекса будет 0 ~ 9. но как мог работать массив [10] ??

Я действительно не понимаю этого.

Answer 1

В качестве дополнения к другим ответам я хотел бы добавить более удобную реализацию в ваш стек, используя структуру.Поведение программы немного изменено, возможно, на желаемое.

#include <stdio.h>

#define MAX_SIZE 10

typedef struct Stack Stack;
void stackPush(Stack* s, int data);

struct Stack{
    unsigned int head;
    int arr[MAX_SIZE];

    void(*push)(Stack* s, int data);
};

void stackPush(Stack* s, int data) {
    if (s->head < MAX_SIZE) {
        s->arr[s->head] = data;  // push to stack
        printf("Head: %d. Data: %d.\n", s->head, s->arr[s->head]); 
        s->head++;  // move forward
    }

    else
        fprintf(stderr, "Stack is full! (head at: %d)\n", s->head);
}

int main() {
    // Initialize the stack
    Stack s;
    s.head = 0;
    s.push = stackPush;

    // Push the data
    int data = 1;

    int i;
    for (i = 0; i < MAX_SIZE; i++)
        s.push(&s, data++);

    s.push(&s, 100); // 
    s.push(&s, 200); // trying to push to a full stack
    s.push(&s, 300); // 

    return 0;
}

Что выдаст

Head: 0. Data: 1.
Head: 1. Data: 2.
Head: 2. Data: 3.
Head: 3. Data: 4.
Head: 4. Data: 5.
Head: 5. Data: 6.
Head: 6. Data: 7.
Head: 7. Data: 8.
Head: 8. Data: 9.
Head: 9. Data: 10.
Stack is full! (head at: 10)
Stack is full! (head at: 10)
Stack is full! (head at: 10)

Answer 2

Вы можете сделать это, потому что C позволяет вам сделать это.Но вы не должны этого делать, потому что писать в нераспределенной области памяти опасно.Вашему массиву присвоено 10 целых чисел длины.10 целых чисел выделенной памяти.У 11-го целого числа, к которому вы пытаетесь получить доступ, нет выделенной памяти для него.

Как указано в комментарии, функция, которую вы хотели бы получить, если вы хотите, чтобы ваш код выдал ошибку, является проверкой привязки.И это именно то, что вы делаете в первой части вашей push функции.

Измените ваше условие на top >= MAX_SIZE - 1, чтобы исправить проблему.

Что касается лучшего способа реализациистек, вы можете попытаться реализовать один поверх связанного списка, который позволяет вам управлять вашим стеком в областях памяти, которые больше не нужны.

Вы также можете использовать unsigned int для индексов массива, потому что вам не нужны отрицательныецифры там.

Answer 3

На самом деле, в вашем коде top равен -1, тогда как по сравнению с max_size-1 это означает 9, условие выполняется до тех пор, пока значение top не станет 9. это означает 10 раз для top = -1,0,1,2, 3,4,5,6,7,8. Поэтому он действителен до массива [10].

Попробуйте следующий код.

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

#define MAX_SIZE 10

int top = -1;
int array[MAX_SIZE];

void init(){
    top = -1;
}

void push(int array[], int data){
++top;
    if(top > MAX_SIZE-1)
        fprintf(stderr, "invalid top %d\n", top+1);
    else{
        array[top] = data; // top == 9, ++top == 10
        printf("top: %d data: %d\n", top+1, array[top]); // top == 11, top == 10
    }
}
void pop(int array[]){

}
void peek(int array[]){

}

int main() {
   int data = 1;

   for (int i=0; i<MAX_SIZE; i++)
        push(array, data++);
   push(array, 100);
   push(array, 200); // invalid top
   push(array, 300); // invalid top
   return 0;
}

Я думаю, это то, что вы хотите.

top: 1 data: 1                                                                                                                                                                               
top: 2 data: 2                                                                                                                                                                               
top: 3 data: 3                                                                                                                                                                               
top: 4 data: 4                                                                                                                                                                               
top: 5 data: 5                                                                                                                                                                               
top: 6 data: 6                                                                                                                                                                               
top: 7 data: 7                                                                                                                                                                               
top: 8 data: 8                                                                                                                                                                               
top: 9 data: 9                                                                                                                                                                               
top: 10 data: 10         
invalid top 11                                                                                                                                                                              
invalid top 12                                                                                                                                                                              
invalid top 13  

Answer 4

Вам действительно нужно научиться базовой отладке.Например, самое основное - это узнать значения в определенных точках кода.Это можно сделать с помощью отладчика или простого оператора печати. ​​

Я сделал это:

void push(int array[], int data){
    printf("%d\n", top);

    if(top > MAX_SIZE-1)
        fprintf(stderr, "invalid top %d\n", top+1);
    else{
        array[++top] = data; // top == 9, ++top == 10
        printf("top: %d data: %d\n", top+1, array[top]); // top == 11, top == 10
    }
}

И получил такой вывод:

...
top: 9 data: 9
8
top: 10 data: 10
9
top: 11 data: 100
10
invalid top 11
10
invalid top 11

Теперь это должно бытьДовольно очевидно, в чем проблема.

Я думаю, что это должно быть ошибкой.потому что я объявил размер массива как 10, который является MAX_SIZE.поэтому размер индекса будет 0 ~ 9. но как мог работать массив [10] ??

Он не работает.Это «работает».Доступ вне границ вызывает неопределенное поведение.Подробнее читайте здесь: https://stackoverflow.com/a/4105123/6699433