Как создается и обрабатывается стек?

Question

Поскольку все, что есть в C ++ и более поздних версиях, имеет хорошие конструкции, которые обрабатывают поведение, подобное «стеку» (векторы, списки, списки массивов и т. Д.), Я хочу оставить вопрос в терминах C.

Итак, я изучаю компиляторы, стеки, inscript и postscript, парсеры, лексеры и все остальное, что включает в себя сборку компилятора, как мне потребуется позже в моем курсе для этого семестра. Я хочу убедиться, что мое понимание стеков является твердым.

Я полагаю, что у меня есть общее представление о том, как собрать человека. В основном у вас есть массив, следующий за моделью LIFO. Когда вы добавляете элемент, он «вставляется» в конец массива и «удаляется» при удалении. Нет проблем там. Моя забота связана с некоторыми деталями реализации. Как отслеживаются такие элементы, как количество элементов? Насколько большим должен быть инициализирован стек? Должен ли я использовать структуру, чтобы объединить эти детали? Являются ли переменные глобальными?

Мой профессор уже передал нам некоторый исходный код в связи с нашим заданием, Я просто ищу некоторые дополнительные детали для моего собственного понимания (как правило, я сам должен что-то собрать, прежде чем понять чужой код). В большей части моего опыта программирования стек был неким волшебным местом, которое было вне моего контроля, но взорвалось бы, если бы мои рекурсивные функции стали слишком глубокими (ТАК кто-нибудь?).

Заранее спасибо.

EDIT:

Хорошо, одну вещь, которую я должен уточнить, это то, что я не делаю "истинный" стек, но мне потребуется взять инфиксное выражение и преобразовать его в постфиксный. Я смотрю на структуру данных стека , поэтому все, что связано с архитектурой, может не применяться в этой области. У меня сложилось впечатление, что стек - это способ справиться с этим, аналогично сокращению правил, описанному в нотации BNF.

Answer 1

О каком стеке вы здесь говорите?

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

Такие «архитектурные» стеки не требуют много, обычно в ЦП есть регистр, который указывает на вершину стека. Задача операционной системы состоит в том, чтобы каждый раз при запуске процесса он имел действительный указатель стека. Это делается путем выделения памяти и инициализации регистра по соответствующему адресу. Современные «большие» ОС: виртуальная память и т. Д. Часто поддерживают динамическое наращивание стека по требованию.

Количество элементов в стеке не отслеживается явно в таких случаях, вы можете вычислить число байтов , используемое путем проверки текущего указателя стека и сравнения со стеком процесса (предположительно известным) начало ", но это не говорит вам о внутренней структуре этих байтов. Это нормально для таких конструкций низкого уровня.

---

Если, как подсказывает nos в комментарии, вы на самом деле говорите о структуре данных стека, то в Си нет стандартной реализации для такой вещи. Можно представить множество возможных API: s, например:

typedef struct _Stack Stack;

Stack * stack_new(size_t element_size, size_t initial_depth, int allow_growth);
int     stack_push(Stack *stack, const void *element);
int     stack_pop(Stack *stack, void *element);
void    stack_peek(const Stack *stack, void *element);
size_t  stack_depth(const Stack *stack);
void    stack_clear(Stack *stack);

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

Answer 2

Похоже, вы ищете информацию о стеке вызовов.В этом случае этот пост может вам очень помочь.

http://altdevblogaday.com/2011/12/24/c-c-low-level-curriculum-part-4-more-stack/

Этот и предыдущий (ссылка в сообщении) рассказывают о том, как работает стек в сборке.уровень.Это необходимо, поскольку даже C скрывает это от вас при создании функций.

Это, вероятно, наиболее актуально с точки зрения компиляторов, но, вероятно, является наиболее важной реализацией стека.

Answer 3

Насколько большим должен быть инициализирован стек?

Я думаю, что он относится к вашему варианту использования индивидуально.

Как отслеживаются такие элементы, как количество отслеживаемых элементов?

Вы можете хранить информацию в дополнительной переменной или подсчитывать элементы каждый раз.