Struktura dat zásobníku je lineární datová struktura to následuje Princip LIFO (Last In First Out). , takže poslední vložený prvek je první, který se vysune. V tomto článku pokryjeme všechny základy Stacku, operace na Stacku, jeho implementaci, výhody a nevýhody, které vám pomohou vyřešit všechny problémy založené na Stacku.

Obsah

• Co je struktura dat zásobníku?
• Základní operace s datovou strukturou zásobníku
• Operace isEmpty v datové struktuře zásobníku
• Implementace datové struktury zásobníku pomocí Linked List
• Analýza složitosti operací na datové struktuře zásobníku
• Výhody datové struktury zásobníku
• Nevýhody datové struktury zásobníku
• Aplikace Stack Data Structure

Co je struktura dat zásobníku?

Zásobník je lineární datová struktura na základě Princip LIFO (Last In First Out). ve kterém vložení nového prvku a odstranění existujícího prvku probíhá na stejném konci reprezentovaném jako horní ze zásobníku.

Pro implementaci zásobníku je nutné udržovat ukazatel na vrchol zásobníku , což je poslední prvek, který má být vložen, protože k prvkům máme přístup pouze v horní části zásobníku.

Reprezentace datové struktury zásobníku:

Stack se řídí principem LIFO (Last In First Out), takže prvek, který je zatlačen jako poslední, je vysunut jako první.

Zásobník s pevnou velikostí : Jak název napovídá, zásobník pevné velikosti má pevnou velikost a nemůže dynamicky růst ani zmenšovat. Pokud je zásobník plný a dojde k pokusu o přidání prvku do něj, dojde k chybě přetečení. Pokud je zásobník prázdný a dojde k pokusu o odebrání prvku z něj, dojde k chybě podtečení.

Dynamická velikost zásobníku : Zásobník dynamických velikostí se může dynamicky zvětšovat nebo zmenšovat. Když je zásobník plný, automaticky se zvětší jeho velikost, aby se do něj vešel nový prvek, a když je zásobník prázdný, jeho velikost se zmenší. Tento typ zásobníku je implementován pomocí propojeného seznamu, protože umožňuje snadnou změnu velikosti zásobníku.

Základní operace na Stacku Datová struktura :

Aby bylo možné provádět manipulace v zásobníku, jsou nám poskytnuty určité operace.

• TAM() pro vložení prvku do zásobníku
• pop() k odstranění prvku ze zásobníku
• horní() Vrátí horní prvek zásobníku.
• je prázdný() vrátí true, pokud je zásobník prázdný, jinak false.
• je plný() vrátí true, pokud je zásobník plný, jinak false.

Algoritmus pro push operaci:

• Před zatlačením prvku do stohu zkontrolujeme, zda je stoh plný .
• Pokud je zásobník plný (nahoře == kapacita-1) , pak Přetečení zásobníku a nemůžeme vložit prvek do zásobníku.
• V opačném případě zvýšíme hodnotu top o 1 (nahoře = nahoře + 1) a nová hodnota se vloží do nejvyšší pozice .
• Prvky lze zasunout do stohu, dokud nedosáhneme kapacita ze zásobníku.

Algoritmus pro operaci Pop:

• Před vyjmutím prvku ze zásobníku zkontrolujeme, zda je zásobník prázdný .
• Pokud je zásobník prázdný (horní == -1), pak Podtečení zásobníku a nemůžeme odstranit žádný prvek ze zásobníku.
• Jinak uložíme hodnotu nahoře, hodnotu top snížíme o 1 (nahoře = nahoře – 1) a vrátit uloženou nejvyšší hodnotu.

Algoritmus pro nejvyšší operaci:

• Před vrácením horního prvku ze zásobníku zkontrolujeme, zda je zásobník prázdný.
• Pokud je zásobník prázdný (horní == -1), jednoduše vytiskneme Zásobník je prázdný.
• V opačném případě vrátíme prvek uložený na index = top .

Algoritmus pro operaci isEmpty :

• Zkontrolujte hodnotu horní v zásobníku.
• Li (nahoře == -1) , pak je zásobník prázdný tak se vrať skutečný .
• V opačném případě není zásobník prázdný, takže se vraťte Nepravdivé .

Algoritmus pro isFull Operation:

• Zkontrolujte hodnotu horní v zásobníku.
• Li (nahoře == kapacita-1), pak je zásobník plný tak se vrať skutečný .
• V opačném případě není zásobník plný, takže se vraťte Nepravdivé .

Implementace Stack Datová struktura :

Mezi základní operace, které lze provádět na zásobníku, patří push, pop a peek. Existují dva způsoby, jak implementovat zásobník –

• Pomocí Array
• Pomocí propojeného seznamu

V implementaci založené na poli je operace push implementována zvýšením indexu horního prvku a uložením nového prvku do tohoto indexu. Operace pop je implementována vrácením hodnoty uložené v horním indexu a následným snížením indexu horního prvku.

V implementaci založené na propojeném seznamu je operace push implementována vytvořením nového uzlu s novým prvkem a nastavením dalšího ukazatele aktuálního horního uzlu na nový uzel. Operace pop je implementována nastavením dalšího ukazatele aktuálního horního uzlu na další uzel a vrácením hodnoty aktuálního horního uzlu.

; vrátit se Nepravdivé ; } jiný { A [ ++ horní ] = X ; cout < < X < < “ strčil do stohu ' ; vrátit se skutečný ; } } int Zásobník::pop () { -li ( horní < 0 ) { cout < < 'Podtečení zásobníku' ; vrátit se 0 ; } jiný { int X = A [ horní -- ]; vrátit se X ; } } int Zásobník::pohled () { -li ( horní < 0 ) { cout < < 'Zásobník je prázdný' ; vrátit se 0 ; } jiný { int X = A [ horní ]; vrátit se X ; } } bool Stack::isEmpty () { vrátit se ( horní < 0 ); } // Program ovladače pro testování výše uvedených funkcí int hlavní () { třída Zásobník s ; s . TAM ( 10 ); s . TAM ( dvacet ); s . TAM ( 30 ); cout < < s . pop () < < ' Vypadl ze stohu ' ; //tisk horního prvku zásobníku po prasknutí cout < < 'Horní prvek je:' < < s . nahlédnout () < < endl ; //vytiskne všechny prvky v zásobníku: cout < < 'Prvky přítomné v zásobníku:' ; zatímco ( ! s . je prázdný ()) { // tisk horního prvku v zásobníku cout < < s . nahlédnout () < < ' ' ; // odstranění horního prvku ze zásobníku s . pop (); } vrátit se 0 ; } //Kód upravil Vinay Pandey C

// 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;  stack->top = -1;  stack->array = (int*)malloc(stack->kapacita * sizeof(int));  návratový zásobník; } // Zásobník je plný, když se vrchol rovná poslednímu indexu int isFull(struct Zásobník* zásobník) { return zásobník->top == zásobník->kapacita - 1; } // Zásobník je prázdný, když se vrchol rovná -1 int isEmpty(struct Zásobník* zásobník) { return stack->top == -1; } // Funkce pro přidání položky do zásobníku. Zvyšuje vrchol o 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stack->array[++stack->top] = položka;  printf('%d odesláno do zásobníku
', položka); } // Funkce pro odstranění položky ze zásobníku. Sníží vrchol o 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top--]; } // Funkce pro vrácení vrcholu ze zásobníku bez jeho odstranění int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top]; } // Program ovladače pro testování výše uvedených funkcí int main() { struct Stack* stack = createStack(100);  push(stack, 10);  push(stack, 20);  push(stack, 30);  printf('%d vyskočilo ze zásobníku
', pop(stack));  návrat 0; } 

Jáva

/* 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('Přetečení zásobníku');  vrátit false;  } else { a[++horní] = x;  System.out.println(x + ' vloženo do zásobníku');  vrátit true;  } } int pop() { if (nahoře < 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]);  } } } // Třída kódu ovladače 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() + ' Vytaženo ze zásobníku');  System.out.println('Horní prvek je :' + s.peek());  System.out.print('Prvky přítomné v zásobníku:');  sprint();  } } //Tento kód upravil Vinay Pandey 

Krajta

# 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('Přetečení zásobníku');  vrátit false;  } else { t+=1;  a[t] = x;    console.log(x + ' vloženo do zásobníku ');  vrátit 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() + ' Vytaženo ze zásobníku');  console.log(' Horní prvek je :' + peek());  console.log(' Prvky přítomné v zásobníku: ');  tisk(); // Tento kód přispěl Rajput-Ji 

Výstup

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 implementace Array:

• Snadná implementace.
• Paměť je uložena, protože ukazatele nejsou zapojeny.

Nevýhody implementace pole:

• Není dynamický, tj. neroste a nezmenšuje se v závislosti na potřebách za běhu. [Ale v případě polí s dynamickou velikostí, jako je vektor v C++, seznam v Pythonu, ArrayList v Javě, mohou zásobníky růst a zmenšovat také s implementací pole].
• Celková velikost zásobníku musí být definována předem.

' ; } int pop ( StackNode ** vykořenit ) { -li ( je prázdný ( * vykořenit )) vrátit se INT_MIN ; StackNode * tepl = * vykořenit ; * vykořenit = ( * vykořenit ) -> další ; int prasklo = tepl -> data ; volný, uvolnit ( tepl ); vrátit se prasklo ; } int nahlédnout ( StackNode * vykořenit ) { -li ( je prázdný ( vykořenit )) vrátit se INT_MIN ; vrátit se vykořenit -> data ; } // Kód ovladače int hlavní () { StackNode * vykořenit = NULA ; TAM ( & vykořenit , 10 ); TAM ( & vykořenit , dvacet ); TAM ( & vykořenit , 30 ); cout < < pop ( & vykořenit ) < < “ vypadlo ze zásobníku ' ; cout < < 'Horní prvek je' < < nahlédnout ( vykořenit ) < < endl ; cout < < 'Prvky přítomné v zásobníku:' ; //vytiskne všechny prvky v zásobníku: zatímco ( ! je prázdný ( vykořenit )) { // tisk horního prvku v zásobníku cout < < nahlédnout ( vykořenit ) < < ' ' ; // odstranění horního prvku ze zásobníku pop ( & vykořenit ); } vrátit se 0 ; } // Tento kód přispěl rathbhupendra C

// 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->data = data;  stackNode->next = NULL;  return stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** kořen, int data) { struct StackNode* stackNode = newNode(data);  stackNode->next = *root;  *root = stackNode;  printf('%d odesláno do zásobníku
', data); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *root;  *kořen = (*kořen)->další;  int popped = temp->data;  free(temp);  návrat vyskočil; } 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 ze zásobníku
', pop(&root));  printf('Horní prvek je %d
', peek(kořen));  návrat 0; } 

Jáva

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

Krajta

# 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ýstup

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 implementace Linked List:

• Implementace propojeného seznamu zásobníku se může za běhu zvětšovat a zmenšovat podle potřeb.
• Používá se v mnoha virtuálních strojích, jako je JVM.

Nevýhody implementace Linked List:

• Vyžaduje další paměť kvůli zapojení ukazatelů.
• V zásobníku není možný náhodný přístup.

Analýza složitosti operací na datové struktuře zásobníku:

Výhody Stack Datová struktura :

• Jednoduchost: Zásobníky jsou jednoduchou a snadno pochopitelnou datovou strukturou, díky čemuž jsou vhodné pro širokou škálu aplikací.
• Účinnost: Operace push a pop na zásobníku lze provádět v konstantním čase (O(1)) poskytující efektivní přístup k datům.
• Poslední dovnitř, první ven (LIFO): Zásobníky se řídí principem LIFO, který zajišťuje, že poslední prvek přidaný do zásobníku je prvním odstraněným prvkem. Toto chování je užitečné v mnoha scénářích, jako je volání funkcí a vyhodnocování výrazů.
• Omezené využití paměti: Zásobníky potřebují pouze ukládat prvky, které do nich byly vloženy, díky čemuž jsou paměťově efektivní ve srovnání s jinými datovými strukturami.

Nevýhody Stack Datová struktura :

• Omezený přístup: K prvkům v zásobníku lze přistupovat pouze shora, takže je obtížné načíst nebo upravit prvky uprostřed zásobníku.
• Možnost přetečení: Pokud je do zásobníku vloženo více prvků, než se do něj vejde, dojde k chybě přetečení, která má za následek ztrátu dat.
• Nevhodné pro náhodný přístup: Zásobník s neumožňují náhodný přístup k prvkům, takže jsou nevhodné pro aplikace, kde je třeba k prvkům přistupovat v určitém pořadí.
• Omezená kapacita: Zásobníky mají pevnou kapacitu, což může být omezení, pokud je počet prvků, které je třeba uložit, neznámý nebo vysoce variabilní.

Aplikace datové struktury zásobníku:

• Infix do Postfixu /Převod předpony
• Znovu vrátit zpět funkce na mnoha místech, jako jsou editory, photoshop.
• Funkce vpřed a vzad ve webových prohlížečích
• Ve správě paměti každý moderní počítač používá zásobník jako primární správu pro běžící účel. Každý program, který běží v počítačovém systému, má vlastní přidělení paměti.
• Stack také pomáhá při implementaci volání funkcí v počítačích. Poslední volaná funkce je vždy dokončena jako první.

Související články:

• Implementujte zásobník pomocí jednoduše propojeného seznamu
• Základní operace v datové struktuře zásobníku s implementacemi
• 50 hlavních problémů se strukturou dat zásobníku dotazovaných v rozhovorech SDE
• Aplikace, výhody a nevýhody Stack
  
• Zásobník pro konkurenční programování