Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
Зачастую стек реализуется в виде однонаправленного списка (каждый элемент списка указывает только на следующий). Кроме того, можно организовать его на обыкновенном массиве.
Значением переменной стека является указатель на вершину стека. Если стек пуст, то значение указателя равно NULL.
| C++ для начинающих Динамические структуры данных СТЕК ... |
5 сен 2012 ... AVL дерево ... Для создания стека (или динамического списка LIFO) будем
использовать 4 функции (main, Добавить в список, Показать список, ... List *
Next,*Head; //Голова стека и указатель на следующий элемент.
http://ci-plus-plus-snachala.ru/?p=91 |
struct stack
{
char *data;
struct stack *next;
};
При удалении элемента убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент).
void push( STACK *ps, int x ) // Добавление в стек нового элемента
{
if ( ps->size == STACKSIZE ) // Не переполнен ли стек?
{
fputs( "Error: stack overflow\n", stderr );
abort();
}
else
{
ps->items[ps->size++] = x;
}
}
int pop( STACK *ps ) // Удаление из стека
{
if ( ps->size == 0 ) // Не опустел ли стек?
{
fputs( "Error: stack underflow\n", stderr );
abort();
}
else
{
return ps->items[--ps->size];
}
}
Для отслеживания точек возврата из подпрограмм используется стек вызовов.
При вызове подпрограммы (процедуры) процессор кладёт в стек адрес команды, следующей за командой вызова подпрограммы «адрес возврата» из подпрограммы. По команде возврата из подпрограммы из стека вынимается адрес возврата и осуществляется переход по этому адресу. Аналогичные процессы происходят при прерывании (процессор X86 при прерывании сохраняет в стеке ещё и регистр флагов). Кроме того, компиляторы размещают локальные переменные процедур в стеке (если в процессоре предусмотрен доступ к произвольному месту стека).
До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на область реальной оперативной памяти (стек в ПЗУ, естественно, работать не может). Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищенном режиме сегмент состояния задачи содержит четыре селектора сегментов стека (для разных уровней привилегий), но в каждый момент используется только один стек[8].
| Очереди, стеки, связанные списки и деревья |
Очереди, стеки, связанные списки и деревья ... приемы программирования в
С, включая динамическое выделение памяти и использование указателей.
http://lord-n.narod.ru/download/books/walla/programming/Spr_po_C/22/22.htm |
