Struktura podatkov sklada je linearna struktura podatkov ki sledi LIFO (Last In First Out) načelo , tako da zadnji vstavljeni element prvi izstopi. V tem članku bomo obravnavali vse osnove Stacka, operacije na Stacku, njegovo implementacijo, prednosti in slabosti, kar vam bo pomagalo rešiti vse težave, ki temeljijo na Stacku.

Kazalo

• Kaj je Stack Data Structure?
• Osnovne operacije nad podatkovno strukturo sklada
• Operacija isEmpty v podatkovni strukturi sklada
• Implementacija podatkovne strukture sklada z uporabo povezanega seznama
• Analiza kompleksnosti operacij na podatkovni strukturi sklada
• Prednosti strukture podatkov sklada
• Slabosti strukture podatkov sklada
• Uporaba podatkovne strukture sklada

Kaj je Stack Data Structure?

Stack je linearna struktura podatkov temelji na Načelo LIFO (Last In First Out). v katerem se vstavljanje novega elementa in odstranjevanje obstoječega elementa zgodi na istem koncu, ki je predstavljen kot vrh sklada.

Za izvedbo sklada je potrebno vzdrževati kazalec na vrh sklada , ki je zadnji element, ki ga je treba vstaviti, ker do elementov lahko dostopamo samo na vrhu sklada.

Predstavitev strukture podatkov sklada:

Sklad sledi načelu LIFO (zadnji vstopi, prvi ven), tako da se element, ki je zadnji potisnjen, izloči prvi.

Stack fiksne velikosti : Kot že ime pove, ima sklad s fiksno velikostjo fiksno velikost in se ne more dinamično povečevati ali krčiti. Če je sklad poln in se vanj poskuša dodati element, pride do napake prelivanja. Če je sklad prazen in se iz njega poskusi odstraniti element, pride do napake pretoka.

Dinamični sklad velikosti : Sklad dinamične velikosti se lahko dinamično poveča ali skrči. Ko je sklad poln, samodejno poveča svojo velikost, da sprejme nov element, in ko je sklad prazen, zmanjša njegovo velikost. Ta vrsta sklada je implementirana z uporabo povezanega seznama, saj omogoča enostavno spreminjanje velikosti sklada.

Osnovne operacije na skladu Struktura podatkov :

Da bi izvajali manipulacije v skladu, so nam na voljo določene operacije.

ukaz v vozlišču js

• potisni() da vstavite element v sklad
• pop() za odstranitev elementa iz sklada
• vrh() Vrne zgornji element sklada.
• je prazno() vrne true, če je sklad prazen, drugače pa false.
• je poln() vrne true, če je sklad poln else false.

Algoritem za potisno operacijo:

• Preden potisnemo element v sklad, preverimo, ali je sklad poln .
• Če je sklad poln (zgoraj == zmogljivost-1) , potem Stack Overflows in elementa ne moremo vstaviti v sklad.
• V nasprotnem primeru povečamo vrednost vrha za 1 (vrh = vrh + 1) in nova vrednost je vstavljena pri najvišji položaj .
• Elemente lahko potiskamo v sklad, dokler ne dosežemo zmogljivost sklada.

Algoritem za pop operacijo:

• Preden izločimo element iz sklada, preverimo, ali je sklad prazno .
• Če je sklad prazen (vrh == -1), potem Stack Underflows in ne moremo odstraniti nobenega elementa iz sklada.
• V nasprotnem primeru shranimo vrednost na vrhu, zmanjšamo vrednost na vrhu za 1 (vrh = vrh – 1) in vrne shranjeno najvišjo vrednost.

Algoritem za vrhunsko delovanje:

• Pred vrnitvijo zgornjega elementa iz sklada preverimo, če je sklad prazen.
• Če je sklad prazen (zgornji == -1), preprosto natisnemo Sklad je prazen.
• V nasprotnem primeru vrnemo element, shranjen v indeks = vrh .

Algoritem za operacijo isEmpty :

• Preverite vrednost vrh v kupu.
• če (zgoraj == -1) , potem je sklad prazno torej vrnitev prav .
• V nasprotnem primeru sklad ni prazen, zato se vrnite lažno .

Algoritem za delovanje isFull:

• Preverite vrednost vrh v kupu.
• če (zgoraj == zmogljivost-1), potem je sklad poln torej vrnitev prav .
• V nasprotnem primeru sklad ni poln, zato se vrnite lažno .

Implementacija sklada Struktura podatkov :

Osnovne operacije, ki jih je mogoče izvesti na skladu, vključujejo push, pop in peek. Obstajata dva načina za implementacijo sklada –

• Uporaba Array
• Uporaba povezanega seznama

V implementaciji, ki temelji na matriki, se operacija potiska izvaja s povečanjem indeksa zgornjega elementa in shranjevanjem novega elementa na ta indeks. Operacija pop se izvede tako, da vrne vrednost, shranjeno na zgornjem indeksu, in nato zmanjša indeks zgornjega elementa.

V implementaciji, ki temelji na povezanem seznamu, se operacija potiska izvaja z ustvarjanjem novega vozlišča z novim elementom in nastavitvijo naslednjega kazalca trenutnega zgornjega vozlišča na novo vozlišče. Operacija pop se izvaja tako, da se naslednji kazalec trenutnega zgornjega vozlišča nastavi na naslednje vozlišče in vrne vrednost trenutnega zgornjega vozlišča.

/* Program C++ za implementacijo osnovnega sklada operacije */ #vključi #vključi uporabo imenski prostor std; #define MAX 1000 razred Stack { int vrh; javnosti: int a[MAKS]; // Največja velikost sklada Stack() { vrh = -1; } bool potiskati(int x); int pop(); int pokukati(); bool je prazno(); }; bool Stack::push(int x) { če (vrh >= (MAKS - 1)) { cout << 'stack=''overflow'<='' span=''>; vrnitev lažno; } drugače { a[++vrh] = x; cout << x << ' potisnjen v sklad '; vrnitev prav; } } int Stack::pop() { če (vrh < 0) { cout << 'Stack Underflow'; vrnitev 0; } drugače { int x = a[vrh--]; vrnitev x; } } int Stack::peek() { če (vrh < 0) { cout << 'Sklad je prazen'; vrnitev 0; } drugače { int x = a[vrh]; vrnitev x; } } bool Stack::isEmpty() { vrnitev (vrh < 0); } // Program gonilnika za testiranje zgornjih funkcij int glavni() { razred Stack s; s.potiskati(10); s.potiskati(dvajset); s.potiskati(30); cout << s.pop() << ' Izstreljen iz sklada '; //natisni zgornji element sklada po pojavu cout << 'Zgornji element je:' << s.pokukati() << konec; //natisni vse elemente v skladu: cout <<'Elementi v skladu:'; medtem(!s.je prazno()) { // natisni zgornji element v skladu cout << s.pokukati() <<' '; // odstrani zgornji element v skladu s.pop(); } vrnitev 0; } //Kodo je spremenil 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->zmogljivost = zmogljivost;  sklad->vrh = -1;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  povratni sklad; } // Sklad je poln, ko je top enak zadnjemu indeksu int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Sklad je prazen, ko je top enak -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Funkcija za dodajanje elementa v sklad. Poveča vrh za 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stack->array[++stack->top] = element;  printf('%d potisnjen v sklad
', element); } // Funkcija za odstranitev elementa iz sklada. Zmanjša vrh za 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  vrni sklad->matrika[sklad->vrh--]; } // Funkcija za vrnitev vrha iz sklada brez njegove odstranitve int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  vrni sklad->niz[sklad->vrh]; } // Program gonilnika za testiranje zgornjih funkcij int main() { struct Stack* stack = createStack(100);  potisni (sklad, 10);  potisni (sklad, 20);  potisni (sklad, 30);  printf('%d izstopil iz sklada
', pop(sklad));  vrni 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('Stack Overflow');  vrni false;  } else { a[++top] = x;  System.out.println(x + ' potisnjeno v sklad');  vrni resnico;  } } 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]);  } } } // Razred kode gonilnika 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() + ' Izstreljeno iz sklada ');  System.out.println('Zgornji element je :' + s.peek());  System.out.print('Elementi v skladu:');  s.print();  } } //To kodo je spremenil 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('Stack Overflow');  vrni false;  } else { t+=1;  a[t] = x;    console.log(x + ' potisnjeno v sklad ');  vrni resnico;  } } funkcija 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);  potisni(20);  potisni (30);  console.log(pop() + ' Izstreljeno iz sklada');  console.log(' Zgornji element je :' + peek());  console.log(' Elementi v skladu: ');  natisni(); // To kodo je prispeval Rajput-Ji>

Izhod

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>

Prednosti implementacije polja:

• Enostaven za izvedbo.
• Pomnilnik je shranjen, saj kazalci niso vključeni.

Slabosti implementacije polja:

• Ni dinamičen, tj. ne raste in se krči glede na potrebe med izvajanjem. [Toda v primeru matrik z dinamično velikostjo, kot je vektor v C++, seznam v Pythonu, ArrayList v Javi, lahko skladi rastejo in krčijo tudi z implementacijo matrike].
• Celotno velikost sklada je treba določiti vnaprej.

// Program C++ za implementacijo sklada povezanega seznama #vključi uporabo imenski prostor std; // Struktura za predstavitev sklada razred StackNode { javnosti: int podatke; StackNode* Naslednji; }; StackNode* novovozlišče(int podatke) { StackNode* stackNode = novo StackNode(); stackNode->podatke = podatke; stackNode->Naslednji = NIČ; vrnitev stackNode; } int je prazno(StackNode* korenina) { vrnitev !korenina; } praznina potiskati(StackNode** korenina, int podatke) { StackNode* stackNode = novovozlišče(podatke); stackNode->Naslednji = *korenina; *korenina = stackNode; cout << podatke << ' pushed='' to='' sklad<='' span=''> '; } int pop(StackNode** korenina) { če (je prazno(*korenina)) vrnitev INT_MIN; StackNode* temp = *korenina; *korenina = (*korenina)->Naslednji; int počil = temp->podatke; prost(temp); vrnitev počil; } int pokukati(StackNode* korenina) { če (je prazno(korenina)) vrnitev INT_MIN; vrnitev korenina->podatke; } // Koda voznika int glavni() { StackNode* korenina = NIČ; potiskati(&korenina, 10); potiskati(&korenina, dvajset); potiskati(&korenina, 30); cout << pop(&korenina) << ' izskočil iz sklada '; cout << 'Zgornji element je' << pokukati(korenina) << konec; cout <<'Elementi v skladu:'; //natisni vse elemente v skladu: medtem(!je prazno(korenina)) { // natisni zgornji element v skladu cout << pokukati(korenina) <<' '; // odstrani zgornji element v skladu pop(&korenina); } vrnitev 0; } // To kodo je prispeval 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->podatki = podatki;  stackNode->next = NULL;  vrni 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 potisnjen v sklad
', podatki); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *root;  *root = (*root)->next;  int popped = temp->data;  prosto (temp);  vrnitev izstrelila; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  vrni koren->podatke; } int main() { struct StackNode* root = NULL;  potisni(&root, 10);  potisni(&root, 20);  potisni(&root, 30);  printf('%d izstopil iz sklada
', pop(&root));  printf('Zgornji element je %d
', peek(root));  vrni 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

>

Izhod

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>

Prednosti implementacije povezanega seznama:

osnove selena

• Implementacija sklada povezanega seznama se lahko med izvajanjem povečuje in krči glede na potrebe.
• Uporablja se v številnih virtualnih strojih, kot je JVM.

Slabosti izvedbe povezanega seznama:

• Zahteva dodaten pomnilnik zaradi vpletenosti kazalcev.
• Naključni dostop v skladu ni mogoč.

Analiza kompleksnosti operacij na podatkovni strukturi sklada:

Prednosti Stacka Struktura podatkov :

• Enostavnost: Skladi so preprosta in lahko razumljiva podatkovna struktura, zaradi česar so primerni za široko paleto aplikacij.
• Učinkovitost: Operacije potiskanja in izpiranja na skladu se lahko izvajajo v konstantnem času (O(1)) , ki zagotavlja učinkovit dostop do podatkov.
• Zadnji vstop, prvi ven (LIFO): Skladi sledijo načelu LIFO, ki zagotavlja, da je zadnji element, dodan v sklad, prvi odstranjen. To vedenje je uporabno v številnih scenarijih, kot so klici funkcij in vrednotenje izrazov.
• Omejena poraba pomnilnika: Skladi morajo shraniti samo elemente, ki so bili potisnjeni vanje, zaradi česar so pomnilniško učinkoviti v primerjavi z drugimi podatkovnimi strukturami.

Slabosti Stacka Struktura podatkov :

• Omejen dostop: Do elementov v skladu je mogoče dostopati le z vrha, kar otežuje pridobivanje ali spreminjanje elementov na sredini sklada.
• Možnost prelivanja: Če je na sklad potisnenih več elementov, kot jih lahko sprejme, bo prišlo do napake prelivanja, kar bo povzročilo izgubo podatkov.
• Ni primerno za naključni dostop: Stack ne omogočajo naključnega dostopa do elementov, zaradi česar so neprimerni za aplikacije, kjer je treba do elementov dostopati v določenem vrstnem redu.
• Omejena zmogljivost: Skladi imajo fiksno zmogljivost, kar je lahko omejitev, če je število elementov, ki jih je treba shraniti, neznano ali zelo spremenljivo.

Uporaba podatkovne strukture sklada:

• Infix v Postfix /Pretvorba predpone
• Funkcije uveljavitve razveljavitve na številnih mestih, kot so urejevalniki, photoshop.
• Funkcije za naprej in nazaj v spletnih brskalnikih
• Pri upravljanju pomnilnika vsak sodoben računalnik uporablja sklad kot primarno upravljanje za tekoči namen. Vsak program, ki se izvaja v računalniškem sistemu, ima svoje dodelitve pomnilnika.
• Stack pomaga tudi pri izvajanju funkcijskega klica v računalnikih. Nazadnje klicana funkcija se vedno najprej zaključi.

Povezani članki:

• Izvedite sklad z uporabo enojno povezanega seznama
• Osnovne operacije v podatkovni strukturi sklada z implementacijami
• 50 najpogostejših težav pri strukturi podatkov sklada v intervjujih SDE
• Aplikacije, prednosti in slabosti Stacka
  
• Stack za konkurenčno programiranje