Stack duomenų struktūra yra linijinė duomenų struktūra tai seka LIFO (Last In First Out) principas , todėl paskutinis įterptas elementas bus pirmasis, kuris iššoks. Šiame straipsnyje apžvelgsime visus „Stack“ pagrindus, „Operations on Stack“, jos įgyvendinimą, privalumus, trūkumus, kurie padės išspręsti visas „Stack“ problemas.

Turinys

• Kas yra kamino duomenų struktūra?
• Pagrindinės dėklo duomenų struktūros operacijos
• isEmpty operacija kamino duomenų struktūroje
• Stack duomenų struktūros įgyvendinimas naudojant susietąjį sąrašą
• Operacijų su kamino duomenų struktūra sudėtingumo analizė
• Stack duomenų struktūros privalumai
• Stack duomenų struktūros trūkumai
• Stack duomenų struktūros taikymai

Kas yra kamino duomenų struktūra?

Stack yra linijinė duomenų struktūra remiantis LIFO (Last In First Out) principas kuriame naujas elementas įterpiamas ir esamas elementas pašalinamas tame pačiame gale, kaip ir viršuje iš kamino.

Norint įdiegti kaminą, būtina prižiūrėti žymeklį į krūvos viršų , kuris yra paskutinis įterpiamas elementas, nes elementus galime pasiekti tik kamino viršuje.

Stacko duomenų struktūros vaizdavimas:

Stack atitinka LIFO (Last In First Out) principą, todėl elementas, kuris stumiamas paskutinis, iškyla pirmas.

Fiksuoto dydžio krūva : Kaip rodo pavadinimas, fiksuoto dydžio krūva turi fiksuotą dydį ir negali dinamiškai augti ar mažėti. Jei krūva pilna ir į ją bandoma pridėti elementą, įvyksta perpildymo klaida. Jei krūva tuščia ir bandoma iš jos pašalinti elementą, atsiranda perpildymo klaida.

Dinaminio dydžio krūva : Dinaminio dydžio krūva gali dinamiškai didėti arba mažėti. Kai krūva pilna, ji automatiškai padidina jos dydį, kad tilptų naujas elementas, o kai krūva tuščia, sumažina jos dydį. Šio tipo dėklas įgyvendinamas naudojant susietą sąrašą, nes tai leidžia lengvai pakeisti krūvos dydį.

Pagrindinės „Stack“ operacijos Duomenų struktūra :

Norint atlikti manipuliacijas krūvoje, mums yra numatytos tam tikros operacijos.

java scan.nextstring

• stumti () įterpti elementą į krūvą
• pop () pašalinti elementą iš kamino
• viršuje () Grąžina viršutinį krūvos elementą.
• Yra tuščias() grąžina true, jei kaminas tuščias, kitaip false.
• pilnas() grąžina true, jei krūva pilna, kitaip false.

Push operacijos algoritmas:

• Prieš stumdami elementą į krūvą, patikriname, ar rietuvė yra pilnas .
• Jei krūva pilna (viršuje == talpa-1) , tada Stack Overflows ir negalime įterpti elemento į krūvą.
• Kitu atveju viršutinės reikšmės vertę padidiname 1 (viršuje = viršuje + 1) ir nauja reikšmė įterpiama ties aukščiausia pozicija .
• Elementus galima stumti į krūvą, kol pasieksime talpa iš kamino.

Pop operacijos algoritmas:

• Prieš iškeldami elementą iš kamino, patikriname, ar jis yra tuščia .
• Jei krūva tuščia (viršus == -1), tada Stack Underflows ir negalime pašalinti iš kamino jokio elemento.
• Kitu atveju išsaugome vertę viršuje, sumažiname viršutinę reikšmę 1 (viršuje = viršuje – 1) ir grąžinti išsaugotą didžiausią vertę.

Aukščiausios operacijos algoritmas:

• Prieš grąžindami viršutinį elementą iš kamino, patikriname, ar rietuvė tuščia.
• Jei krūva tuščia (viršuje == -1), tiesiog spausdiname Stack is empty.
• Kitu atveju grąžiname elementą, saugomą adresu indeksas = viršuje .

„isEmpty“ operacijos algoritmas :

• Patikrinkite vertę viršuje krūvoje.
• Jeigu (viršuje == -1) , tada kamino yra tuščia taigi grįžk tiesa .
• Kitu atveju krūva nėra tuščia, todėl grįžkite klaidinga .

„IsFull“ veikimo algoritmas:

• Patikrinkite vertę viršuje krūvoje.
• Jeigu (viršuje == talpa-1), tada kamino yra pilnas taigi grįžk tiesa .
• Priešingu atveju krūva nėra pilna, todėl grąžinkite klaidinga .

Stack įgyvendinimas Duomenų struktūra :

Pagrindinės operacijos, kurias galima atlikti su krūva, yra stūmimas, iššokimas ir žvilgsnis. Yra du būdai, kaip įdiegti krūvą -

• Naudojant masyvą
• Susieto sąrašo naudojimas

Masyvu pagrįsto diegimo atveju stūmimo operacija įgyvendinama padidinant viršutinio elemento indeksą ir išsaugant naują elementą tame indekse. Pop operacija įgyvendinama grąžinant vertę, saugomą viršutiniame indekse, o tada sumažinant viršutinio elemento indeksą.

Naudojant susietą sąrašą pagrįstą įgyvendinimą, stūmimo operacija įgyvendinama sukuriant naują mazgą su nauju elementu ir nustatant kitą dabartinio viršutinio mazgo žymeklį į naują mazgą. Pop operacija įgyvendinama nustatant kitą dabartinio viršutinio mazgo rodyklę į kitą mazgą ir grąžinant dabartinio viršutinio mazgo reikšmę.

/* C++ programa pagrindiniam kaminui įdiegti operacijos */ #įtraukti #įtraukti naudojant vardų erdvė std; #define MAX 1000 klasė Stack { tarpt viršuje; viešas: tarpt a[MAX]; // Didžiausias krūvos dydis Stack() { viršuje = -1; } bool stumti(tarpt x); tarpt pop(); tarpt žvilgtelėti(); bool Yra tuščias(); }; bool Stack::stumti(tarpt x) { jeigu (viršuje >= (MAX - 1)) { cout << ' stack = ' perpildymas'<='' span=''>; grąžinti klaidinga; } Kitas { a[++viršuje] = x; cout << x << “ sustumtas į krūvą '; grąžinti tiesa; } } tarpt Stack::pop() { jeigu (viršuje < 0) { cout << „Stack Underflow“; grąžinti 0; } Kitas { tarpt x = a[viršuje--]; grąžinti x; } } tarpt Stack::peek() { jeigu (viršuje < 0) { cout << „Stekas tuščias“; grąžinti 0; } Kitas { tarpt x = a[viršuje]; grąžinti x; } } bool Stack::isEmpty() { grąžinti (viršuje < 0); } // Tvarkyklės programa aukščiau pateiktoms funkcijoms išbandyti tarpt pagrindinis() { klasė Stack s; s.stumti(10); s.stumti(dvidešimt); s.stumti(30); cout << s.pop() << “ Iššoko iš krūvos '; //atspausdinti viršutinį kamino elementą po iššokimo cout << Viršutinis elementas yra: << s.žvilgtelėti() << endl; //atspausdinti visus krūvos elementus: cout <<„Steckelyje esantys elementai:“; kol(!s.Yra tuščias()) { // spausdinti viršutinį elementą krūvoje cout << s.žvilgtelėti() <<''; // pašalinti viršutinį elementą iš krūvos s.pop(); } grąžinti 0; } //Kodą modifikavo 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->talpa = talpa;  krūva->viršus = -1;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  grąžinti kaminą; } // Krūvas pilnas, kai viršus lygus paskutiniam indeksui int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Krūvas tuščias, kai viršus lygus -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Funkcija pridėti elementą į krūvą. Jis padidina viršuje 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stack->masyvas[++stack->top] = elementas;  printf('%d nustumtas į krūvą
', elementas); } // Funkcija pašalinti elementą iš krūvos. Jis sumažinamas iš viršaus 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->masyvas[stack->top--]; } // Funkcija grąžinti viršų iš krūvos nepašalinant int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->masyvas[stekas->viršus]; } // Tvarkyklės programa aukščiau pateiktoms funkcijoms išbandyti int main() { struct Stack* stack = createStack(100);  stumti(stack, 10);  stumti(krūva, 20);  stumti(krūva, 30);  printf('%d iššoko iš dėklo
', pop(stack));  grąžinti 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');  return false;  } else { a[++viršuje] = x;  System.out.println(x + ' įstumtas į krūvą');  grįžti tiesa;  } } int pop() { if (viršuje< 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]);  } } } // Tvarkyklės kodas class 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() + ' Iškelta iš kamino');  System.out.println('Viršutinis elementas yra :' + s.peek());  System.out.print('Stecke esantys elementai :');  s.print();  } } //Šį kodą modifikavo 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');  return false;  } else { t+=1;  a[t] = x;    console.log(x + ' įstumtas į krūvą ');  grįžti tiesa;  } } 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]);  } } stumti(10);  stumti(20);  stumti(30);  console.log(pop() + ' Iškelta iš kamino');  console.log(' Viršutinis elementas yra :' + peek());  console.log(' Elementai, esantys krūvoje : ');  spausdinti (); // Šį kodą sukūrė Rajput-Ji>>  
  Išvestis      Masyvo diegimo privalumai:    
 
Lengva įgyvendinti.
Atmintis išsaugoma, nes nenaudojamos rodyklės.
    Masyvo diegimo trūkumai:    
 
Jis nėra dinamiškas, ty neauga ir nesitraukia priklausomai nuo poreikių vykdymo metu. [Tačiau naudojant dinaminio dydžio masyvus, tokius kaip vektorius C++, sąrašas Python, ArrayList Java, krūvos taip pat gali augti ir mažėti diegiant masyvą].
Bendras krūvos dydis turi būti nustatytas iš anksto.

// C++ programa, skirta kamino susieto sąrašo įgyvendinimui #įtraukti naudojant vardų erdvė std; // Struktūra, vaizduojanti krūvą klasė StackNode { viešas: tarpt duomenis; StackNode* Kitas; }; StackNode* naujas mazgas(tarpt duomenis) { StackNode* stackNode = naujas StackNode(); stackNode->duomenis = duomenis; stackNode->Kitas = NULL; grąžinti stackNode; } tarpt Yra tuščias(StackNode* šaknis) { grąžinti !šaknis; } tuštuma stumti(StackNode** šaknis, tarpt duomenis) { StackNode* stackNode = naujas mazgas(duomenis); stackNode->Kitas = *šaknis; *šaknis = stackNode; cout << duomenis << ' pushed='' to='' krūva<='' span=''> '; } tarpt pop(StackNode** šaknis) { jeigu (Yra tuščias(*šaknis)) grąžinti INT_MIN; StackNode* temp = *šaknis; *šaknis = (*šaknis)->Kitas; tarpt iššoko = temp->duomenis; Laisvas(temp); grąžinti iššoko; } tarpt žvilgtelėti(StackNode* šaknis) { jeigu (Yra tuščias(šaknis)) grąžinti INT_MIN; grąžinti šaknis->duomenis; } // Vairuotojo kodas tarpt pagrindinis() { StackNode* šaknis = NULL; stumti(&šaknis, 10); stumti(&šaknis, dvidešimt); stumti(&šaknis, 30); cout << pop(&šaknis) << “ iššoko iš kamino '; cout << „Viršutinis elementas yra“ << žvilgtelėti(šaknis) << endl; cout <<„Steckelyje esantys elementai:“; //atspausdinti visus krūvos elementus: kol(!Yra tuščias(šaknis)) { // spausdinti viršutinį elementą krūvoje cout << žvilgtelėti(šaknis) <<''; // pašalinti viršutinį elementą iš krūvos pop(&šaknis); } grąžinti 0; } // Šį kodą pateikė 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->duomenys = duomenys;  stackNode->next = NULL;  return stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newMazgas(duomenys);  stackNode->next = *root;  *root = stackNode;  printf('%d nustumtas į krūvą
', duomenys); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *root;  *root = (*root)->kitas;  int popped = temp->duomenys;  laisvas(temp);  grįžti iššoko; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  grąžinti šaknį->duomenis; } int main() { struct StackNode* root = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d iškelta iš kamino
', pop(&root));  printf('Viršutinis elementas yra %d
', peek(root));  grąžinti 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

>>  
  Išvestis      Susieto sąrašo diegimo privalumai:    
 
Susieto sąrašo dėklo įgyvendinimas gali augti ir mažėti, atsižvelgiant į poreikius vykdymo metu.
Jis naudojamas daugelyje virtualių mašinų, tokių kaip JVM.
    Susieto sąrašo diegimo trūkumai:    
 
Reikia papildomos atminties dėl rodyklių.
Atsitiktinė prieiga negalima dėkle.

Stack duomenų struktūros operacijų sudėtingumo analizė:

Stack privalumai Duomenų struktūra :

• Paprastumas: Stackai yra paprasta ir lengvai suprantama duomenų struktūra, todėl tinka įvairioms programoms.
• Efektyvumas: Push ir pop operacijas ant krūvos galima atlikti pastoviu laiku (O(1)) , suteikdamas veiksmingą prieigą prie duomenų.
• Paskutinis atvykęs, pirmasis išėjęs (LIFO): Stackai vadovaujasi LIFO principu, užtikrinant, kad paskutinis elementas, įtrauktas į krūvą, būtų pirmasis pašalintas. Šis elgesys yra naudingas daugelyje scenarijų, pvz., funkcijų iškvietimų ir išraiškų įvertinimo.
• Ribotas atminties naudojimas: Stackuose tereikia saugoti elementus, kurie buvo įstumti į juos, todėl jie taupo atmintį, palyginti su kitomis duomenų struktūromis.

Stack trūkumai Duomenų struktūra :

• Ribotas priėjimas: Prie krūvos elementų galima pasiekti tik iš viršaus, todėl sunku nuskaityti ar modifikuoti elementus krūvos viduryje.
• Perpildymo galimybė: Jei į krūvą įstumiama daugiau elementų, nei telpa, įvyks perpildymo klaida, dėl kurios bus prarasti duomenys.
• Netinka atsitiktinei prieigai: Stack s neleidžia atsitiktinės prieigos prie elementų, todėl jie netinkami programoms, kuriose elementus reikia pasiekti tam tikra tvarka.
• Ribotas pajėgumas: Stackų talpa yra fiksuota, o tai gali būti apribojimas, jei elementų, kuriuos reikia saugoti, skaičius nežinomas arba labai kinta.

Stack duomenų struktūros taikymai:

• Infix prie Postfix /Prefikso konvertavimas
• Anuliuoti funkcijas daugelyje vietų, pvz., redaktoriuose, „Photoshop“.
• Pirmyn ir atgal funkcijos žiniatinklio naršyklėse
• Atminties valdyme bet kuris modernus kompiuteris naudoja dėklą kaip pagrindinį valdymo tikslą. Kiekviena programa, kuri veikia kompiuterinėje sistemoje, turi savo atminties paskirstymą.
• Stack taip pat padeda įdiegti funkcijų iškvietimą kompiuteriuose. Paskutinė iškviesta funkcija visada užbaigiama pirmiausia.

Susiję straipsniai: