Stack +++
.pdfДинамические структуры данных
на С
Стек Stack
Очередь Queue
Дек Deque
2
Стек
magazine |
Push |
Pop |
|
Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца - вершины стека. Stack = кипа, куча, стопка , стог
LIFO = Last In – First Out
Кто последним вошёл, тот первым вышел
Операции со стеком:
1) добавить элемент на вершину Push = втолкнуть
2) снять элемент с вершины |
Pop = вылететь со звуком |
3
Пример задачи
Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы).
Примеры: [()]{} ][ [({)]}
Упрощенная задача: то же самое, но с одним видом скобок. Решение: счетчик вложенности скобок. Последовательность
правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным.
( ( ) ) ( ) |
|
( ( ) ) |
) ( |
|
( ( ) ) ( |
1 2 1 0 1 0 |
1 2 1 0 -1 0 |
1 2 1 0 1 |
|||
? Можно ли решить исходную задачу так же, но с тремя счетчиками?
|
|
[ ( { ) ] } |
|
|
|
|
|
(: 0 |
1 |
0 |
|
[: |
0 |
1 |
0 |
{: |
0 |
1 |
0 |
4
Решение задачи со скобками
[ |
( |
( |
) |
) |
] |
{ |
} |
|
|
( |
|
|
|
|
|
|
( |
( |
( |
|
|
|
|
[ |
[ |
[ |
[ |
[ |
|
{ |
|
Алгоритм:
1)в начале стек пуст;
2)в цикле просматриваем все символы строки по порядку;
3)если очередной символ – открывающая скобка, заносим ее на вершину стека;
4)если символ – закрывающая скобка, проверяем вершину стека: там должна быть соответствующая открывающая скобка (если это не так, то ошибка);
5)если в конце стек не пуст, выражение неправильное.
Реализация стека в виде массива
Структура-стек: const int STACKSIZE = 100;
struct STACK
{int top; // вершина стека=число элементов
//top указывает на запись
int data[STACKSIZE];
// стек на 100 элементов
};
Добавление элемента: int Push ( STACK &s, int x )
{ if ( s.top == STACKSIZE ) return 0; s.data[s.top] = x;
s.top++;
return 1; |
success |
|
error:
переполнение
стека
добавление
элемента
}
6
Реализация стека в виде массива
Снятие элемента с вершины:
int Pop(STACK &s )
{ if ( s.top == 0 ) return -1; s.top--;
return s.data [s.top];
}
error:
стек пуст
Пустой или нет?
int isEmpty ( STACK &s ) { if ( s.top == 0 ) return 1;
else return 0;
}
Реализация стека динамическим массивом 7
Структура-стек:
struct STACK { int top, size;
//вершина стека=число элементов int *data;
//указатель на стек любого типа
};
В программе:
STACK s; s.size=100;
s.data= (int *) calloc(s.size,4);
// можно переопределять size и realloc s.top=0;
Реализация стека динамическим массивом 8
Добавление элемента: int Push ( STACK &s, int x )
{ if ( s.top == s.size) {s.size = 2* s.size ;
s.data=(int*) realloc(s.data, s.size*sizeof(int));
}
s.data[s.top] = x; s.top++;
return top; // или 1 == success
}
warning:
переопределение
стека
Программа – скобки
int main() |
|
{ char open[3] = { '(', '[', '{' }, |
// открывающие скобки |
close[3] = { ')', ']', '}' }; |
// закрывающие скобки |
char string[80], c, upper; |
// то, что сняли со стека |
int i, k, error = 0; |
// признак ошибки |
STACK stack; |
|
stack.top = 0; |
|
printf(“Input expression with brackets > "); gets ( string );
n=strlen(string); stack.size = n;
// здесь основной цикл обработки – следующий слайд
if ( ! error ) printf("just expression\n"); else printf(“error expression\n");
}
10
Обработка строки
|
for ( i = 0; i < n; i++ ) |
// цикл по всем символам строки |
{ |
c= string[i]; |
|
|
for ( k = 0; k < 3; k++ ) |
// цикл по всем видам скобок |
{ |
if (c== open[k] ) |
// если открывающая скобка |
|
{Push ( stack, c ); break;} |
// втолкнуть в стек из цикла k |
|
if ( c == close[k] ) |
// если закрывающая скобка |
|
{upper = Pop ( stack ); |
// снять верхний элемент |
if ( upper != c ) { error = 1; break; }
}// if close
}// for k
if ( error ) break;
}// for i