Stos to liniowa struktura danych, która następuje po LIFO (ostatni na wejściu, pierwszy na wyjściu) zasada. Stos ma jeden koniec, podczas gdy kolejka ma dwa końce ( przód i tył ). Zawiera tylko jeden wskaźnik górny wskaźnik wskazując na najwyższy element stosu. Za każdym razem, gdy element jest dodawany do stosu, jest on dodawany na wierzchu stosu i element można usunąć tylko ze stosu. Innymi słowy, A stos można zdefiniować jako pojemnik, w którym można wstawiać i usuwać elementy z jednego końca, zwanego wierzchołkiem stosu.
Kilka kluczowych punktów związanych ze stosem
- Nazywa się to stosem, ponieważ zachowuje się jak stos w świecie rzeczywistym, stosy książek itp.
- Stos to abstrakcyjny typ danych o z góry określonej pojemności, co oznacza, że może przechowywać elementy o ograniczonym rozmiarze.
- Jest to struktura danych, w której następuje pewna kolejność wstawiania i usuwania elementów, a kolejność ta może być LIFO lub FILO.
Działanie stosu
Stos działa na wzór LIFO. Jak widać na poniższym rysunku, na stosie znajduje się pięć bloków pamięci; dlatego rozmiar stosu wynosi 5.
js ładuje
Załóżmy, że chcemy przechowywać elementy na stosie i załóżmy, że stos jest pusty. Wzięliśmy stos o rozmiarze 5, jak pokazano poniżej, w którym przesuwamy elementy jeden po drugim, aż stos się zapełni.
Ponieważ nasz stos jest pełny, gdyż rozmiar stosu wynosi 5. W powyższych przypadkach możemy zaobserwować, że podczas wchodzenia do nowego elementu stosu przesuwa się on z góry na dół. Stos jest zapełniany od dołu do góry.
Kiedy wykonujemy operację usuwania na stosie, istnieje tylko jedna droga wejścia i wyjścia, ponieważ drugi koniec jest zamknięty. Działa zgodnie ze wzorem LIFO, co oznacza, że wartość wpisana jako pierwsza zostanie usunięta jako ostatnia. W powyższym przypadku jako pierwsza wpisywana jest wartość 5, zatem zostanie ona usunięta dopiero po usunięciu wszystkich pozostałych elementów.
Standardowe operacje na stosie
Poniżej przedstawiono kilka typowych operacji realizowanych na stosie:
Operacja PUSH
Poniżej przedstawiono kroki związane z operacją PUSH:
- Przed włożeniem elementu do stosu sprawdzamy, czy stos jest pełny.
- Jeśli spróbujemy wstawić element na stos, a stos jest pełny, to przelewowy warunek występuje.
- Kiedy inicjujemy stos, ustawiamy wartość top na -1, aby sprawdzić, czy stos jest pusty.
- Kiedy nowy element jest umieszczany na stosie, najpierw zwiększana jest wartość wierzchołka, tj. góra=góra+1, a element zostanie umieszczony w nowej pozycji szczyt .
- Elementy będą wstawiane aż dotrzemy do maks wielkość stosu.
Operacja POP
Poniżej przedstawiono kroki związane z operacją POP:
ciąg do znaku
- Przed usunięciem elementu ze stosu sprawdzamy, czy stos jest pusty.
- Jeśli spróbujemy usunąć element z pustego stosu, to niedomiar warunek występuje.
- Jeśli stos nie jest pusty, najpierw uzyskujemy dostęp do elementu wskazanego przez szczyt
- Po wykonaniu operacji pop górna część jest zmniejszana o 1, tj. góra=góra-1 .
Zastosowania stosu
Oto zastosowania stosu:
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';>