Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования «Чувашский государственный университет имени И.Н. Ульянова»

Факультет информатики и вычислительной техники

Кафедра математического и аппаратного обеспечения информационных систем

Расчетно-графическая работа

на тему: «Организация стеков»

Выполнил:

Ст. группы ИВТ-21-20

Иванова Т.А.

Проверил:

Зав. кафедрой МиАОИС

Ильин Д.В.

Чебоксары, 2020

Оглавление

• стек библиотека абстрактный
• Введение
• 1. Основные сведения
• 2. Применение стеков
• 3. Свойства
• 4. Методы реализации стека
• 5. Реализация стека
• 6. Решение задачи со скобочной последовательностью без использования библиотеки stack
• 7. Решение задачи со скобочной последовательностью с применением библиотеки stack
• 8. Задача с сайта acmp.ru
• Заключение
• Список литературы

Введение

Стек (англ. stack - стопка; читается стэк) - абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in - first out, «последним пришёл - первым вышел»).

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

Главный принцип работы стека - данные, которые попали в стек недавно, используются первыми. Чем раньше попал - тем позже используется. После использования элемент стека исчезает, и верхним становится следующий элемент.

В 1946 Алан Тьюринг ввёл понятие стека. А в 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею Тьюринга.

В некоторых языках (например, Lisp, Python) стеком можно назвать любой список, так как для них доступны операции pop и push. В языке C++ стандартная библиотека имеет класс с реализованной структурой и методами и т. д.



1. Основные сведения

Стек является одной из наиболее используемых и наиболее важных структур данных. Он применяются очень часто:

· Распознавание синтаксиса в компиляторе;

· Оценка выражений;

· Передачи параметров функциям;

· Выполнение вызова функции;

· Возврат из функции;

Стек, чаще всего, реализуется на основе обычных массивов, односвязных и двусвязных списков. В зависимости от конкретных условий, выбирается одна из этих структур данных. Он предназначен для хранения элементов, доступных естественным путём в вершине стека, например: стопка подносов или груда тарелок.

В стеке нет индексов как в массиве, а значит вы не можете обратиться к определенному элементу. Всё потому что, стек построен на связных списках.

Это значит, что каждый элемент (кроме последнего - он показывает на NULL, если простыми словами, то на ничего) имеет указатель на следующий элемент. Но есть элемент, на который нет указателя - первый (или как его еще называют головной).

Операции со стеком:

· добавление элемента;

· удаление элемента;

· чтение верхнего элемента;

Kогда стек достигает максимального количества элементов, наступает ситуация полноты стека (stack full) - в случае использования массивов.

Другая крайность - нельзя взять поднос с пустой полки. Условие пустого стека (stack empty) подразумевает, что нельзя удалить\извлечь элемент.

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

Список функций C++ для работы со стеком:

• добавить элемент - push();

• удалить элемент - pop();

• получить верхний элемент - top();

• размер стека - size();

• проверить стек на наличие элементов - empty();

Данные функции входят в стандартную библиотеку шаблонов C++ - STL, а именно в контейнер stack.

Ыtack - контейнер, в котором добавление и удаление элементов осуществляется с одного конца, что свойственно непосредственно стеку. Использование стековых операций не требует их описания в программе, т. е. stack здесь предоставляет набор стандартных функций. Для начала работы со стеком в программе необходимо подключить библиотеку stack:

#include <stack>

в функции описывается:

stack <тип данных> имя стека;

Рассмотрим подробнее функции для работы со стеком.

1. Push()

Функция push() ставит значение на вершину стека. Например:

st.push(1); // - на вершине число 1

st.push(2); // - на вершине число 2

st.push(3); // - на вершине число 3

2. Pop()

Функция pop() удаляет значение с вершины, то есть удаляет последний элемент.

// - изначально стек 138

st.pop(); // осталось 13

st.pop(); // осталось 1

3. Top()

Функция top() получает значение верхнего элемента, не удаляя его.

// изначально стек 138

int a = st.top(); // a =8;

4. Size()

Функция size() возвращает количество элементов в стеке.

// изначально стек 131331

int a = st.size(); // a = 6;

5. Empty()

Булева функция empty() дает понять пуст стек или нет. Возвращает true в случае, если стек пуст.

// Программа выведет верхний элемент если он есть, иначе выведет сообщение о том, что стек пуст.

if (st.empty())

cout << "Stack is empty";

else

cout << st.top();

2. Применение стеков

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

Один из способов реализации такого порядка обработки данных - это организовать своего рода очередь вызовов функций. Последняя добавленная в стек функция, будет завершена первой и наоборот, первая добавленная в стек функция будет завершена последней. Таким образом, сама структура данных обеспечивает надлежащий порядок вызовов.

Вычисление выражений.

Стек используется для оценки префиксных, постфиксных и инфиксных выражений.

Преобразование выражений.

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

Синтаксический разбор.

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

Поиск с возвратом.

Предположим, что мы должны найти путь в лабиринте для решения проблемы. Мы выбираем путь и после этого понимаем, что этот путь неправильный. Теперь нам нужно вернуться к началу пути, чтобы начать новый путь. Это может быть сделано с помощью стека.

Проверка скобок.

Стек используется, чтобы проверить правильность открытия и закрытия скобок.

Реверсирование строки.

Стек используется для смены строки. Мы посылаем символы строки по одному в стек, а затем символы всплывают из стека.

Вызов функции.

Стек используется для сохранения информации об активной функции или подпрограммы.

3. Свойства

Count	Получает число элементов, содержащихся в интерфейсе Stack.
IsSynchronized	Возвращает значение, показывающее, является ли доступ к коллекции Stack синхронизированным (потокобезопасным).
SyncRoot	Получает объект, с помощью которого можно синхронизировать доступ к коллекции Stack.

4. Методы реализации стека

Clear()	Удаляет все объекты из Stack.
Clone()	Создает неполную копию Stack.
Contains(Object)	Определяет, входит ли элемент в коллекцию Stack.
CopyTo(Array, Int32)	Копирует Stack в существующий одномерный массив Array, начиная с указанного индекса массива.
Equals(Object)	Определяет, равен ли заданный объект текущему объекту. (Наследуется от Object.)
GetEnumerator()	Позволяет объекту попытаться освободить ресурсы и выполнить другие операции очистки, перед тем как он будет уничтожен во время сборки мусора.(Наследуется от Object.)
GetHashCode()	Возвращает перечислитель IEnumerator для словаря Stack.
GetType()	Служит хэш-функцией по умолчанию. (Наследуется от Object.)
MemberwiseClone()	Возвращает объект Type для текущего экземпляра. (Наследуется от Object.)
Peek()	Создает неполную копию текущего объекта Object.(Наследуется от Object.)
Pop()	Возвращает объект в верхней части Stack без его удаления.
Push(Object)	Удаляет и возвращает объект, находящийся в начале Stack.
Synchronized(Stack)	Вставляет объект как верхний элемент стека Stack.
ToArray()	Возвращает синхронизированную (потокобезопасную) оболочку для Stack.
ToString()	Копирует Stack в новый массив.

5. Реализация стека

Реализация простых функций стека без использования библиотеки

#include

<iostream>

using namespace std;

int stck[100]; //массив стека

int s=0;

int push (int x) //Функция ставит значение на вершину стека

{

stck [s] = x;

s++;

}

int pop () //Функция удаляет значение с вершины

{

return stck [s--];

}

// проверяет, пуст ли стек

bool isempty() {return s == 0;}

int top(int a) { cout << stck [s-1];}

int main()

{

int p;

push (15);

push (54);

push (87);

pop ();

isempty();

top (p);

return 0;

}

Результат:

Реализация простых функций стека с применением библиотеки

#include <iostream>

#include <stack>

using namespace std;

// Реализация стека на C ++ с использованием std:: stack

int main()

{

stack<string> s;

s.push("A");

s.push("B");

s.push("C");

s.push("D");

// Возвращает количество элементов в стеке

cout << "Размер стека " << s.size() << endl;

// Выводит верхний элемент

cout << "Верхний элемент: " << s.top() << endl;

s.pop(); // удаление верхнего элемента ("D")

s.pop(); // удаление следующего верхнего элемента ("C")

cout << "Размер стека " << s.size() << endl;

// проверяет, пуст ли стек

if (s.empty())

cout << "Стек пуст\n";

else

cout << "Стек не пуст\n";

return 0;

}

Результат:



6. Решение задачи со скобочной последовательностью без использования библиотеки stack

#include <iostream>

#include <cstring>

using namespace std;

int stack[1000];

int l=0;

void push(int x){

l++;

stack[l]=x;

}

int pop() {

l--;

return stack[l];

}

int main()

{

setlocale(LC_ALL,"rus");

int n=0;

string s;

cin>> s;

for (int i=0;i<s.size();i++) {

if (s[i]=='(') {

push(s[i]);

}

if (s[i]==')') {

if (l==0)

n=1;

if (l!=0 && stack[l]=='(')

pop();

}

if (s[i]=='[') {

push(s[i]);

}

if (s[i]==']') {

if (l==0)

n=1;

if (l!=0 && stack[l]=='[')

pop();

}

if (s[i]=='{') {

push(s[i]);

}

if (s[i]=='}') {

if (l==0)

n=1;

if (l!=0 && stack[l]=='{')

pop();

}

if (s[i]=='<') {

push(s[i]);

}

if (s[i]=='>') {

if (l==0)

n=1;

if (l!=0 && stack[l]=='<')

pop();

}

}

if(n==0 && l==0) cout<<"Правильная скобочная последовательность";

if(n==1 || l!=0) cout<<"Неправильная скобочная последовательность";

}

Результаты:

7. Решение задачи со скобочной последовательностью с применением библиотеки stack

#include<iostream>

#include <stack>

#include <cstring>

using namespace std;

int main()

{

setlocale(LC_ALL,"rus");

string s;

cin>> s;

stack<char>stack;

int n=0;

for (int i=0;i<s.size();i++) {

if (s[i]=='(') {

stack.push(s[i]);

}

if (s[i]==')') {

if (stack.empty())

n=1;

if (!stack.empty()&&stack.top()=='(')

stack.pop();

}

if (s[i]=='[') {

stack.push(s[i]);

}

if (s[i]==']') {

if (stack.empty())

n=1;

if (!stack.empty()&&stack.top()=='[')

stack.pop();

}

if (s[i]=='[') {

stack.push(s[i]);

}

if (s[i]==']') {

if (stack.empty())

n=1;

if (!stack.empty()&&stack.top()=='[')

stack.pop();

}

if (s[i]=='[') {

stack.push(s[i]);

}

if (s[i]==']') {

if (stack.empty())

n=1;

if (!stack.empty()&&stack.top()=='[')

stack.pop();

}

}

if(n==0&&stack.empty())

cout<<"Правильная скобочная последовательность";

if(n==1||!stack.empty())

cout<<"Неправильная скобочная последовательность ";

}

Результаты:



8. Задача с сайта acmp.ru

Условие задачи:

У каждого общественного деятеля есть собственный спичрайтер - некто, помогающий в подготовке публичной речи, тот, кто делает ее более выразительной и интересной.

Это относится и к главе Ордена джедаев магистру Йоде, известному нам своими подвигами в «Звездных войнах». На первый взгляд может показаться, что спичрайтеру Йоды приходится тяжелее других: все-таки речь магистра своеобразна и ее изучение требует серьезных усилий. На самом деле все несколько проще. Спичрайтеру Йоды достаточно сначала придумать речь для обычного человека, после чего поменять порядок слов в каждом предложении на обратный. В силу того, что алгоритм преобразования обычной речи в речь магистра Йоды достаточно однообразен, спичрайтер решил автоматизировать этот процесс и попросил Вас написать программу, которая будет преобразовывать речь, составленную им для обычного человека в речь для Йоды.

Решение:

Будем считывать по одному слову и складывать их в стек. Как только в конце очередного слова точка, следует вывести все слова из стека (в обратном порядке, именно поэтому и используется стек). А считывание продолжить дальше.



#include <iostream>

#include <cstdio>

#include <cstring>

#include <stack>

using namespace std;

int main(){

//Считываем данные из файла

freopen("input.txt", "r", stdin);

//Записываем данные в файл

freopen("output.txt", "w", stdout);

string str;

stack<string> st;

bool f=false;

while(cin>>str){

if(str[str.size()-1]=='.'){

str=str.substr(0, str.size()-1);

if(f) cout<<" ";

else f=true;

cout<<str;

while(!st.empty()){

cout<<" "<<st.top();

st.pop();

}

cout<<".";

}else st.push(str);

}

return 0;

}



стек библиотека абстрактный



Заключение

В некотором смысле, стеки являются частью фундаментального языка информатики. Концептуально, структура данных - стек очень проста: она позволяет добавлять или удалять элементы в определенном порядке. Каждый раз, когда добавляется элемент, он попадает на вершину стека, единственный элемент, который может быть удален из стека - элемент, который находится на вершине стека. Таким образом, стек, как принято говорить, «первым пришел, последним ушел - FILO» или «последним пришел, первым ушел - LIFO». Первый элемент, добавленный в стек, будет удален из него в последнюю очередь.

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



Список литературы

1. Свободная энциклопедия Википедия https://ru.wikipedia.org/wiki/Стек

2. КОД |Журнал Яндекс практикума https://thecode.media/stack/

3. Национальный исследовательский университет «Высшая школа экономики». Факультет компьютерных наук. Летняя школа по компьютерным наукам. Август. 2016. Параллель С. Шуйкова И.А. Лекция 1. http://shujkova.ru/sites/default/files/lec1.pdf

4. Сайт Programmado - блог начинающих программистов http://programmado.ru/51-stackc.html

5. Code Lessons https://codelessons.ru/cplusplus/realizaciya-steka-stack-v-c.html

6. БЛОГ Web Программиста http://juice-health.ru/programming/503-primenenie-steka

7. Software Testing Help https://www.softwaretestinghelp.com/stack-in-cpp/

Размещено на Allbest.ru

...