Stack Data Structure je a lineárna dátová štruktúra to nasleduje Princíp LIFO (Last In First Out). , takže posledný vložený prvok je prvý, ktorý sa vysunie. V tomto článku pokryjeme všetky základy Stacku, operácie na Stacku, jeho implementáciu, výhody a nevýhody, ktoré vám pomôžu vyriešiť všetky problémy založené na Stacku.

Obsah

• Čo je štruktúra údajov zásobníka?
• Základné operácie so štruktúrou údajov zásobníka
• Operácia isEmpty v dátovej štruktúre zásobníka
• Implementácia Stack Data Structure pomocou Linked List
• Analýza zložitosti operácií na dátovej štruktúre zásobníka
• Výhody štruktúry dátových zásobníkov
• Nevýhody štruktúry dátových zásobníkov
• Aplikácie Stack Data Structure

Čo je štruktúra údajov zásobníka?

Stoh je a lineárna dátová štruktúra založené na Princíp LIFO (Last In First Out). v ktorom sa vloženie nového prvku a odstránenie existujúceho prvku uskutoční na rovnakom konci, ktorý je znázornený ako top zo zásobníka.

Na implementáciu zásobníka je potrebné udržiavať ukazovateľ na vrchol zásobníka , čo je posledný prvok, ktorý sa má vložiť, pretože máme prístup k prvkom iba na vrchu zásobníka.

Reprezentácia dátovej štruktúry zásobníka:

Zásobník sa riadi princípom LIFO (Last In First Out), takže prvok, ktorý je zatlačený ako posledný, vyskočí ako prvý.

Stack s pevnou veľkosťou : Ako už názov napovedá, zásobník s pevnou veľkosťou má pevnú veľkosť a nemôže dynamicky rásť ani sa zmenšovať. Ak je zásobník plný a vykoná sa pokus o pridanie prvku do neho, dôjde k chybe pretečenia. Ak je zásobník prázdny a vykoná sa pokus o odstránenie prvku z neho, dôjde k chybe podtečenia.

Dynamický zásobník veľkostí : Zásobník dynamickej veľkosti sa môže dynamicky zväčšovať alebo zmenšovať. Keď je zásobník plný, automaticky zväčší svoju veľkosť, aby sa do neho zmestil nový prvok, a keď je zásobník prázdny, jeho veľkosť sa zmenší. Tento typ zásobníka sa implementuje pomocou prepojeného zoznamu, pretože umožňuje jednoduchú zmenu veľkosti zásobníka.

Základné operácie na zásobníku Dátová štruktúra :

Na vykonanie manipulácií v zásobníku sú nám poskytnuté určité operácie.

mvc java

• TAM() na vloženie prvku do zásobníka
• pop() na odstránenie prvku zo zásobníka
• top() Vráti horný prvok zásobníka.
• je prázdny() vráti true, ak je zásobník prázdny, inak false.
• je plný() vráti true, ak je zásobník plný, inak false.

Algoritmus pre operáciu push:

• Pred zatlačením prvku do stohu skontrolujeme, či je stoh plný .
• Ak je zásobník plný (hore == kapacita-1) , potom Stack Overflows a nemôžeme vložiť prvok do zásobníka.
• V opačnom prípade zvýšime hodnotu top o 1 (hore = hore + 1) a nová hodnota sa vloží do horná pozícia .
• Prvky môžu byť zasunuté do stohu, kým nedosiahneme kapacita zo zásobníka.

Algoritmus pre operáciu Pop:

• Pred vytiahnutím prvku zo zásobníka skontrolujeme, či je zásobník prázdny .
• Ak je zásobník prázdny (horný == -1), potom Stack Underflows a nemôžeme odstrániť žiadny prvok zo zásobníka.
• V opačnom prípade uložíme hodnotu hore, hodnotu top znížime o 1 (hore = hore – 1) a vrátiť uloženú najvyššiu hodnotu.

Algoritmus hornej operácie:

• Pred vrátením vrchného prvku zo stohu skontrolujeme, či je stoh prázdny.
• Ak je zásobník prázdny (vrchol == -1), jednoducho vytlačíme Zásobník je prázdny.
• V opačnom prípade vrátime prvok uložený na index = vrchol .

Algoritmus pre operáciu isEmpty :

• Skontrolujte hodnotu top v zásobníku.
• Ak (hore == -1) , potom je zásobník prázdny tak sa vráť pravda .
• V opačnom prípade zásobník nie je prázdny, takže sa vráťte falošné .

Algoritmus pre operáciu isFull:

• Skontrolujte hodnotu top v zásobníku.
• Ak (hore == kapacita-1), potom je zásobník plný tak sa vráť pravda .
• V opačnom prípade nie je zásobník plný, takže sa vráťte falošné .

Implementácia Stack Dátová štruktúra :

Medzi základné operácie, ktoré možno vykonávať na zásobníku, patrí push, pop a peek. Existujú dva spôsoby, ako implementovať zásobník –

• Pomocou Array
• Pomocou prepojeného zoznamu

V implementácii založenej na poli sa operácia push implementuje zvýšením indexu horného prvku a uložením nového prvku do tohto indexu. Operácia pop sa implementuje vrátením hodnoty uloženej v hornom indexe a následným znížením indexu horného prvku.

V implementácii založenej na prepojenom zozname sa operácia push implementuje vytvorením nového uzla s novým prvkom a nastavením ďalšieho ukazovateľa aktuálneho horného uzla na nový uzol. Operácia pop sa implementuje nastavením ďalšieho ukazovateľa aktuálneho horného uzla na nasledujúci uzol a vrátením hodnoty aktuálneho horného uzla.

/* C++ program na implementáciu základného zásobníka operácie */ #include #include použitím menný priestor std; #define MAX 1000 trieda Stoh { int top; verejnosti: int a[MAX]; // Maximálna veľkosť zásobníka Stoh() { top = -1; } bool TAM(int X); int pop(); int nahliadnuť(); bool je prázdny(); }; bool Stack::push(int X) { ak (top >= (MAX - 1)) { cout << ' stack='' overflow'<='' span=''>; vrátiť falošné; } inak { a[++top] = X; cout << X << ' zasunutý do stohu '; vrátiť pravda; } } int Zásobník::pop() { ak (top < 0) { cout << 'Stack Underflow'; vrátiť 0; } inak { int X = a[top--]; vrátiť X; } } int Stack::peek() { ak (top < 0) { cout << „Zásobník je prázdny“; vrátiť 0; } inak { int X = a[top]; vrátiť X; } } bool Stack::isEmpty() { vrátiť (top < 0); } // Program ovládača na testovanie vyššie uvedených funkcií int Hlavná() { trieda Stoh s; s.TAM(10); s.TAM(dvadsať); s.TAM(30); cout << s.pop() << ' Vypadlo zo stohu '; //vytlačí horný prvok zásobníka po prasknutí cout << 'Horný prvok je:' << s.nahliadnuť() << endl; //vytlačí všetky prvky v zásobníku: cout <<'Prvky prítomné v zásobníku:'; zatiaľ čo(!s.je prázdny()) { // vytlačí horný prvok v zásobníku cout << s.nahliadnuť() <<' '; // odstránenie horného prvku v zásobníku s.pop(); } vrátiť 0; } //Kód upravil 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->kapacita = kapacita;  zásobník->vrchol = -1;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  návratový zásobník; } // Zásobník je plný, keď sa vrchol rovná poslednému indexu int isFull(struct Zásobník* zásobník) { return zásobník->vrchol == zásobník->kapacita - 1; } // Zásobník je prázdny, keď sa vrchol rovná -1 int isEmpty(struct Zásobník* zásobník) { return stack->top == -1; } // Funkcia na pridanie položky do zásobníka. Zvyšuje vrchol o 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stack->array[++stack->top] = položka;  printf('%d posunuté do zásobníka
', položka); } // Funkcia na odstránenie položky zo zásobníka. Zníži vrchol o 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top--]; } // Funkcia na vrátenie vrcholu zásobníka bez jeho odstránenia int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top]; } // Program ovládača na testovanie vyššie uvedených funkcií int main() { struct Stack* stack = createStack(100);  push(stack, 10);  push(stack, 20);  push(stack, 30);  printf('%d vyskočilo zo zásobníka
', pop(zásobník));  návrat 0; }>

Java

/* 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('Pretečenie zásobníka');  vrátiť nepravdu;  } else { a[++top] = x;  System.out.println(x + ' vložené do zásobníka');  vrátiť true;  } } int pop() { if (top< 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]);  } } } // Trieda kódu ovládača 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() + ' Vybraté zo zásobníka');  System.out.println('Horný prvok je :' + s.peek());  System.out.print('Prvky prítomné v zásobníku:');  s.print();  } } //Tento kód upravil Vinay Pandey>

Python

# 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('Pretečenie zásobníka');  vrátiť nepravdu;  } else { t+=1;  a[t] = x;    console.log(x + ' vložené do zásobníka ');  vrátiť true;  } } function 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]);  } } push(10);  push(20);  push(30);  console.log(pop() + ' Vyskočilo zo zásobníka');  console.log(' Vrchný prvok je :' + peek());  console.log(' Prvky prítomné v zásobníku: ');  print(); // Tento kód prispel Rajput-Ji>

Výkon

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>

Výhody implementácie Array:

• Jednoduchá implementácia.
• Pamäť je uložená, pretože ukazovatele nie sú zahrnuté.

Nevýhody implementácie Array:

• Nie je dynamický, t. j. nerastie a nezmenšuje sa v závislosti od potrieb počas behu. [Ale v prípade polí s dynamickou veľkosťou, ako je vektor v C++, zoznam v Pythone, ArrayList v Jave, môžu zásobníky rásť a zmenšovať aj s implementáciou poľa].
• Celková veľkosť zásobníka musí byť definovaná vopred.

// C++ program na implementáciu prepojeného zoznamu zásobníka #include použitím menný priestor std; // Štruktúra reprezentujúca zásobník trieda StackNode { verejnosti: int údajov; StackNode* Ďalšie; }; StackNode* newNode(int údajov) { StackNode* stackNode = Nový StackNode(); stackNode->údajov = údajov; stackNode->Ďalšie = NULOVÝ; vrátiť stackNode; } int je prázdny(StackNode* koreň) { vrátiť !koreň; } neplatné TAM(StackNode** koreň, int údajov) { StackNode* stackNode = newNode(údajov); stackNode->Ďalšie = *koreň; *koreň = stackNode; cout << údajov << ' push='' to='' stack<='' span=''> '; } int pop(StackNode** koreň) { ak (je prázdny(*koreň)) vrátiť INT_MIN; StackNode* tepl = *koreň; *koreň = (*koreň)->Ďalšie; int prasklo = tepl->údajov; zadarmo(tepl); vrátiť prasklo; } int nahliadnuť(StackNode* koreň) { ak (je prázdny(koreň)) vrátiť INT_MIN; vrátiť koreň->údajov; } // Kód ovládača int Hlavná() { StackNode* koreň = NULOVÝ; TAM(&koreň, 10); TAM(&koreň, dvadsať); TAM(&koreň, 30); cout << pop(&koreň) << “ vyskočilo zo stohu '; cout << 'Horný prvok je' << nahliadnuť(koreň) << endl; cout <<'Prvky prítomné v zásobníku:'; //vytlačí všetky prvky v zásobníku: zatiaľ čo(!je prázdny(koreň)) { // vytlačí horný prvok v zásobníku cout << nahliadnuť(koreň) <<' '; // odstránenie horného prvku v zásobníku pop(&koreň); } vrátiť 0; } // Tento kód prispel 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->dáta = dáta;  stackNode->next = NULL;  return stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data);  stackNode->next = *root;  *root = stackNode;  printf('%d vložené do zásobníka
', dáta); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *root;  *koreň = (*koreň)->ďalší;  int vyskocene = temp->data;  voľný (temp);  návrat vyskočený; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  return root->data; } int main() { struct StackNode* root = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d vyskočilo zo zásobníka
', pop(&root));  printf('Horný prvok je %d
', peek(root));  návrat 0; }>

Java

// 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());  } }>

Python

# 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

>

Výkon

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>

Výhody implementácie prepojeného zoznamu:

• Implementácia prepojeného zoznamu zásobníka môže počas behu rásť a zmenšovať sa podľa potrieb.
• Používa sa v mnohých virtuálnych strojoch, ako je JVM.

Nevýhody implementácie prepojeného zoznamu:

• Vyžaduje dodatočnú pamäť kvôli zapojeniu ukazovateľov.
• V zásobníku nie je možný náhodný prístup.

Analýza zložitosti operácií na dátovej štruktúre zásobníka:

Výhody Stack Dátová štruktúra :

• jednoduchosť: Zásobníky sú jednoduchou a ľahko pochopiteľnou dátovou štruktúrou, vďaka čomu sú vhodné pre širokú škálu aplikácií.
• Účinnosť: Operácie push a pop na zásobníku možno vykonávať v konštantnom čase (O(1)) poskytujúci efektívny prístup k údajom.
• Posledný dnu, prvý von (LIFO): Stohy sa riadia princípom LIFO, ktorý zaisťuje, že posledný prvok pridaný do stohu je prvý odstránený. Toto správanie je užitočné v mnohých scenároch, ako sú volania funkcií a vyhodnocovanie výrazov.
• Obmedzené využitie pamäte: Zásobníky potrebujú ukladať iba prvky, ktoré sa na ne vložili, vďaka čomu sú pamäťovo efektívne v porovnaní s inými dátovými štruktúrami.

Nevýhody Stack Dátová štruktúra :

• Obmedzený prístup: Prvky v stohu sú prístupné iba zhora, čo sťažuje načítanie alebo úpravu prvkov v strede stohu.
• Potenciál pretečenia: Ak sa do zásobníka vloží viac prvkov, ako sa doňho zmestí, dôjde k chybe pretečenia, čo vedie k strate údajov.
• Nevhodné pre náhodný prístup: Stoh s neumožňujú náhodný prístup k prvkom, takže sú nevhodné pre aplikácie, kde je potrebné pristupovať k prvkom v špecifickom poradí.
• Obmedzená kapacita: Zásobníky majú pevnú kapacitu, čo môže byť obmedzenie, ak je počet prvkov, ktoré je potrebné uložiť, neznámy alebo veľmi variabilný.

Aplikácie štruktúry dát zásobníka:

• Infix do Postfixu /Premena predpony
• Znova vrátiť funkcie na mnohých miestach, ako sú editory, photoshop.
• Funkcie dopredu a dozadu vo webových prehliadačoch
• V správe pamäte každý moderný počítač používa zásobník ako primárnu správu na prevádzkový účel. Každý program, ktorý je spustený v počítačovom systéme, má svoje vlastné pridelenie pamäte.
• Stack tiež pomáha pri implementácii volania funkcií v počítačoch. Posledná volaná funkcia sa vždy dokončí ako prvá.

Súvisiace články:

• Implementujte zásobník pomocou samostatne prepojeného zoznamu
• Základné operácie v štruktúre dát zásobníka s implementáciami
• 50 najčastejších problémov so štruktúrou údajov zásobníka, ktoré sa pýtali v rozhovoroch SDE
• Aplikácie, výhody a nevýhody Stack
  
• Zásobník pre konkurencieschopné programovanie