Программные реализации структур данных. Стек. Реализация в виде массива.

Используется фиксированная область памяти (массив) и индекс вершины стека.

Например, для стека типа целый определяется массив целых чисел определенного размера и индекс головы стека. Индекс тоже удобно выбрать целым. Стек при этом описывается следующей структурой:

typedef struct

{

int anStack[STACK_SIZE];

int nStackIdx;

} CONT_STACK_STRUCT;

Здесь переменная nStackIdx содержит индекс первого свободного элемента массива. Она же равна числу элементов в стеке. Тогда операции положить в стек и взять из стека можно определить следующим образом:

#define SUCCESS 1

#define ERROR 0

int PushCont(CONT_STACK_STRUCT *pStack, int nItem)

{

if (pStack->nStackIdx < STACK_SIZE)

{

pStack->anStack[pStack->nStackIdx++] = nItem;

return SUCCESS;

}

return ERROR;

}

int PopCont(CONT_STACK_STRUCT *pStack, int *pItem)

{

if (pStack->nStackIdx != 0)

{

pStack->nStackIdx--;

if (pItem != NULL)

*pItem = pStack->anStack[pStack->nStackIdx];

return SUCCESS;

}

return ERROR;

}

Полезными будут также операция освобождения стека от всех элементов и операция, возвращающая число элементов в стеке:

void EmptyContStack(CONT_STACK_STRUCT *pStack)

{

pStack->nStackIdx = 0;

}

int GetCountCont(CONT_STACK_STRUCT *pStack)

{

return pStack->nStackIdx;

}

Недостатки сплошного представления очевидны:

• имеется возможность несанкционированного доступа к элементам внутри стека как к обычным элементам массива;

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

Стек. Связанное представление.

Стек можно хранить, как последовательность элементов, каждый из которых содержит указатель на последующий элемент. Элемент стека описывается при этом следующей структурой:

typedef struct _LINK_STACK_ITEM

{

int nItem;

struct _LINK_STACK_ITEM *pNext;

} LINK_STACK_ITEM;

а сам стек представляет собой себя указатель на свой первый элемент:

typedef struct

{

LINK_STACK_ITEM *pHead;

} LINK_STACK_STRUCT;

Операции со стеком, аналогичные тем, что были приведены в предыдущем примере, реализуются для такого стека следующим образом:

void EmptyLinkStack(LINK_STACK_STRUCT *pStack)

{

LINK_STACK_ITEM *pItem = pStack->pHead;

LINK_STACK_ITEM *pNextItem;

while (pItem != NULL)

{

pNextItem = pItem->pNext;

free(pItem);

pItem = pNextItem;

}

pStack->pHead = NULL;

}

int PushLink(LINK_STACK_STRUCT *pStack, int nItem)

{

LINK_STACK_ITEM *pItem = pStack->pHead;

LINK_STACK_ITEM *pNewItem = malloc(sizeof(LINK_STACK_ITEM));

if (pNewItem == NULL)

return ERROR;

pNewItem->nItem = nItem;

pNewItem->pNext = NULL;

if (pItem == NULL)

{

pStack->pHead = pNewItem;

} else

{

while (pItem->pNext != NULL)

pItem = pItem->pNext;

pItem->pNext = pNewItem;

}

return SUCCESS;

}

int PopLink(LINK_STACK_STRUCT *pStack, int *pPopItem)

{

LINK_STACK_ITEM *pItem = pStack->pHead;

LINK_STACK_ITEM *pPrevItem = NULL;

if (pItem == NULL)

return ERROR;

else

{

while (pItem->pNext != NULL)

{

pPrevItem = pItem;

pItem = pItem->pNext;

}

if (pPopItem != NULL)

*pPopItem = pItem->nItem;

free(pItem);

if (pPrevItem == NULL)

pStack->pHead = NULL;

else

pPrevItem->pNext = NULL;

}

return SUCCESS;

}

int GetCountLink(LINK_STACK_STRUCT *pStack)

{

LINK_STACK_ITEM *pItem = pStack->pHead;

int nCount = 0;

while (pItem != NULL)

{

pItem = pItem->pNext;

nCount++;

}

return nCount;

}