Стекът е линейна структура от данни, която следва LIFO (последен влязъл първи излязъл) принцип. Стекът има един край, докато опашката има два края ( отпред и отзад ). Съдържа само един указател горен показалец сочещи към най-горния елемент на стека. Всеки път, когато се добави елемент в стека, той се добавя в горната част на стека и елементът може да бъде изтрит само от стека. С други думи, a стекът може да се дефинира като контейнер, в който вмъкването и изтриването може да се извършва от единия край, известен като върха на стека.
Някои ключови точки, свързани със стека
- Нарича се стек, защото се държи като стек от реалния свят, купища книги и т.н.
- Стекът е абстрактен тип данни с предварително определен капацитет, което означава, че може да съхранява елементи с ограничен размер.
- Това е структура от данни, която следва някакъв ред за вмъкване и изтриване на елементите и този ред може да бъде LIFO или FILO.
Работа на стека
Стекът работи по модела LIFO. Както можем да видим на фигурата по-долу има пет блока памет в стека; следователно размерът на стека е 5.
fmoviez
Да предположим, че искаме да съхраним елементите в стек и нека приемем, че стекът е празен. Взехме стека с размер 5, както е показано по-долу, в който натискаме елементите един по един, докато стекът се напълни.
Тъй като нашият стек е пълен, тъй като размерът на стека е 5. В горните случаи можем да наблюдаваме, че той върви от върха към дъното, когато въвеждаме новия елемент в стека. Стекът се запълва отдолу нагоре.
Когато изпълняваме операцията за изтриване на стека, има само един начин за влизане и излизане, тъй като другият край е затворен. Той следва модела LIFO, което означава, че въведената първа стойност ще бъде премахната последна. В горния случай първо се въвежда стойността 5, така че тя ще бъде премахната едва след изтриването на всички останали елементи.
Стандартни операции със стека
Следват някои често срещани операции, изпълнявани в стека:
python rstrip
PUSH операция
Стъпките, включени в операцията PUSH, са дадени по-долу:
- Преди да вмъкнем елемент в стек, проверяваме дали стекът е пълен.
- Ако се опитаме да вмъкнем елемента в стек и стекът е пълен, тогава препълване възниква състояние.
- Когато инициализираме стек, задаваме стойността на top като -1, за да проверим дали стекът е празен.
- Когато новият елемент се избута в стек, първо стойността на върха се увеличава, т.е. отгоре=отгоре+1, и елементът ще бъде поставен на новата позиция на Горна част .
- Елементите ще бъдат вмъкнати, докато стигнем до макс размер на стека.
POP операция
Стъпките, включени в POP операцията, са дадени по-долу:
- Преди да изтрием елемента от стека, проверяваме дали стекът е празен.
- Ако се опитаме да изтрием елемента от празния стек, тогава подток възниква състояние.
- Ако стекът не е празен, първо имаме достъп до елемента, който е посочен от Горна част
- След като се извърши операцията за изскачане, горната част се намалява с 1, т.е. топ=топ-1 .
Приложения на Stack
Следните са приложенията на стека:
int main() { cout<<'hello'; cout<<'javatpoint'; } < pre> <p>As we know, each program has <em>an opening</em> and <em>closing</em> braces; when the opening braces come, we push the braces in a stack, and when the closing braces appear, we pop the opening braces from the stack. Therefore, the net value comes out to be zero. If any symbol is left in the stack, it means that some syntax occurs in a program.</p> <ul> <tr><td>String reversal:</td> Stack is also used for reversing a string. For example, we want to reverse a ' <strong>javaTpoint</strong> ' string, so we can achieve this with the help of a stack. <br> First, we push all the characters of the string in a stack until we reach the null character. <br> After pushing all the characters, we start taking out the character one by one until we reach the bottom of the stack. </tr><tr><td>UNDO/REDO:</td> It can also be used for performing UNDO/REDO operations. For example, we have an editor in which we write 'a', then 'b', and then 'c'; therefore, the text written in an editor is abc. So, there are three states, a, ab, and abc, which are stored in a stack. There would be two stacks in which one stack shows UNDO state, and the other shows REDO state. <br> If we want to perform UNDO operation, and want to achieve 'ab' state, then we implement pop operation. </tr><tr><td>Recursion:</td> The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained. </tr><tr><td>DFS(Depth First Search):</td> This search is implemented on a Graph, and Graph uses the stack data structure. </tr><tr><td>Backtracking:</td> Suppose we have to create a path to solve a maze problem. If we are moving in a particular path, and we realize that we come on the wrong way. In order to come at the beginning of the path to create a new path, we have to use the stack data structure. </tr><tr><td>Expression conversion:</td> Stack can also be used for expression conversion. This is one of the most important applications of stack. The list of the expression conversion is given below: <pre>Infix to prefix Infix to postfix Prefix to infix Prefix to postfix Postfix to infix</pre> </tr><tr><td>Memory management:</td> The stack manages the memory. The memory is assigned in the contiguous memory blocks. The memory is known as stack memory as all the variables are assigned in a function call stack memory. The memory size assigned to the program is known to the compiler. When the function is created, all its variables are assigned in the stack memory. When the function completed its execution, all the variables assigned in the stack are released. </tr></ul> <hr></'hello';>