stack data structure c with illustration
най-добрият драйвер за Windows 10
Всичко, което трябва да знаете за стека в C ++.
Стекът е основна структура от данни, която се използва за съхраняване на елементи по линеен начин.
Следва стека LIFO (последно влизане, първо излизане) ред или подход, при който се извършват операциите. Това означава, че елементът, който е добавен последен към стека, ще бъде първият елемент, който ще бъде премахнат от стека.
=> Посетете тук, за да видите цялата серия C ++ за обучение за всички.
Какво ще научите:
Стек в C ++
Стек е подобен на стека от реалния живот или купчина неща, които подреждаме едно над друго.
Дадено по-долу е изобразително представяне на Stack.
Както е показано по-горе, има купчина плочи, подредени една върху друга. Ако искаме да добавим друг елемент към него, тогава го добавяме в горната част на стека, както е показано на горната фигура (лявата страна). Тази операция на добавяне на елемент към стека се нарича „ Натиснете ”.
От дясната страна показахме противоположна операция, т.е. премахваме елемент от стека. Това също се прави от същия край, т.е. горната част на стека. Тази операция се нарича „ Поп ”.
Както е показано на горната фигура, виждаме, че натискането и изскачането се извършват от един и същ край. Това прави стека да следва LIFO реда. Позицията или краят, от който елементите се избутват или изскачат към / от стека, се нарича „ Върхът на стека ”.
Първоначално, когато в стека няма елементи, горната част на стека е настроена на -1. Когато добавяме елемент към стека, горната част на стека се увеличава с 1, което показва, че елементът е добавен. За разлика от това, горната част на стека се намалява с 1, когато елемент изскочи от стека.
След това ще видим някои от основните операции на структурата от данни на стека, които ще са ни необходими, докато внедряваме стека.
Основни операции
Следват основните операции, които се поддържат от стека.
- тласък - Добавя или избутва елемент в стека.
- поп - Премахва или изскача елемент от стека.
- надниквам - Получава горния елемент на стека, но не го премахва.
- е пълен - Тества дали стекът е пълен.
- празно е - Тества дали стекът е празен.
Илюстрация
Горната илюстрация показва последователността на операциите, които се извършват върху стека. Първоначално стекът е празен. За празен стек горната част на стека е зададена на -1.
След това натискаме елемента 10 в стека. Виждаме, че горната част на стека сега сочи към елемент 10.
След това изпълняваме друга операция с натискане с елемент 20, в резултат на което горната част на стека сега сочи към 20. Това състояние е третата фигура.
Сега на последната фигура изпълняваме операция pop (). В резултат на операцията за изскачане елементът, посочен в горната част на стека, се отстранява от стека. Следователно на фигурата виждаме, че елемент 20 е отстранен от стека. Така горната част на стека сега сочи към 10.
По този начин можем лесно да различим подхода LIFO, използван от стека.
Изпълнение
# 1) Използване на масиви
Следва изпълнението на C ++ на стека с помощта на масиви:
#include using namespace std; #define MAX 1000 //max size for stack class Stack { int top; public: int myStack[MAX]; //stack array Stack() { top = -1; } bool push(int x); int pop(); bool isEmpty(); }; //pushes element on to the stack bool Stack::push(int item) { if (top >= (MAX-1)) { cout << 'Stack Overflow!!!'; return false; } else { myStack[++top] = item; cout< Изход:
Натискането на стека
две
4
6
Попът на стека:
6
4
две
В изхода можем да видим, че елементите се изтласкват в стека в един ред и се изскачат от стека в обратен ред. Това показва подхода LIFO (Last in, First out) за стека.
За горната реализация на масива на стека можем да заключим, че това е много лесно за изпълнение, тъй като няма включени указатели. Но в същото време размерът на стека е статичен и стекът не може да нараства или да се свива динамично.
След това ще приложим стека, използвайки масиви в езика за програмиране Java.
class Stack { static final int MAX = 1000; // Maximum Stack size int top; int myStack[] = new int[MAX]; boolean isEmpty() { return (top = (MAX-1)) { System.out.println('Stack Overflow'); return false; } else { myStack[++top] = item; System.out.println(item); return true; } } int pop() { if (top <0) { System.out.println('Stack Underflow'); return 0; } else { int item = myStack[top--]; return item; } } } //Main class code class Main { public static void main(String args[]) { Stack stack = new Stack(); System.out.println('Stack Push:'); stack.push(1); stack.push(3); stack.push(5); System.out.println('Stack Pop:'); while(!stack.isEmpty()) { System.out.println(stack.pop()); } } } Изход:
Натискане на стека:
1
3
5
Стек поп:
5
3
1
Логиката за внедряване е същата като при изпълнението на C ++. Резултатът показва техниката LIFO за избутване и изскачане на елементите към / от стека.
Както вече беше посочено, изпълнението на стека с помощта на масиви е най-простото изпълнение, но е от статичен характер, тъй като не можем динамично да разрастваме или свиваме стека.
# 2) Използване на свързан списък
След това изпълняваме операции на стека, използвайки свързан списък както в C ++, така и в Java. Първо, ще демонстрираме изпълнението на C ++.
#include using namespace std; // class to represent a stack node class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(StackNode *root) { return !root; } void push(StackNode** root, int new_data){ StackNode* stackNode = newNode(new_data); stackNode->next = *root; *root = stackNode; cout<data; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return -1; return root->data; } int main() { StackNode* root = NULL; cout<<'Stack Push:'< Изход:
Натискане на стека:
100
200
300
Най-горният елемент е 300
Стек поп:
300
200
100
Най-горният елемент е -1
След това представяме изпълнението на Java на стека, използвайки свързан списък.
class LinkedListStack { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int new_data) { StackNode newNode = new StackNode(new_data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(new_data); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } } class Main{ public static void main(String[] args) { LinkedListStack stack = new LinkedListStack(); System.out.println('Stack Push:'); stack.push(100); stack.push(200); stack.push(300); System.out.println('Top element is ' + stack.peek()); System.out.println('Stack Pop:'); while(!stack.isEmpty()){ System.out.println(stack.pop()); } System.out.println('Top element is ' + stack.peek()); } } Изход:
Натискане на стека:
100
200
300
как да отворите .eps файл в Windows 10
Най-горният елемент е 300
Стек поп:
300
200
100
Стекът е празен
Най-горният елемент е -2147483648
Току-що видяхме внедряванията на C ++ и Java за стек, използващи свързани списъци. Представяме всеки запис в стека като възел на свързания списък. Най-важното предимство на това изпълнение е, че то е динамично. Това означава, че можем да увеличим или да намалим размера на стека според нашето изискване.
Това е за разлика от случая на изпълнение на стека, използващ масиви, в които трябва да декларираме размера предварително и не можем да го променяме динамично.
Недостатъкът на това изпълнение е, че тъй като ние използваме указатели навсякъде, това заема малко твърде много място в сравнение с изпълнението на масив.
Приложения на Stack
Нека обсъдим някои от приложенията на структурата на стека данни. Структурата на стека данни се използва в редица приложения при софтуерното програмиране, главно поради своята простота и лекота на изпълнение.
Ще опишем накратко някои от приложенията на стека по-долу:
# 1) Infix към Postfix изрази
Всеки общ аритметичен израз е от формата операнд1 ОП операнд 2 .
Въз основа на позицията на оператора OP имаме следните типове изрази:
- Infix - Общата форма на инфиксния израз е „ операнд1 ОП операнд 2 ”. Това е основната форма на израза и ние постоянно използваме в математиката.
- Префикс - Когато операторът е поставен преди операндите, това е префикс израз. Общата форма на инфиксния израз е „ OP операнд1 операнд2 ”.
- Postfix - В изразите за постфикс първо се пишат операнди, последвани от оператора. Той има формата “operand1 operand2 OP”.
Помислете за израза „a + b * c ' . Компилаторът сканира израза отляво надясно или отдясно наляво. Като се грижи за приоритета и асоциативността на оператора, първо ще сканира израза, за да оцени израза b * c. След това отново ще трябва да сканира израза, за да добави резултата от b * c към a.
Тъй като изразите стават все по-сложни, този подход на повторно и отново сканиране на израза става неефективен.
За да се преодолее тази неефективност, ние преобразуваме израза в постфикс или префикс, така че те лесно да могат да бъдат оценени с помощта на структура от данни на стека.
# 2) Разбор / оценка на израза
Използвайки стека, можем да извършим и оценка на действителния израз. При това изразът се сканира отляво надясно и операндите се преместват в стека.
Когато се срещне оператор, операндите се изскачат и операцията се изпълнява. Резултатът от операцията отново се избутва в стека. По този начин изразът се оценява чрез използване на стека и крайният резултат от израза обикновено е текущият връх на стека.
# 3) Обхождане на дървета
Структурата на дървесните данни може да бъде обходена, за да посети всеки възел по много начини и в зависимост от това кога е посетен коренният възел, който имаме.
- обръщане inOrder
- Предварително обръщане
- обръщане след поръчка
За да прекосим ефективно дървото, използваме структурата на данните за стека, за да избутаме междинни възли в стека, така че да поддържаме реда на обхождане.
# 4) Алгоритми за сортиране
Алгоритмите за сортиране като бърза сортировка могат да бъдат направени по-ефективни, като се използват структурите от данни на стека.
# 5) Кулите на Ханой
Това е класически проблем, включващ n броя дискове и три кули, а проблемът включва преместване на дисковете от една кула в друга, като третата кула се използва като междинна.
Този проблем може да бъде решен ефективно с помощта на стека, докато натискаме дисковете да бъдат преместени в стека, тъй като стекът всъщност действа като кула, използвана за преместване на дисковете.
Заключение
Стекът е най-простата структура от данни и по-лесна за изпълнение като програма. Той използва подхода LIFO (последен вход, първи изход), което означава, че елементът, въведен последен, е този, който се премахва първи. Това е така, защото стекът използва само един край за добавяне (избутване) и премахване (изскачане) на елементи.
Структурата на стека има много приложения в софтуерното програмиране. Изтъкнатият сред тях е оценяването на израза. Оценката на израза включва и преобразуване на израза от инфикс в постфикс или префикс. Той също така включва оценка на израза за получаване на крайния резултат.
В този урок видяхме илюстрацията и изпълнението на стека, както и различните му операции.
В нашия предстоящ урок ще научим подробно за структурата на данните за опашката.
=> Посетете тук за пълния курс на C ++ от експерти.
Препоръчително четене
- Структура на данните за опашката в C ++ с илюстрация
- Структура на данните от циркулярно свързан списък в C ++ с илюстрация
- Свързана структура на списъка с данни в C ++ с илюстрация
- Структура на данните за приоритетна опашка в C ++ с илюстрация
- Структура на данните от двойно свързан списък в C ++ с илюстрация
- Въведение в структурите на данни в C ++
- Параметризиране на данни на JMeter, използвайки дефинирани от потребителя променливи
- 10+ най-добри инструменти за събиране на данни със стратегии за събиране на данни