Struktura danych stosu jest liniowa struktura danych to następuje Zasada LIFO (ostatnie weszło, pierwsze wyszło). , więc ostatni wstawiony element będzie pierwszym, który zostanie wyskoczony. W tym artykule omówimy wszystkie podstawy stosu, operacje na stosie, jego implementację, zalety i wady, które pomogą Ci rozwiązać wszystkie problemy oparte na stosie.

Spis treści

• Co to jest struktura danych stosu?
• Podstawowe operacje na strukturze danych stosu
• Operacja isEmpty w strukturze danych stosu
• Implementacja struktury danych stosu przy użyciu listy połączonej
• Analiza złożoności operacji na strukturze danych stosu
• Zalety struktury danych stosu
• Wady struktury danych stosu
• Zastosowania struktury danych stosu

Co to jest struktura danych stosu?

Stos jest liniowa struktura danych oparte na Zasada LIFO (ostatnie weszło, pierwsze wyszło). w którym wstawienie nowego elementu i usunięcie istniejącego elementu odbywa się na tym samym końcu reprezentowanym jako szczyt stosu.

Aby zaimplementować stos, wymagane jest utrzymanie wskaźnik na górę stosu , który jest ostatnim elementem do wstawienia, ponieważ możemy uzyskać dostęp do elementów tylko na górze stosu.

Reprezentacja struktury danych stosu:

Stos działa zgodnie z zasadą LIFO (ostatnie weszło, pierwsze wyszło), więc element, który jest wypychany jako ostatni, jest wyskakujący jako pierwszy.

Stos o stałym rozmiarze : Jak sama nazwa wskazuje, stos o stałym rozmiarze ma stały rozmiar i nie może dynamicznie rosnąć ani zmniejszać się. Jeśli stos jest pełny i zostanie podjęta próba dodania do niego elementu, pojawi się błąd przepełnienia. Jeśli stos jest pusty i zostanie podjęta próba usunięcia z niego elementu, pojawi się błąd niedopełnienia.

Stos rozmiarów dynamicznych : Stos o dynamicznym rozmiarze może dynamicznie rosnąć lub zmniejszać się. Gdy stos jest pełny, automatycznie zwiększa swój rozmiar, aby pomieścić nowy element, a gdy stos jest pusty, zmniejsza swój rozmiar. Ten typ stosu jest realizowany przy użyciu listy połączonej, ponieważ pozwala na łatwą zmianę rozmiaru stosu.

Podstawowe operacje na stosie Struktura danych :

Aby dokonać manipulacji na stosie, udostępniane są nam pewne operacje.

strsep

• naciskać() aby wstawić element do stosu
• Muzyka pop() aby usunąć element ze stosu
• szczyt() Zwraca najwyższy element stosu.
• jest pusty() zwraca wartość true, jeśli stos jest pusty, w przeciwnym razie false.
• jest pełna() zwraca wartość true, jeśli stos jest pełny, w przeciwnym razie false.

Algorytm operacji Push:

• Przed wypchnięciem elementu na stos sprawdzamy czy stos jest pełny .
• Jeśli stos jest pełny (góra == pojemność-1) , Następnie Przepełnienie stosu i nie możemy wstawić elementu na stos.
• W przeciwnym razie zwiększamy wartość top o 1 (góra = góra + 1) i nowa wartość jest wstawiana w najwyższa pozycja .
• Elementy można wsuwać w stos, aż dotrzemy do pojemność stosu.

Algorytm operacji Pop:

• Przed zdjęciem elementu ze stosu sprawdzamy, czy stos jest pusty .
• Jeśli stos jest pusty (góra == -1), to Niedociągnięcia stosu i nie możemy usunąć żadnego elementu ze stosu.
• W przeciwnym razie przechowujemy wartość na górze, zmniejszamy wartość top o 1 (góra = góra – 1) i zwróć zapisaną najwyższą wartość.

Algorytm operacji z góry:

• Przed zwróceniem górnego elementu ze stosu sprawdzamy, czy stos jest pusty.
• Jeśli stos jest pusty (góra == -1), po prostu drukujemy Stos jest pusty.
• W przeciwnym razie zwracamy element przechowywany w indeks = góra .

Algorytm operacji isEmpty :

• Sprawdź wartość szczyt w stosie.
• Jeśli (góra == -1) , to stos jest pusty więc wróć PRAWDA .
• W przeciwnym razie stos nie jest pusty, więc wróć FAŁSZ .

Algorytm działania isFull:

• Sprawdź wartość szczyt w stosie.
• Jeśli (góra == pojemność-1), wtedy stos jest pełny więc wróć PRAWDA .
• W przeciwnym razie stos nie jest pełny, więc wróć FAŁSZ .

Implementacja stosu Struktura danych :

Podstawowe operacje, które można wykonać na stosie, to push, pop i peek. Istnieją dwa sposoby implementacji stosu –

• Korzystanie z tablicy
• Korzystanie z listy połączonej

W implementacji opartej na tablicach operacja wypychania jest realizowana poprzez zwiększenie indeksu najwyższego elementu i zapisanie nowego elementu pod tym indeksem. Operacja pop jest realizowana poprzez zwrócenie wartości zapisanej w górnym indeksie, a następnie zmniejszenie indeksu najwyższego elementu.

W implementacji opartej na połączonej liście operacja wypychania jest realizowana poprzez utworzenie nowego węzła z nowym elementem i ustawienie następnego wskaźnika bieżącego najwyższego węzła na nowy węzeł. Operacja pop jest realizowana poprzez ustawienie następnego wskaźnika bieżącego górnego węzła na następny węzeł i zwrócenie wartości bieżącego górnego węzła.

/* Program w C++ implementujący podstawowy stos operacje */ #włączać #włączać za pomocą przestrzeń nazw st; #zdefiniuj MAKSYMALNIE 1000 klasa Stos { wew szczyt; publiczny: wew A[MAKS]; // Maksymalny rozmiar stosu Stos() { szczyt = -1; } bool naciskać(wew X); wew Muzyka pop(); wew zerkać(); bool jest pusty(); }; bool Stos::pchnij(wew X) { Jeśli (szczyt >= (MAKS - 1)) { cout << 'stos ='' przepełnienie'<='' span=''>; powrót FAŁSZ; } w przeciwnym razie { A[++szczyt] = X; cout << X << ' wepchnięty do stosuN'; powrót PRAWDA; } } wew Stos::pop() { Jeśli (szczyt < 0) { cout << „Niedopełnienie stosu”; powrót 0; } w przeciwnym razie { wew X = A[szczyt--]; powrót X; } } wew Stos::zajrzyj() { Jeśli (szczyt < 0) { cout << „Stos jest pusty”; powrót 0; } w przeciwnym razie { wew X = A[szczyt]; powrót X; } } bool Stos::jest pusty() { powrót (szczyt < 0); } // Program sterownika do testowania powyższych funkcji wew główny() { klasa Stos S; S.naciskać(10); S.naciskać(20); S.naciskać(30); cout << S.Muzyka pop() << Wyskoczył ze stosuN'; //wydrukuj górny element stosu po wyskoczeniu cout << 'Górny element to: ' << S.zerkać() << koniec; //wydrukuj wszystkie elementy na stosie: cout <<'Elementy obecne na stosie: '; chwila(!S.jest pusty()) { //wydrukuj górny element stosu cout << S.zerkać() <<''; // usuń górny element stosu S.Muzyka pop(); } powrót 0; } //Kod został zmodyfikowany przez Vinay PandeyC

// C program for array implementation of stack #include  #include  #include  // A structure to represent a stack struct Stack {  int top;  unsigned capacity;  int* array; }; // function to create a stack of given capacity. It initializes size of // stack as 0 struct Stack* createStack(unsigned capacity) {  struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));  stack->pojemność = pojemność;  stos->góra = -1;  stos->tablica = (int*)malloc(stos->pojemność * rozmiar(int));  zwróć stos; } // Stos jest pełny, gdy góra jest równa ostatniemu indeksowi int isFull(struct Stack* stos) { return stos->góra == stos->pojemność - 1; } // Stos jest pusty, gdy wierzchołek jest równy -1 int isEmpty(struct Stack* stos) { return stos->top == -1; } // Funkcja dodawania elementu do stosu. Zwiększa górę o 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stos->tablica[++stos->góra] = element;  printf('%d przeniesione na stos
', element); } // Funkcja usuwająca element ze stosu. Zmniejsza górę o 1 int pop(struct Stack* stos) { if (isEmpty(stos)) return INT_MIN;  zwróć stos->tablica[stos->góra--]; } // Funkcja zwracająca wierzchołek stosu bez jego usuwania int peek(struct Stack* stos) { if (isEmpty(stos)) return INT_MIN;  zwróć stos->tablica[stos->góra]; } // Program sterownika do testowania powyższych funkcji int main() { struct Stack* stack = createStack(100);  push(stos, 10);  push(stos, 20);  push(stos, 30);  printf('%d wyskoczył ze stosu
', pop(stos));  zwróć 0; }>

Jawa

/* Java program to implement basic stack operations */ class Stack {  static final int MAX = 1000;  int top;  int a[] = new int[MAX]; // Maximum size of Stack  boolean isEmpty()  {  return (top < 0);  }  Stack()  {  top = -1;  }  boolean push(int x)  {  if (top>= (MAX - 1)) { System.out.println('Przepełnienie stosu');  zwróć fałsz;  } else { a[++góra] = x;  System.out.println(x + ' włożone do stosu');  zwróć wartość true;  } } int pop() { if (góra< 0) {  System.out.println('Stack Underflow');  return 0;  }  else {  int x = a[top--];  return x;  }  }  int peek()  {  if (top < 0) {  System.out.println('Stack Underflow');  return 0;  }  else {  int x = a[top];  return x;  }  }    void print(){  for(int i = top;i>-1;i--){ System.out.print(' '+ a[i]);  } } } // Klasa kodu sterownika Main { public static void main(String args[]) { Stack s = new Stack();  s.push(10);  s.push(20);  s.push(30);  System.out.println(s.pop() + ' Wyrzucono ze stosu');  System.out.println('Górny element to :' + s.peek());  System.out.print('Elementy znajdujące się na stosie:');  sprint();  } } //Ten kod został zmodyfikowany przez Vinay Pandey>

Pyton

# Python program for implementation of stack # import maxsize from sys module  # Used to return -infinite when stack is empty from sys import maxsize # Function to create a stack. It initializes size of stack as 0 def createStack(): stack = [] return stack # Stack is empty when stack size is 0 def isEmpty(stack): return len(stack) == 0 # Function to add an item to stack. It increases size by 1 def push(stack, item): stack.append(item) print(item + ' pushed to stack ') # Function to remove an item from stack. It decreases size by 1 def pop(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack.pop() # Function to return the top from stack without removing it def peek(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack[len(stack) - 1] # Driver program to test above functions  stack = createStack() push(stack, str(10)) push(stack, str(20)) push(stack, str(30)) print(pop(stack) + ' popped from stack')>

C#

// C# program to implement basic stack // operations using System; namespace ImplementStack { class Stack {  private int[] ele;  private int top;  private int max;  public Stack(int size)  {  ele = new int[size]; // Maximum size of Stack  top = -1;  max = size;  }  public void push(int item)  {  if (top == max - 1) {  Console.WriteLine('Stack Overflow');  return;  }  else {  ele[++top] = item;  }  }  public int pop()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return -1;  }  else {  Console.WriteLine('{0} popped from stack ',  ele[top]);  return ele[top--];  }  }  public int peek()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return -1;  }  else {  Console.WriteLine('{0} popped from stack ',  ele[top]);  return ele[top];  }  }  public void printStack()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return;  }  else {  for (int i = 0; i <= top; i++) {  Console.WriteLine('{0} pushed into stack',  ele[i]);  }  }  } } // Driver program to test above functions class Program {  static void Main()  {  Stack p = new Stack(5);  p.push(10);  p.push(20);  p.push(30);  p.printStack();  p.pop();  } } }>

JavaScript

/* javascript program to implement basic stack operations  */  var t = -1;  var MAX = 1000;  var a = Array(MAX).fill(0); // Maximum size of Stack  function isEmpty() {  return (t < 0);  }  function push(x) {  if (t>= (MAX - 1)) { console.log('Przepełnienie stosu');  zwróć fałsz;  } inaczej { t+=1;  a[t] = x;    console.log(x + ' umieszczone na stosie ');  zwróć wartość true;  } } funkcja pop() { if (t< 0) {  console.log('Stack Underflow');  return 0;  } else {  var x = a[t];  t-=1;  return x;  }  }  function peek() {  if (t < 0) {  console.log('Stack Underflow');  return 0;  } else {  var x = a[t];  return x;  }  }  function print() {  for (i = t; i>-1; i--) { console.log(' ' + a[i]);  } } naciśnij(10);  pchnij(20);  pchnij(30);  console.log(pop() + ' Wyrzucono ze stosu');  console.log(' Najwyższym elementem jest :' + peek());  console.log(' Elementy znajdujące się na stosie: ');  wydrukować(); // Ten kod został napisany przez Rajput-Ji>

Wyjście

10 pushed into stack 20 pushed into stack 30 pushed into stack 30 Popped from stack Top element is : 20 Elements present in stack : 20 10>

Zalety implementacji tablicy:

• Łatwe do wdrożenia.
• Pamięć jest oszczędzana, ponieważ wskaźniki nie są zaangażowane.

Wady implementacji tablic:

• Nie jest dynamiczny, tzn. nie rośnie i nie kurczy się w zależności od potrzeb w czasie wykonywania. [Ale w przypadku tablic o dynamicznych rozmiarach, takich jak wektory w C++, listy w Pythonie, ArrayList w Javie, stosy mogą również rosnąć i zmniejszać się wraz z implementacją tablic].
• Całkowity rozmiar stosu należy wcześniej określić.

// Program C++ do implementacji listy połączonej stosu #włączać za pomocą przestrzeń nazw st; // Struktura reprezentująca stos klasa Węzeł stosu { publiczny: wew dane; Węzeł stosu* Następny; }; Węzeł stosu* nowyWęzeł(wew dane) { Węzeł stosu* węzeł stosu = nowy Węzeł stosu(); węzeł stosu->dane = dane; węzeł stosu->Następny = ZERO; powrót węzeł stosu; } wew jest pusty(Węzeł stosu* źródło) { powrót !źródło; } próżnia naciskać(Węzeł stosu** źródło, wew dane) { Węzeł stosu* węzeł stosu = nowyWęzeł(dane); węzeł stosu->Następny = *źródło; *źródło = węzeł stosu; cout << dane << 'pchnięty ='' do ='' stosu<='' span=''>N'; } wew Muzyka pop(Węzeł stosu** źródło) { Jeśli (jest pusty(*źródło)) powrót INT_MIN; Węzeł stosu* temp = *źródło; *źródło = (*źródło)->Następny; wew wyskoczył = temp->dane; bezpłatny(temp); powrót wyskoczył; } wew zerkać(Węzeł stosu* źródło) { Jeśli (jest pusty(źródło)) powrót INT_MIN; powrót źródło->dane; } // Kod sterownika wew główny() { Węzeł stosu* źródło = ZERO; naciskać(&źródło, 10); naciskać(&źródło, 20); naciskać(&źródło, 30); cout << Muzyka pop(&źródło) << ' wyskoczył ze stosuN'; cout << „Górny element to” << zerkać(źródło) << koniec; cout <<'Elementy obecne na stosie: '; //wydrukuj wszystkie elementy na stosie: chwila(!jest pusty(źródło)) { //wydrukuj górny element stosu cout << zerkać(źródło) <<''; // usuń górny element stosu Muzyka pop(&źródło); } powrót 0; } // To jest kod, którego autorem jest rathbhupendraC

// C program for linked list implementation of stack #include  #include  #include  // A structure to represent a stack struct StackNode {  int data;  struct StackNode* next; }; struct StackNode* newNode(int data) {  struct StackNode* stackNode =   (struct StackNode*)  malloc(sizeof(struct StackNode));  stackNode->dane = dane;  stackNode->next = NULL;  zwróć węzeł stosu; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data);  stackNode->next = *root;  *root = węzeł stosu;  printf('%d przeniesione na stos
', dane); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struktura StackNode* temp = *root;  *root = (*root)->następny;  int pojawił się = temp->dane;  bezpłatny (tymczasowo);  powrót nastąpił; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  zwróć katalog główny->dane; } int main() { struktura StackNode* root = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d wyskoczył ze stosu
', pop(&root));  printf('Górny element to %d
', peek(root));  zwróć 0; }>

Jawa

// Java Code for Linked List Implementation public class StackAsLinkedList {  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 data)  {  StackNode newNode = new StackNode(data);  if (root == null) {  root = newNode;  }  else {  StackNode temp = root;  root = newNode;  newNode.next = temp;  }  System.out.println(data + ' pushed to stack');  }  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;  }  }  // Driver code  public static void main(String[] args)  {  StackAsLinkedList sll = new StackAsLinkedList();  sll.push(10);  sll.push(20);  sll.push(30);  System.out.println(sll.pop()  + ' popped from stack');  System.out.println('Top element is ' + sll.peek());    sll.push(10);  sll.push(20);  sll.push(30);  System.out.println(sll.pop()  + ' popped from stack');  System.out.println('Top element is ' + sll.peek());  } }>

Pyton

# Python program for linked list implementation of stack # Class to represent a node class StackNode: # Constructor to initialize a node def __init__(self, data): self.data = data self.next = None class Stack: # Constructor to initialize the root of linked list def __init__(self): self.root = None def isEmpty(self): return True if self.root is None else False def push(self, data): newNode = StackNode(data) newNode.next = self.root self.root = newNode print ('% d pushed to stack' % (data)) def pop(self): if (self.isEmpty()): return float('-inf') temp = self.root self.root = self.root.next popped = temp.data return popped def peek(self): if self.isEmpty(): return float('-inf') return self.root.data # Driver code stack = Stack() stack.push(10) stack.push(20) stack.push(30) print ('% d popped from stack' % (stack.pop())) print ('Top element is % d ' % (stack.peek())) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)>

C#

// C# Code for Linked List Implementation using System; public class StackAsLinkedList {  StackNode root;  public class StackNode {  public int data;  public StackNode next;  public StackNode(int data) { this.data = data; }  }  public bool isEmpty()  {  if (root == null) {  return true;  }  else  return false;  }  public void push(int data)  {  StackNode newNode = new StackNode(data);  if (root == null) {  root = newNode;  }  else {  StackNode temp = root;  root = newNode;  newNode.next = temp;  }  Console.WriteLine(data + ' pushed to stack');  }  public int pop()  {  int popped = int.MinValue;  if (root == null) {  Console.WriteLine('Stack is Empty');  }  else {  popped = root.data;  root = root.next;  }  return popped;  }  public int peek()  {  if (root == null) {  Console.WriteLine('Stack is empty');  return int.MinValue;  }  else {  return root.data;  }  }  // Driver code  public static void Main(String[] args)  {  StackAsLinkedList sll = new StackAsLinkedList();  sll.push(10);  sll.push(20);  sll.push(30);  Console.WriteLine(sll.pop() + ' popped from stack');  Console.WriteLine('Top element is ' + sll.peek());  } } /* This code contributed by PrinciRaj1992 */>

JavaScript

>

Wyjście

10 pushed to stack 20 pushed to stack 30 pushed to stack 30 popped from stack Top element is 20 Elements present in stack : 20 10>

Zalety implementacji listy połączonej:

• Implementacja stosu połączonej listy może rosnąć i zmniejszać się w zależności od potrzeb w czasie wykonywania.
• Jest używany w wielu maszynach wirtualnych, takich jak JVM.

Wady implementacji listy połączonej:

• Wymaga dodatkowej pamięci ze względu na użycie wskaźników.
• Losowy dostęp nie jest możliwy w stosie.

Analiza złożoności operacji na strukturze danych stosu:

Zalety stosu Struktura danych :

• Prostota: Stosy to prosta i łatwa do zrozumienia struktura danych, dzięki czemu nadają się do szerokiego zakresu zastosowań.
• Efektywność: Operacje push i pop na stosie można wykonywać w stałym czasie (O(1)) , zapewniając efektywny dostęp do danych.
• Ostatnie weszło, pierwsze wyszło (LIFO): Stosy działają zgodnie z zasadą LIFO, zapewniając, że ostatni element dodany do stosu jest pierwszym usuniętym. To zachowanie jest przydatne w wielu scenariuszach, takich jak wywołania funkcji i ocena wyrażeń.
• Ograniczone wykorzystanie pamięci: Stosy muszą przechowywać jedynie elementy, które zostały na nie wypchnięte, dzięki czemu są wydajne pod względem pamięci w porównaniu z innymi strukturami danych.

Wady stosu Struktura danych :

• Ograniczony dostęp: Dostęp do elementów stosu można uzyskać jedynie od góry, co utrudnia pobieranie lub modyfikowanie elementów znajdujących się na środku stosu.
• Potencjał przepełnienia: Jeśli na stos zostanie wepchniętych więcej elementów, niż jest w stanie pomieścić, wystąpi błąd przepełnienia, co spowoduje utratę danych.
• Nie nadaje się do dostępu swobodnego: Stos nie pozwalają na losowy dostęp do elementów, co czyni je nieodpowiednimi do zastosowań, w których dostęp do elementów musi być dostępny w określonej kolejności.
• Ograniczona pojemność: Stosy mają stałą pojemność, co może stanowić ograniczenie, jeśli liczba elementów, które należy przechowywać, jest nieznana lub bardzo zmienna.

Zastosowania struktury danych stosu:

• Infix do Postfixa /Konwersja prefiksu
• Funkcje ponownego cofania dostępne w wielu miejscach, takich jak edytory, Photoshop.
• Funkcje przewijania do przodu i do tyłu w przeglądarkach internetowych
• W zarządzaniu pamięcią każdy nowoczesny komputer używa stosu jako podstawowego narzędzia do zarządzania w bieżącym celu. Każdy program działający w systemie komputerowym ma własne przydziały pamięci.
• Stack pomaga również we wdrażaniu wywołań funkcji w komputerach. Ostatnia wywołana funkcja jest zawsze wykonywana jako pierwsza.

Powiązane artykuły:

• Zaimplementuj stos przy użyciu listy pojedynczo połączonej
• Podstawowe operacje na strukturze danych stosu z implementacjami
• 50 najważniejszych problemów ze strukturą danych stosu zadawanych w wywiadach SDE
• Zastosowania, zalety i wady stosu
  
• Stos do programowania konkurencyjnego