Stack datu struktūra ir lineārā datu struktūra kas seko LIFO (Last In First Out) princips , tāpēc pēdējais ievietotais elements tiek parādīts pirmais. Šajā rakstā mēs apskatīsim visus Stack pamatus, Operations on Stack, tā ieviešanu, priekšrocības un trūkumus, kas palīdzēs atrisināt visas problēmas, pamatojoties uz Stack.

Satura rādītājs

• Kas ir steka datu struktūra?
• Stack datu struktūras pamatoperācijas
• isEmpty darbība steka datu struktūrā
• Stack datu struktūras ieviešana, izmantojot saistīto sarakstu
• Stack datu struktūras operāciju sarežģītības analīze
• Stack datu struktūras priekšrocības
• Stack datu struktūras trūkumi
• Stack datu struktūras pielietojumi

Kas ir steka datu struktūra?

Kaudze ir lineārā datu struktūra balstoties uz LIFO (Last In First Out) princips kurā jauna elementa ievietošana un esošā elementa noņemšana notiek tajā pašā galā, kas attēlots kā tops no kaudzes.

Lai ieviestu kaudzi, ir jāuztur rādītājs uz kaudzes augšdaļu , kas ir pēdējais ievietojamais elements, jo mēs varam piekļūt elementiem tikai kaudzes augšpusē.

Stack datu struktūras attēlojums:

Stack seko LIFO (Last In First Out) principam, tāpēc elements, kas tiek nospiests pēdējais, tiek parādīts pirmais.

Fiksēta izmēra kaudze : Kā norāda nosaukums, fiksēta izmēra kopai ir noteikts izmērs, un tā nevar dinamiski augt vai sarukt. Ja kaudze ir pilna un tai tiek mēģināts pievienot elementu, rodas pārpildes kļūda. Ja kaudze ir tukša un no tās tiek mēģināts noņemt elementu, rodas nepietiekamas plūsmas kļūda.

Dinamiskā izmēra kaudze : dinamiska izmēra kopa var dinamiski pieaugt vai sarukt. Kad kaudze ir pilna, tā automātiski palielina tā lielumu, lai pielāgotos jaunajam elementam, un, kad kaudze ir tukša, tā lielums samazinās. Šāda veida steka tiek ieviesta, izmantojot saistīto sarakstu, jo tas ļauj viegli mainīt kaudzes izmērus.

Pamatdarbības uz Stack Datu struktūra :

Lai veiktu manipulācijas kaudzē, mums tiek nodrošinātas noteiktas darbības.

mini rīkjosla Excel

• push () lai ievietotu elementu kaudzē
• pop () lai noņemtu elementu no kaudzes
• tops() Atgriež kaudzes augšējo elementu.
• ir tukšs() atgriež patiesu, ja steka ir tukša, pretējā gadījumā false.
• ir pilns() atgriež true, ja kaudze ir pilna, pretējā gadījumā false.

Push darbības algoritms:

• Pirms elementa stumšanas uz skursteni pārbaudām, vai kaudze ir pilns .
• Ja kaudze ir pilna (augšā == ietilpība-1) , tad Stack Overflows un mēs nevaram ievietot elementu kaudzē.
• Pretējā gadījumā mēs palielinām augšdaļas vērtību par 1 (augšā = augšā + 1) un jaunā vērtība tiek ievietota pie augstākā pozīcija .
• Elementus var iestumt kaudzē, līdz mēs sasniedzam jaudu no kaudzes.

Pop darbības algoritms:

• Pirms elementa izņemšanas no kaudzes mēs pārbaudām, vai steks ir tukšs .
• Ja kaudze ir tukša (augšējā == -1), tad Stack Underflows un mēs nevaram noņemt nevienu elementu no steka.
• Pretējā gadījumā mēs saglabājam vērtību augšpusē, samazinām augšdaļas vērtību par 1 (augšā = augšā - 1) un atgriezt saglabāto augstāko vērtību.

Algoritms augstākajai darbībai:

• Pirms augšējā elementa atgriešanas no kaudzes pārbaudām, vai kaudze nav tukša.
• Ja kaudze ir tukša (augšējā == -1), mēs vienkārši izdrukājam Kaudzīte ir tukša.
• Pretējā gadījumā mēs atgriežam elementu, kas saglabāts vietnē indekss = augšā .

Darbības isEmpty algoritms :

• Pārbaudiet vērtību tops kaudzē.
• Ja (augšā == -1) , tad kaudze ir tukšs tāpēc atgriezieties taisnība .
• Pretējā gadījumā kaudze nav tukša, tāpēc atgriezieties viltus .

Pilnas darbības algoritms:

linux faili

• Pārbaudiet vērtību tops kaudzē.
• Ja (augšā == ietilpība-1), tad kaudze ir pilns tāpēc atgriezieties taisnība .
• Pretējā gadījumā kaudze nav pilna, tāpēc atgriezieties viltus .

Stack ieviešana Datu struktūra :

Pamatdarbības, ko var veikt ar steku, ietver push, pop un peek. Ir divi veidi, kā ieviest steku -

• Izmantojot masīvu
• Saistītā saraksta izmantošana

Uz masīvu balstītā implementācijā push operācija tiek īstenota, palielinot augšējā elementa indeksu un saglabājot jauno elementu šajā indeksā. Pop operācija tiek īstenota, atgriežot vērtību, kas saglabāta augšējā indeksā, un pēc tam samazinot augšējā elementa indeksu.

Saistītā uz sarakstu balstītā implementācijā push operācija tiek īstenota, izveidojot jaunu mezglu ar jauno elementu un iestatot nākamo pašreizējā augšējā mezgla rādītāju uz jauno mezglu. Pop operācija tiek īstenota, iestatot nākamo pašreizējā augšējā mezgla rādītāju uz nākamo mezglu un atgriežot pašreizējā augšējā mezgla vērtību.

/* C++ programma pamata steka ieviešanai operācijas */ #iekļauts #iekļauts izmantojot nosaukumvieta std; #define MAX 1000 klasē Kaudze { starpt tops; publiski: starpt a[MAX]; // Maksimālais steka lielums Kaudze() { tops = -1; } bool spiediet(starpt x); starpt pop(); starpt palūrēt(); bool ir tukšs(); }; bool Stack::push(starpt x) { ja (tops >= (MAX - 1)) { cout << ' steck=' overflow'<='' span=''>; atgriezties viltus; } cits { a[++tops] = x; cout << x << ' iestumts kaudzē '; atgriezties taisnība; } } starpt Stack::pop() { ja (tops < 0) { cout << 'Stack Underflow'; atgriezties 0; } cits { starpt x = a[tops--]; atgriezties x; } } starpt Stack::peek() { ja (tops < 0) { cout << 'Steck is Empty'; atgriezties 0; } cits { starpt x = a[tops]; atgriezties x; } } bool Stack::isEmpty() { atgriezties (tops < 0); } // Draivera programma iepriekš minēto funkciju pārbaudei starpt galvenais() { klasē Kaudze s; s.spiediet(10); s.spiediet(divdesmit); s.spiediet(30); cout << s.pop() << Izlēca no kaudzes '; //izdrukājiet kaudzes augšējo elementu pēc uznirstīšanas cout << Augšējais elements ir: << s.palūrēt() << endl; //izdrukāt visus elementus kaudzē: cout <<'Elementi, kas atrodas kaudzē:'; kamēr(!s.ir tukšs()) { // drukāt augšējo elementu kaudzē cout << s.palūrēt() <<''; // noņemt augšējo elementu kaudzē s.pop(); } atgriezties 0; } //Kodu modificēja 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->jauda = jauda;  kaudze->augšējā = -1;  kaudze->masīvs = (int*)malloc(steka->kapacitāte * sizeof(int));  atpakaļ kaudze; } // Stack ir pilna, kad top ir vienāds ar pēdējo indeksu int isFull(struct Stack* steck) { return steck->top == kaudze->kapacitāte - 1; } // Stacks ir tukšs, ja top ir vienāds ar -1 int isEmpty(struct Stack* steck) { return steck->top == -1; } // Funkcija, lai pievienotu vienumu kaudzēm. Tas palielina top par 1 void push(struct Stack* kaudze, int item) { if (isFull(steck)) return;  kaudze->masīvs[++kaudze->augšdaļa] = vienums;  printf('%d iespiests kaudzē
', vienums); } // Funkcija, lai noņemtu vienumu no kaudzes. Tas samazinās augšā par 1 int pop(struct Stack* steck) { if (isEmpty(steck)) return INT_MIN;  return kaudze->masīvs[steck->top--]; } // Funkcija, lai atgrieztu augšējo daļu no steka, to nenoņemot int peek(struct Stack* steck) { if (isEmpty(steck)) return INT_MIN;  return kaudze->masīvs[steck->top]; } // Draivera programma, lai pārbaudītu iepriekš minētās funkcijas int main() { struct Stack* stack = createStack(100);  push(steck, 10);  push(steck, 20);  push(steck, 30);  printf('%d izlēca no steka
', pop(steka));  atgriezties 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('Steck Overflow');  return false;  } else { a[++augšā] = x;  System.out.println(x + ' iespiests kaudzē');  atgriezt patiesu;  } } int pop() { if (augšā< 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]);  } } } // Draivera koda klase 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() + ' Izlec no steka');  System.out.println('Augšējais elements ir :' + s.peek());  System.out.print('Steckā esošie elementi :');  s.print();  } } //Šo kodu ir modificējis 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('Steck Overflow');  return false;  } else { t+=1;  a[t] = x;    console.log(x + ' iespiests kaudzē ');  atgriezt patiesu;  } } 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--) { konsole.log(' ' + a[i]);  } } push(10);  push (20);  push (30);  console.log(pop() + ' Popped no steka');  console.log(' Augšējais elements ir :' + peek());  console.log(' Kaudzē esošie elementi: ');  drukāt (); // Šo kodu sniedz Rajput-Ji>

Izvade

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>

Masīva ieviešanas priekšrocības:

• Viegli īstenojams.
• Atmiņa tiek saglabāta, jo norādes nav iesaistītas.

Masīva ieviešanas trūkumi:

• Tas nav dinamisks, t.i., tas neaug un nesamazinās atkarībā no vajadzībām izpildlaikā. [Bet dinamiska izmēra masīvu gadījumā, piemēram, vektors C++, saraksts Python, ArrayList Java, skursteņi var augt un samazināties arī ar masīva ieviešanu].
• Kopējais kaudzes izmērs ir jānosaka iepriekš.

// C++ programma steka saistīto sarakstu ieviešanai #iekļauts izmantojot nosaukumvieta std; // Struktūra, kas attēlo kaudzi klasē StackNode { publiski: starpt datus; StackNode* Nākamais; }; StackNode* newNode(starpt datus) { StackNode* stackNode = jauns StackNode(); stackNode->datus = datus; stackNode->Nākamais = NULL; atgriezties stackNode; } starpt ir tukšs(StackNode* sakne) { atgriezties !sakne; } nederīgs spiediet(StackNode** sakne, starpt datus) { StackNode* stackNode = newNode(datus); stackNode->Nākamais = *sakne; *sakne = stackNode; cout << datus << ' pushed='' to='' kaudze<='' span=''> '; } starpt pop(StackNode** sakne) { ja (ir tukšs(*sakne)) atgriezties INT_MIN; StackNode* temp = *sakne; *sakne = (*sakne)->Nākamais; starpt izlēca = temp->datus; bezmaksas(temp); atgriezties izlēca; } starpt palūrēt(StackNode* sakne) { ja (ir tukšs(sakne)) atgriezties INT_MIN; atgriezties sakne->datus; } // Vadītāja kods starpt galvenais() { StackNode* sakne = NULL; spiediet(&sakne, 10); spiediet(&sakne, divdesmit); spiediet(&sakne, 30); cout << pop(&sakne) << ' izlēca no kaudzes '; cout << Augšējais elements ir << palūrēt(sakne) << endl; cout <<'Elementi, kas atrodas kaudzē:'; //izdrukāt visus elementus kaudzē: kamēr(!ir tukšs(sakne)) { // drukāt augšējo elementu kaudzē cout << palūrēt(sakne) <<''; // noņemt augšējo elementu kaudzē pop(&sakne); } atgriezties 0; } // Šis kods ir 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->dati = dati;  stackNode->next = NULL;  atgriezties stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** sakne, int dati) { struct StackNode* stackNode = newNode(data);  stackNode->next = *sakne;  *sakne = stackNode;  printf('%d iespiests kaudzē
', dati); } int pop(struct StackNode** sakne) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *sakne;  *sakne = (*sakne)->nākamais;  int popped = temp->dati;  brīvs(temp);  atgriešanās popped; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  atgriezt root->data; } int main() { struct StackNode* root = NULL;  push(&sakne, 10);  push(&sakne, 20);  push(&sakne, 30);  printf('%d izlēca no steka
', pop(&root));  printf('Augšējais elements ir %d
', peek(root));  atgriezties 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

>>  
  Izvade      Saistītā saraksta ieviešanas priekšrocības:    
 
Saistītā saraksta ieviešana steka var augt un sarukt atbilstoši vajadzībām izpildlaikā.
To izmanto daudzās virtuālajās mašīnās, piemēram, JVM.
    Saistītā saraksta ieviešanas trūkumi:    
 
Nepieciešama papildu atmiņa, jo ir iesaistītas norādes.
Nejauša piekļuve nav iespējama kaudzē.

Stack datu struktūras operāciju sarežģītības analīze:

Stack priekšrocības Datu struktūra :

• Vienkāršība: Stacki ir vienkārša un viegli saprotama datu struktūra, kas padara tos piemērotus plašam lietojumu klāstam.
• Efektivitāte: Push un pop darbības stekā var veikt nemainīgā laikā (O(1)) , nodrošinot efektīvu piekļuvi datiem.
• Pēdējais iekšā, pirmais ārā (LIFO): Stacks ievēro LIFO principu, nodrošinot, ka pēdējais stekam pievienotais elements ir pirmais noņemtais. Šī darbība ir noderīga daudzos scenārijos, piemēram, funkciju izsaukumos un izteiksmju novērtēšanā.
• Ierobežots atmiņas lietojums: Stackiem ir jāsaglabā tikai tie elementi, kas tajās ir ievietoti, padarot tos efektīvāku atmiņu salīdzinājumā ar citām datu struktūrām.

Stack trūkumi Datu struktūra :

• Ierobežota piekļuve: Kaudzītes elementiem var piekļūt tikai no augšas, tādējādi apgrūtinot elementu izgūšanu vai modificēšanu kaudzes vidū.
• Pārplūdes potenciāls: Ja stekā tiek nospiests vairāk elementu, nekā tajā var ietilpt, radīsies pārpildes kļūda, kā rezultātā tiks zaudēti dati.
• Nav piemērots nejaušai piekļuvei: Kaudze s neļauj nejauši piekļūt elementiem, padarot tos nepiemērotus lietojumprogrammām, kur elementiem ir jāpiekļūst noteiktā secībā.
• Ierobežota jauda: Stackiem ir noteikta ietilpība, kas var būt ierobežojums, ja nav zināms vai ļoti mainīgs saglabājamo elementu skaits.

Stack datu struktūras lietojumprogrammas:

• Infix uz Postfix /Prefiksa konvertēšana
• Atsaukt funkcijas daudzās vietās, piemēram, redaktoros, Photoshop.
• Priekšu un atpakaļ funkcijas tīmekļa pārlūkprogrammās
• Atmiņas pārvaldībā jebkurš moderns dators izmanto steku kā galveno pārvaldību darbības mērķiem. Katrai programmai, kas darbojas datorsistēmā, ir savs atmiņas sadalījums.
• Stack palīdz arī ieviest funkciju izsaukumu datoros. Pēdējā izsauktā funkcija vienmēr tiek pabeigta vispirms.

Saistītie raksti: