Помогите со стеком на Си

Question

Помогите со стеком на Си

AMA_Lucifer Ученик (7), закрыт 1 неделю назад

 #include  
#include  
 
 
typedef struct obj{ 
    int data; 
    struct obj* next; 
} OBJ ; 
 
OBJ* push(OBJ* top, int data) 
{ 
    OBJ* ptr = malloc(sizeof(OBJ)); 
    ptr->data = data; 
    ptr->next = top; 
    return ptr; 
 
} 
 
 
int main(void) 
{ 
    OBJ* top = NULL; 
    top = push(top, 1); 
 
 
    return 0; 
}

Привет! По видео инструкции пытался разобраться что такое стек в Си. Написал этот код, но не совсем понимаю как он работает. Понимаю что создаем структуру, в которой какие-то данные и указатель на следующий элемент в стеке. Потом в main особо не понимаю, но вроде создается указатель top, который указывает на самый первый элемент т.е самый нижний элемент. А вот функцию push вообще не понял. Можете пожалуйста объяснить как работает стек. Может нужны разные ответы что-бы понять.

Answer 1

Да, конечно, я объясню работу вашего кода и принцип работы стека.

1. **Структура `OBJ`:**
- В вашем коде определена структура `OBJ`, которая представляет элемент стека.
- У этой структуры есть два поля:
- `data`: для хранения данных (в вашем случае, это целочисленное значение `int`).
- `next`: указатель на следующий элемент стека (так как стек является структурой данных LIFO - "последним вошел, первым вышел").

2. **Функция `push`:**
- Эта функция добавляет новый элемент на вершину стека.
- Принимает два параметра:
- `top`: указатель на вершину стека.
- `data`: данные, которые нужно поместить в новый элемент стека.
- Создается новый элемент стека с помощью функции `malloc`, который выделяет память под структуру `OBJ`.
- Поле `data` нового элемента заполняется переданным значением.
- Поле `next` нового элемента устанавливается так, чтобы указывать на текущую вершину стека (элемент, на который указывает `top`).
- Указатель `top` обновляется, чтобы указывать на новый элемент стека, который стал вершиной.

3. **Функция `main`:**
- В этой функции создается указатель `top`, который изначально указывает на `NULL`, что означает, что стек пуст.
- После этого вызывается функция `push` для добавления нового элемента со значением `1` на вершину стека.
- После выполнения функции `push` элемент со значением `1` становится вершиной стека.

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

Answer 2

Конечно, давай разберемся!

Стек работает по принципу "последний пришел, первый ушел" (LIFO - Last In, First Out). Представь стопку тарелок: последнюю положенную тарелку берут первой.

В твоем коде `OBJ` это структура для элемента стека, в которой есть данные (`data`) и указатель на следующий элемент стека (`next`). Это как каждая тарелка, помимо своей формы, знает, что лежит под ней.

Когда ты делаешь `top = push(top, 1);`, ты кладешь элемент с данными `1` в стек. `push` создает новый элемент стека (`OBJ`), присваивает ему значение `data` и делает его вершиной стека, причем его `next` указывает на предыдущую вершину стека (или на `NULL`, если стек был пуст). Так стек растет вверх, при каждом `push`.

`top` - это вершина стека, указатель на самый последний добавленный элемент. Когда ты добавляешь элементы, `top` меняется, указывая на новую вершину.

Так что твой код создает стек, в который можно добавлять элементы. Чтобы стек был полноценным, нужны функции не только для добавления, но и для удаления элементов из стека (обычно `pop`), проверки пуст ли стек и просмотра верхнего элемента без его удаления.

Надеюсь, стало понятнее!

Answer 3

Генномодифицированный гриб Мастер (1513) 1 месяц назад

.

AMA_LuciferУченик (7) 1 месяц назад

А можете пожалуйста объяснить почему зачем в функции push первый аргумент это top?

Answer 4

Смотри, у тебя в коде вначале создаётся нулевой указатель, который ни на что не указывает.
Потом у тебя при помощи функции push добавляется элемент в стек.
То есть создаётся новая структура с твоими данными и указателем на прошлый верхний элемент. Эта функция тебе вернет указатель на этот элемент.

Указатель Top у тебя всегда будет указывать на элемент, который ты добавил последним.

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

Answer 5

 #include  
#include  
#include  
 
#define DEFAULT_SIZE 8 
#define INCREMENT 8 
 
#define STACK_OVERFLOW -100 
#define BAD_ALLOC -101 
 
typedef int T; 
typedef struct stack { 
    T* data; 
    size_t capacity; 
    size_t count; 
} Stack; 
 
static Stack* create() { 
    Stack* head = NULL; 
    head = malloc(sizeof(Stack)); 
    if (head == NULL) { 
        exit(BAD_ALLOC); 
    } 
    head->capacity = DEFAULT_SIZE; 
    head->data = malloc(head->capacity * sizeof(T)); 
    if (head->data == NULL) { 
        free(head); 
        exit(BAD_ALLOC); 
    } 
    head->count = 0; 
    return head; 
} 
 
static void claer(Stack** stack) { 
    free((*stack)->data); 
    free(*stack); 
    *stack = NULL; 
} 
 
static void resize(Stack* stack) { 
    stack->capacity += INCREMENT; 
    stack->data = realloc(stack->data, stack->capacity * sizeof(T)); 
    if (stack->data == NULL) { 
        exit(STACK_OVERFLOW); 
    } 
} 
 
static void push(Stack* stack, T value) { 
    if (stack->count >= stack->capacity) { 
        resize(stack); 
    } 
    stack->data[stack->count] = value; 
    stack->count++; 
} 
 
static _Bool empty(Stack* stack) { 
    return stack->count == 0; 
}

static void pop(Stack* stack) { 
    stack->count--; 
} 
 
static T top(const Stack* stack) { 
    return stack->data[stack->count - 1]; 
} 
 
static void shrink_to_fit(Stack* stack) { 
    stack->capacity = stack->count; 
    stack->data = realloc(stack->data, stack->capacity * sizeof(T)); 
} 
 
static size_t size(Stack* stack) { 
    return stack->count; 
} 
 
static size_t capacity(Stack* stack) { 
    return stack->capacity; 
} 
 
int main(void) { 
    int box[] = { 25, 47, 13, 84, 66, 89, 18, 33, 58, 62, 85 }; 
    size_t length = sizeof(box) / sizeof(box[0]); 
    size_t i = 0; 
    Stack* stack = create(); 
    while (i != length) { 
        push(stack, box[i]); 
        printf("data: %d, count: %zu, capacity: %zu\n", 
            top(stack), 
            size(stack), 
            capacity(stack) 
        ); 
        ++i; 
    } 
    puts("----------------------------------"); 
    while (!empty(stack)) { 
        printf("data: %d, count: %zu, capacity: %zu\n", 
            top(stack), 
            size(stack), 
            capacity(stack) 
        ); 
        pop(stack); 
        if (size(stack) == 4) { 
            shrink_to_fit(stack); 
        } 
    } 
    claer(&stack);  
    return 0; 
}

Пользуйтесь!