Стеком называется одномерная структура данных, включение и исключение элементов которого осуществляется с помощью указателя стека в соответствии с правилом "последним введен, первым выведен".
| Задание
| Краткие теоретические сведения
|
| 1. Изучить реализацию стека на основе динамического массива, выполнив программу, приведенную в правой части.
| Стек организован на основе динамического массива, для которого динамически выделяется фрагмент памяти.
В данной программе чтобы сложить, например, 3 и 2, необходимо ввести 3, затем 2, а потом нажать клавишу "плюс". При вводе точки программа выводит текущее значение на вершине стека. Функция atoi () используется для конвертации строки в числовой вид.
| #include <iostream>
#define MAX 100
int *p;/* указатель на область свободной памяти */
int *tos, *bos;/* указатель на вершину и дно стека */
void push(int i);
int pop(void);
int main(void)
{ setlocale (LC_CTYPE, "Russian");
int a, b; char s[80];
p = new int [MAX*sizeof(int)];
if(!p)
{ printf("Ошибка при выделении памяти\n");
exit(1);
}
tos = p; bos = p + MAX-1;
printf("Калькулятор \n");
printf("Нажмите 'q' для выхода\n");
do
{ printf(": ");
gets(s);
switch(*s)
{ case '+': a = pop(); b = pop();
printf("%d\n", a+b);
push(a+b);
break;
case '-': a = pop(); b = pop();
printf("%d\n", b-a);
push(b-a);
break;
case '*': a = pop(); b = pop();
printf("%d\n", b*a);
push(b*a);
break;
| case '/': a = pop(); b = pop();
if(a==0)
{ printf("Деление на 0.\n");
break; }
printf("%d\n", b/a); push(b/a);
break;
case '.':/* показать содержимое вершины стека */
a = pop(); push(a);
printf("Текущее значение на вершине стека: %d\n", a);
break;
default: push(atoi(s));
}
}
while(*s!= 'q');
return 0;
}
void push(int i) // Занесение элемента в стек
{ if(p > bos)
{ printf("Стек полон\n");
return; }
*p = i; p++;
}
int pop(void) // Получение верхнего элем. из стека
{ p--; if(p < tos)
{ printf("Стек пуст\n");
return 0; }
return *p;
}
|
|
| 2. В программе, приведенной справа, демонстрируется использование стека на основе списка.
| В примере ниже стек реализован на основе списка.
| #include <iostream>
using namespace std;
struct stek
{ int d;
struct stek *next;
};
// добавление элемента
void push(stek* &next, int d)
{
stek *pv = new stek;
pv->d = d; // значение помещается в стек
pv->next = next;
next = pv;
}
// извлечение элемента
int pop(stek* &next)
{
// извлекается в tmp значение в вершине стека
int tmp = next->d;
| // запоминается указатель на вершину стека
stek *pv = next;
// вершиной становится предшеств. элемент
next = next->next;
delete pv;// освобождается память,
cout<<tmp<<endl;//вывод тек. элемента return tmp
}
int main()
{ stek *p=0;
push(p, 100);//число 100 – в стек
push(p, 200);//число 200 – в стек
pop(p);//вывод текущего элемента = 200
pop(p);// вывод текущего элемента = 100return 0;
}
|
|
| 3. Изучить реализацию стека на основе списка, выполнив программу, приведенную в правой части.
Добавить функцию удаления элемента и продемонстрировать ее использование.
| В примере стек организован на основе списка. В стек заносятся числа от 0 до 9 с помощью цикла.
| #include <iostream>
using namespace std;
struct Stk
{ int x;
Stk *Next, *Head;
};
void Push(int x, Stk **MyStk)//Добавление элемента
{ Stk *temp = new Stk;
temp->x = x;
temp->Next = (*MyStk)->Head;
(*MyStk)->Head = temp;
}
void Show(Stk *MyStk)//Вывод стека
{ Stk *temp = MyStk->Head;
while (temp!= NULL)
{ cout<<temp->x<<" ";
temp = temp->Next; }
cout<<endl;
}
| void ClearStk(Stk *MyStk)//Удаление стека { while (MyStk->Head!= NULL)
{ Stk *temp = MyStk->Head->Next;
delete MyStk->Head;
MyStk->Head = temp;
}
}
void main()
{ Stk *MyStk = new Stk;
MyStk->Head = NULL;
for (int i = 0; i < 10; i++)
Push(i,&MyStk);
Show(MyStk);
void ClearStk(Stk *MyStk);
}
|
|
| 4. В правой части приведены некоторые функции, которые можно использовать для организации стека на основе списка.
Проанализировать текст с тем, чтобы использовать эти функции в задании 5.
| | struct STACK
{ void* Data;//данные элемента стека
STACK *next; //указатель на след.
}
void Push(STACK **ppStack, void* nItem)
{ STACK *pNewItem;
pNewItem = new STACK;//память для стека
pNewItem->Data = nItem;//заполн. поляpNewItem->next = *ppStack;
//устан.новый указатель на вершину стека
*ppStack = pNewItem;
}
void* Pop(STACK **ppStack, int *nError)
{ STACK *pOldData = *ppStack;
void* nOldData = NULL;//запом.старый адрес вершины
if(*ppStack)
{ nOldData = pOldData->Data;//если стек не пустой - извлечь
*ppStack – (*ppStack)->next;
delete pOldData; }
else *nError = 1;
return nOldData;
}
| void* Peek(STACK **ppStack, int *nError)
{ if(*ppStack)
{ nError = 0;
return (*ppStack->Data; }
else { *nError = 1;
return NULL; }
}
void Clear(STACK **ppStack)
{ STACK *pDelItem = *ppStack;
while (*ppStack)!= NULL
*pDelItem = *ppStack;
*ppStack = (*ppStack)->next;//перейти к след.
delete *pDelItem;
}
}
|
|
5. Создать проект, демонстрирующий работу со стеком, организованным на основе списка. В соответствии со своим вариантом выполнить задание из таблицы, представленной ниже. Для организации стека использовать структуру с функциями и реализовать все операции со стеком через функции (некоторые функции можно взять из п. 4). Объявления записать в заголовочном файле проекта, определение функций и реализацию алгоритма выполнить в отдельных модулях.
| № варианта
| Задание для выполнения
|
| 1, 4
| Разработать функцию, которая по одному стеку строит два новых: Stack1 из положительных элементов и Stack2 из отрицательных.
|
| 2, 5
| Разработать функцию, которая удаляет из стека первый отрицательный элемент, если такой есть.
|
| 3, 6
| Разработать функцию, которая формирует стек Stack, включив в него по одному разу элементы, которые входят в один из стеков Stack1 и Stack2, но не входят в другой.
|
| 7, 10
| Разработать функцию, которая определяет, есть ли в стеке хотя бы один элемент, который равен следующему за ним элементу.
|
| 8, 11
| Разработать функцию, которая формирует стек Stack, включив в него по одному разу элементы, которые входят в стек Stack1, но не входят в стек Stack2.
|
| 9, 12
| Разработать функцию, которая подсчитывает количество элементов стека, у которых равные "соседи".
|
| 13, 15
| Разработать функцию, которая удаляет из стека первый элемент, значение которого превышает число 100, если такой элемент есть.
|
| 14, 16
| Разработать функцию, которая по одному стеку строит два новых: Stack1 из элементов, значение которых превышает число 50, и Stack2 - из остальных элементов.
|
В начало практикума
