Pinotietorakenne on lineaarinen tietorakenne siitä seuraa LIFO (Last In First Out) -periaate , joten viimeksi lisätty elementti ponnahtaa esiin ensimmäisenä. Tässä artikkelissa käsittelemme kaikki pinon perusteet, Operations on Stack, sen toteutuksen, edut ja haitat, jotka auttavat sinua ratkaisemaan kaikki Stackiin perustuvat ongelmat.

Sisällysluettelo

• Mikä on pinotietorakenne?
• Pinotietorakenteen perustoiminnot
• isEmpty-toiminto pinotietorakenteessa
• Pinotietorakenteen käyttöönotto linkitettyjen luetteloiden avulla
• Pinotietorakenteen toimintojen monimutkaisuusanalyysi
• Pinotietorakenteen edut
• Pinotietorakenteen haitat
• Pinotietorakenteen sovellukset

Mikä on pinotietorakenne?

Pino on lineaarinen tietorakenne perustuen LIFO (Last In First Out) -periaate jossa uuden elementin lisääminen ja olemassa olevan elementin poistaminen tapahtuu samassa päässä kuin alkuun pinosta.

Pinon toteuttamiseksi on ylläpidettävä osoitin pinon yläosaan , joka on viimeinen lisättävä elementti, koska voimme käyttää elementtejä vain pinon yläosassa.

Pinotietorakenteen esitys:

Pino noudattaa LIFO-periaatetta (Last In First Out), joten viimeisenä työnnetty elementti ponnahtaa ensimmäisenä.

Kiinteän kokoinen pino : Kuten nimestä voi päätellä, kiinteän kokoisella pinolla on kiinteä koko, eikä se voi kasvaa tai kutistua dynaamisesti. Jos pino on täynnä ja siihen yritetään lisätä elementti, tapahtuu ylivuotovirhe. Jos pino on tyhjä ja siitä yritetään poistaa elementti, tapahtuu alivuotovirhe.

Dynaamisen kokoinen pino : Dynaamisen kokoinen pino voi kasvaa tai kutistua dynaamisesti. Kun pino on täynnä, se lisää automaattisesti kokoaan uuden elementin mukaiseksi, ja kun pino on tyhjä, se pienentää sen kokoa. Tämän tyyppinen pino toteutetaan linkitetyn luettelon avulla, koska se mahdollistaa pinon helpon koon muuttamisen.

Stackin perustoiminnot Tietorakenne :

Jotta pinossa voidaan tehdä manipulaatioita, meille tarjotaan tiettyjä toimintoja.

distributiivinen laki Boolen algebra

• työntää() lisätäksesi elementin pinoon
• pop() poistaaksesi elementin pinosta
• top() Palauttaa pinon ylimmän elementin.
• on tyhjä() palauttaa tosi, jos pino on tyhjä, muuten epätosi.
• on täynnä() palauttaa tosi, jos pino on täynnä, muuten epätosi.

Push-toiminnan algoritmi:

• Ennen kuin työnnät elementin pinoon, tarkistamme, onko pino koko .
• Jos pino on täynnä (ylä == kapasiteetti-1) , sitten Pinon ylivuoto emmekä voi lisätä elementtiä pinoon.
• Muussa tapauksessa lisäämme topin arvoa yhdellä (ylä = ylä + 1) ja uusi arvo lisätään kohtaan ylin asema .
• Elementit voidaan työntää pinoon, kunnes saavutamme kapasiteettia pinosta.

Pop-toiminnan algoritmi:

• Ennen kuin nostat elementin pinosta, tarkistamme, onko pino tyhjä .
• Jos pino on tyhjä (ylä == -1), niin Pinoa alivirtaukset emmekä voi poistaa mitään elementtiä pinosta.
• Muussa tapauksessa tallennamme arvon alkuun, vähennämme yläosan arvoa yhdellä (ylä = ylä - 1) ja palauttaa tallennetun yläarvon.

Algoritmi huipputoiminnolle:

• Ennen kuin palautamme yläelementin pinosta, tarkistamme, onko pino tyhjä.
• Jos pino on tyhjä (ylä == -1), tulostetaan yksinkertaisesti Pino on tyhjä.
• Muussa tapauksessa palautamme osoitteeseen tallennetun elementin indeksi = alkuun .

Algoritmi isEmpty-operaatiolle :

• Tarkista arvo alkuun pinossa.
• Jos (ylä == -1) , niin pino on tyhjä niin palaa totta .
• Muuten pino ei ole tyhjä, joten palauta väärä .

IsFull-toiminnan algoritmi:

• Tarkista arvo alkuun pinossa.
• Jos (ylä == kapasiteetti-1), sitten pino on koko niin palaa totta .
• Muuten pino ei ole täynnä, joten palauta väärä .

Stackin käyttöönotto Tietorakenne :

Pinolle suoritettavia perustoimintoja ovat push, pop ja peek. Pinon toteuttamiseen on kaksi tapaa -

• Arrayn käyttäminen
• Linkitetyn luettelon käyttäminen

Taulukkopohjaisessa toteutuksessa push-toiminto toteutetaan suurentamalla ylimmän elementin indeksiä ja tallentamalla uusi elementti kyseiseen indeksiin. Pop-operaatio toteutetaan palauttamalla yläindeksiin tallennettu arvo ja pienentämällä sitten ylimmän elementin indeksiä.

Linkitetyssä listapohjaisessa toteutuksessa push-toiminto toteutetaan luomalla uusi solmu uudella elementillä ja asettamalla nykyisen ylimmän solmun seuraava osoitin uuteen solmuun. Pop-operaatio toteutetaan asettamalla nykyisen huippusolmun seuraava osoitin seuraavaan solmuun ja palauttamalla nykyisen yläsolmun arvon.

/* C++-ohjelma peruspinon toteuttamiseen toiminta */ #sisältää #sisältää käyttämällä nimiavaruus std; #define MAX 1000 luokkaa Pino { int alkuun; julkinen: int a[MAX]; // Pinon enimmäiskoko Pino() { alkuun = -1; } bool työntää(int x); int pop(); int kurkistaa(); bool on tyhjä(); }; bool Pino::push(int x) { jos (alkuun >= (MAX - 1)) { cout << 'pino='ylivuo'<='' span=''>; palata väärä; } muu { a[++alkuun] = x; cout << x << ' työnnetty pinoon '; palata totta; } } int Pino::pop() { jos (alkuun < 0) { cout << 'Stack Underflow'; palata 0; } muu { int x = a[alkuun--]; palata x; } } int Pino::peek() { jos (alkuun < 0) { cout << 'Pino on tyhjä'; palata 0; } muu { int x = a[alkuun]; palata x; } } bool Pino::isTyhjä() { palata (alkuun < 0); } // Ohjainohjelma yllä olevien toimintojen testaamiseksi int pää() { luokkaa Pino s; s.työntää(10); s.työntää(kaksikymmentä); s.työntää(30); cout << s.pop() << ' Pomppasi pinosta '; //tulostaa pinon yläosan poksauksen jälkeen cout << 'Ylin elementti on:' << s.kurkistaa() << endl; //tulosta kaikki pinon elementit: cout <<'Pinossa olevat elementit:'; sillä aikaa(!s.on tyhjä()) { // tulosta yläelementti pinossa cout << s.kurkistaa() <<''; // poista pinosta ylin elementti s.pop(); } palata 0; } //Koodia on muokannut 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->kapasiteetti = kapasiteetti;  pino->ylä = -1;  pino->array = (int*)malloc(pino->kapasiteetti * koko(int));  paluu pino; } // Pino on täynnä, kun top on yhtä suuri kuin viimeinen indeksi int isFull(struct Stack* stack) { return pino->top == pino->kapasiteetti - 1; } // Pino on tyhjä, kun top on yhtä suuri kuin -1 int isEmpty(struct Pino* pino) { return pino->top == -1; } // Toiminto pinottavan kohteen lisäämiseksi. Se kasvaa alkuun 1 void push(struct Pino* pino, int item) { if (isFull(pino)) return;  pino->array[++pino->top] = kohde;  printf('%d työnnetty pinoon
', kohde); } // Toiminto, joka poistaa kohteen pinosta. Se pienenee ylhäältä 1 int pop(rakenne Pino* pino) { if (isEmpty(pino)) return INT_MIN;  return pino->array[pino->top--]; } // Toiminto, joka palauttaa pinon yläosan poistamatta sitä int peek(struct Pino* pino) { if (isEmpty(pino)) return INT_MIN;  return pino->array[pino->top]; } // Ohjainohjelma yllä olevien funktioiden testaamiseen int main() { struct Pino* pino = createStack(100);  push(pino, 10);  push(pino, 20);  push(pino, 30);  printf('%d popped pinosta
', pop(pino));  paluu 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('Pinon ylivuoto');  palauttaa väärä;  } else { a[++yläosa] = x;  System.out.println(x + ' työnnetty pinoon');  palauttaa tosi;  } } 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]);  } } } // Ohjainkoodi luokka Main { public static void main(String args[]) { Pino s = new Pino();  s.push(10);  s.push(20);  s.push(30);  System.out.println(s.pop() + ' Poplattu pinosta');  System.out.println('Top elementti on :' + s.peek());  System.out.print('Pinossa olevat elementit :');  s.print();  } } //Tätä koodia on muokannut 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('Pinon ylivuoto');  palauttaa väärä;  } else { t+=1;  a[t] = x;    console.log(x + ' työnnetty pinoon ');  palauttaa tosi;  } } 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);  työnnä (20);  työnnä (30);  console.log(pop() + ' Popped pinosta');  console.log(' Ylin elementti on :' + peek());  console.log(' Pinossa olevat elementit : ');  Tulosta(); // Tämän koodin tarjoaa Rajput-Ji>>  
  Lähtö      Array-toteutuksen edut:    
 
Helppo toteuttaa.
Muisti tallennetaan, koska osoittimet eivät ole mukana.
    Array-toteutuksen haitat:    
 
Se ei ole dynaaminen, eli se ei kasva ja kutistu tarpeista riippuen ajon aikana. [Mutta jos kyseessä ovat dynaamiset taulukot, kuten vektori C++:ssa, lista Pythonissa, ArrayList Javassa, pinot voivat kasvaa ja kutistua myös taulukon toteutuksen myötä].
Pinon kokonaiskoko on määriteltävä etukäteen.

// C++-ohjelma pinon linkitettyjen luetteloiden toteuttamiseen #sisältää käyttämällä nimiavaruus std; // Rakenne, joka edustaa pinoa luokkaa StackNode { julkinen: int tiedot; StackNode* Seuraava; }; StackNode* newNode(int tiedot) { StackNode* stackNode = Uusi StackNode(); stackNode->tiedot = tiedot; stackNode->Seuraava = TYHJÄ; palata stackNode; } int on tyhjä(StackNode* juuri) { palata !juuri; } mitätön työntää(StackNode** juuri, int tiedot) { StackNode* stackNode = newNode(tiedot); stackNode->Seuraava = *juuri; *juuri = stackNode; cout << tiedot << ' pushed='' to='' pinoon<='' span=''> '; } int pop(StackNode** juuri) { jos (on tyhjä(*juuri)) palata INT_MIN; StackNode* temp = *juuri; *juuri = (*juuri)->Seuraava; int poksahti = temp->tiedot; vapaa(temp); palata poksahti; } int kurkistaa(StackNode* juuri) { jos (on tyhjä(juuri)) palata INT_MIN; palata juuri->tiedot; } // Kuljettajakoodi int pää() { StackNode* juuri = TYHJÄ; työntää(&juuri, 10); työntää(&juuri, kaksikymmentä); työntää(&juuri, 30); cout << pop(&juuri) << ' poksahti pinosta '; cout << 'Ylein elementti on' << kurkistaa(juuri) << endl; cout <<'Pinossa olevat elementit:'; //tulosta kaikki pinon elementit: sillä aikaa(!on tyhjä(juuri)) { // tulosta yläelementti pinossa cout << kurkistaa(juuri) <<''; // poista pinosta ylin elementti pop(&juuri); } palata 0; } // Tämän koodin on antanut 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->data = data;  stackNode->seuraava = NULL;  paluu stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* pinosolmu = uusiSolmu(data);  stackNode->next = *juuri;  *juuri = pinosolmu;  printf('%d työnnetty pinoon
', data); } int pop(struct StackNode** root) { if (isEmpty(*juuri)) return INT_MIN;  struct StackNode* temp = *juuri;  *juuri = (*juuri)->seuraava;  int popped = temp->data;  vapaa (temp);  paluu popped; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  palauttaa root-> data; } int main() { struct StackNode* root = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d popped pinosta
', pop(&root));  printf('Top elementti on %d
', peek(root));  paluu 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

>>  
  Lähtö      Linkitetyn luettelon toteutuksen edut:    
 
Pinon linkitetty listatoteutus voi kasvaa ja kutistua ajonaikaisten tarpeiden mukaan.
Sitä käytetään monissa virtuaalikoneissa, kuten JVM.
    Linkitetyn luettelon toteutuksen haitat:    
 
Vaatii ylimääräistä muistia osoittimien käytön vuoksi.
Satunnaiskäyttö ei ole mahdollista pinossa.

Pinotietorakenteen toimintojen monimutkaisuusanalyysi:

Stackin edut Tietorakenne :

• Yksinkertaisuus: Pinot ovat yksinkertainen ja helposti ymmärrettävä tietorakenne, joten ne sopivat monenlaisiin sovelluksiin.
• Tehokkuus: Pinon työntö- ja pop-operaatiot voidaan suorittaa vakioajassa (O(1)) , joka tarjoaa tehokkaan pääsyn tietoihin.
• Viimeinen sisään, ensimmäinen ulos (LIFO): Pinot noudattavat LIFO-periaatetta varmistaen, että viimeinen pinoon lisätty elementti poistetaan ensimmäisenä. Tämä toiminta on hyödyllistä monissa skenaarioissa, kuten funktiokutsuissa ja lausekkeiden arvioinnissa.
• Rajoitettu muistin käyttö: Pinojen tarvitsee tallentaa vain ne elementit, jotka on työnnetty niihin, mikä tekee niistä muistitehokkaita muihin tietorakenteisiin verrattuna.

Stackin haitat Tietorakenne :

• Rajoitettu pääsy: Pinon elementteihin pääsee käsiksi vain ylhäältä, mikä vaikeuttaa elementtien hakemista tai muokkaamista pinon keskeltä.
• Ylivuotomahdollisuus: Jos pinoon työnnetään enemmän elementtejä kuin siihen mahtuu, tapahtuu ylivuotovirhe, joka johtaa tietojen menetykseen.
• Ei sovellu satunnaiskäyttöön: Pino s eivät salli satunnaista pääsyä elementteihin, joten ne eivät sovellu sovelluksiin, joissa elementtejä on käytettävä tietyssä järjestyksessä.
• Rajoitettu kapasiteetti: Pinoilla on kiinteä kapasiteetti, mikä voi olla rajoitus, jos tallennettavien elementtien lukumäärää ei tunneta tai se vaihtelee suuresti.

Pinotietorakenteen sovellukset:

• Korjaus Postfixiin /Etuliitteen muunnos
• Toista kumoamisominaisuudet monissa paikoissa, kuten editoreissa, Photoshopissa.
• Eteenpäin- ja taaksepäin-ominaisuudet verkkoselaimissa
• Muistinhallinnassa mikä tahansa nykyaikainen tietokone käyttää pinoa ensisijaisena hallintana käynnissä olevaan tarkoitukseen. Jokaisella tietokonejärjestelmässä käynnissä olevalla ohjelmalla on omat muistivarauksensa.
• Pino auttaa myös funktiokutsujen toteuttamisessa tietokoneissa. Viimeksi kutsuttu toiminto suoritetaan aina ensin.

Aiheeseen liittyvät artikkelit: