Структура данных «стек»

Стек — это упрощенный вариант связанного списка. Новые узлы могут добавляться в стек и удаляться из стека только сверху. По этой причине, стек часто называют структурой вида последним пришел — первым обслужился (LIFO). На стек ссылаются через указатель на верхний элемент стека. Связывающий элемент в последнем узле стека установлен равным NULL, чтобы пометить границу стека.

Графическое представление стека с несколькими узлами показано на рис. 1.4. Следует отметить, что стеки и связанные списки представляются идентично. Разница между стеком и связанными списками в том, что вставку и удаление в связанных списках можно выполнять в любом месте, а в стеке только сверху.

Рис. 1.4. Графическая иллюстрация стека

Примеры. Программа работает с простым стеком целых чисел. Программа выполняет три действия на выбор: 1) помещает значение в стек (функция push), 2) извлекает значение из стека (функция pop), и 3) завершает работу.

#include "stdafx.h"

#include<stdlib.h>

#include<malloc.h>

#include<stdio.h>

struct stackNode

{

int data;

struct stackNode *nextPrt;

};

typedef struct stackNode STACKNODE;

typedef STACKNODE * STACKNODEPTR;

void push(STACKNODEPTR *, int);

int pop(STACKNODEPTR *);

int isEmpty(STACKNODEPTR);

void printStack(STACKNODEPTR);

void instruc(void);

void main()

{

STACKNODEPTR stackPtr = NULL;

int choice, value;

instruc();

printf("? ");

scanf("%d", &choice);

while (choice!=3)

{

switch (choice)

{

case 1:

printf("Enter an integer >> ");

scanf("%d", &value);

push (&stackPtr, value);

printStack(stackPtr);

break;

case 2:

if (!isEmpty(stackPtr))

printf("the popped value is %d \n", pop(&stackPtr));

printStack(stackPtr);

break;

default:

printf("Error enter\n");

instruc();

break;

}

printf("? ");

scanf("%d", &choice);

}

printf("End \n");

}

void instruc(void)

{

printf("1 - dobavit\n");

printf("2 - delete\n");

printf("3 - exit\n");

}

void push(STACKNODEPTR *topPtr, int info)

{

STACKNODEPTR newPtr;

newPtr = new STACKNODE;

if (newPtr!= NULL)

{

newPtr ->data = info;

newPtr ->nextPrt = * topPtr;

*topPtr = newPtr;

}

else

printf("%d Error not memori\n", info);

}

int pop(STACKNODEPTR *topPtr)

{

STACKNODEPTR tempPtr;

int popValue;

tempPtr = *topPtr;

popValue = (*topPtr) ->data;

*topPtr = (*topPtr) ->nextPrt;

free(tempPtr);

return popValue;

}

void printStack(STACKNODEPTR currentPtr)

{

if (currentPtr == NULL)

printf("Error not stack\n\n");

else

{

printf("Stack is:>> \n");

while (currentPtr!= NULL)

{

printf("%d -> ", currentPtr ->data);

currentPtr = currentPtr ->nextPrt;

}

printf("\n");

}

}

int isEmpty (STACKNODEPTR topPtr)

{

return topPtr == NULL;

}

В данном примере основные функции, используемые при работе со стеками — push и pop. Функция push создает новый узел и помещает его на вершину стека. Функция pop удаляет верхний узел стека, освобождает память, которая была выделена изъятому узлу, и возвращает изъятое значение.

Программа работает с простым стеком целых чисел. Программа выполняет три действия на выбор: 1) помещает значение в стек (функция push), 2) изымает значение из стека (функция pop), и 3) завершает работу.

Функция push помещает новый узел на вершину стека. В выполнении функции можно выделить три этапа:

1. Создание нового узла посредством вызова malloc, при этом указателю newPtr присваивается адрес блока выделенной памяти; переменной newPtr -> data присваивается значение, которое необходимо поместить в стек; и указателю newPtr->nextPtr присваивается NULL.

2. Указателю newPtr->nextPtr присваивается *topPtr (указатель на вершину стека); связывающий элемент newPtr теперь указывает на узел, который был верхним до этого.

3. *topPtr присваивается значение newPtr; *topPtr теперь указывает на новую вершину стека. Операции, включающие в себя *topPtr, меняют значение stackPtr в main.

а)
б)

Рис. 1.5. Графическая иллюстрация выполнения функции push

Наглядное представление о том, как происходит выполнение функции push показано на рис. 1.5. На рис. 1.5, а изображен стек и новый узел перед выполнением функции push. Пунктирные линии на рис. 1.5, б иллюстрируют шаги 2 и 3 выполнения функции push, в результате которых узел, содержащий 12, становится новой вершиной стека.

Функция pop удаляет верхний узел стека. Отметим, что перед тем как вызвать функцию pop, функция main определяет, не пуст ли стек. В выполнении функции pop можно выделить пять основных этапов:

1. Указателю tempPtr присваивается *topPtr (tempPtr будет использован для освобождения ненужной памяти).

2. Переменной popValue присваивается значение (*topPtr)->data (сохраняется значение, находившееся в верхнем узле).

3. *topPtr присваивается (*topPtr)->nextPtr (*topPtr присваивается адрес нового верхнего узла).

4. Освобождается память, на которую указывает tempPtr.

5. Вызывающей функции возвращается значение popValue (в примере программы это функция — main).

Выполнение функции pop проиллюстрировано на рис. 1.6. На рис. 1.6, а показано состояния стека после предыдущей операции push. На рис. 1.6, б выделены указатели tempPtr, указывающий на первый узел стека, и *topPtr, указывающий на второй узел. Для освобождения указанной tempPtr памяти вызывается функция free.

а)
б)

Рис. 1.6. Графическая иллюстрация выполнения функции pop

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

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

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