Paras vastaus
Lähde: Abstrakti tietotyyppi:
tietojenkäsittelytieteessä on abstrakti tietotyyppi ( ADT ) on matemaattinen malli mallille tietotyypit , joissa tietotyyppi määritetään sen käyttäytymisen ( semantiikan ) perusteella käyttäjä tietojen, erityisesti mahdollisten arvojen, tämän tyyppisten tietojen mahdollisten toimintojen ja näiden toimintojen suhteen. Tämä on ristiriidassa tietorakenteiden kanssa, jotka ovat konkreettisia esityksiä tiedoista ja jotka ovat toteuttajan, ei käyttäjän näkökulma.
Lähteestä Tietorakenne :
tietojenkäsittelytieteen yhteydessä tietorakenne on erityinen tapa järjestää data tietokoneessa siten, että sitä voidaan käyttää tehokkaasti .
Tietorakenteet voivat toteuttaa yhden tai useamman tietyn abstraktin tietotyypin (ADT), joilla määritetään toimintasopimus ja niiden monimutkaisuus
Tietorakenne on ADT: n tarjoaman sopimuksen konkreettinen toteutus
Tämä tarkoittaa:
1. ADT on abstrakti esitys käyttäjän näkökulmasta
2. DS on konkreettinen esitys , ei käyttäjän näkökulmasta
Yksinkertaisesti:
1. Pino on ADT , se määrittää vain, että käyttäjän on oltava push, pop jne.
2. Pino (kuten muut ADT: t, kuten jono) toteutetaan DS: llä, kuten taulukko tai luettelo (linkitetty luettelo jne.)
Yhteenveto:
Pino ei ole DS, se on ADT, ja se toteutetaan muu DS.
Toivottavasti auttoi.
Onnea onnella
Vastaa
Pinot
Pino on säilö esineistä, jotka lisätään ja poistetaan LIFO-periaatteen mukaisesti. Putkipinoissa sallitaan vain kaksi toimintoa: työnnä kohde pinoon ja pop esine pinosta. Pino on rajoitetun pääsyn tietorakenne – elementtejä voidaan lisätä ja poistaa pinosta vain yläosassa. push lisää kohteen pinon yläosaan, pop poistaa kohteen ylhäältä . Hyödyllinen analogia on ajatella pino kirjoja; voit poistaa vain ylimmän kirjan. Voit myös lisätä uuden kirjan yläosaan.
Pino on rekursiivinen tietorakenne. Tässä on pinon rakennemääritelmä:
Sovellukset
- Pinon yksinkertaisin sovellus on sanan kääntäminen. Työnnät tietyn sanan pinota varten – kirjain kirjaimelta – ja sitten kirjaimet pinosta.
- Toinen sovellus on ”kumoamismekanismi” tekstieditorissa; tämä toimenpide suoritetaan pitämällä kaikki tekstimuutokset pinossa. Takaisinta . Tämä on prosessi, kun sinun on käytettävä uusinta tietoelementtiä sarjassa elementtejä. Ajattele labyrinttiä tai sokkeloa – kuinka löydät tien sisäänkäynnistä uloskäynnille? Kun olet saavuttanut umpikujan, sinun on palattava takaisin. Mutta palaa mihin? edelliseen valintakohtaan. Siksi kussakin valintapisteessä tallennat kaikki mahdolliset valinnat pinoon. Tällöin taaksepäin siirtyminen tarkoittaa yksinkertaisesti seuraavan valinnan tekemistä pinosta.
- Kielenkäsittely: tilaa parametreille ja paikallisille muuttujille luodaan sisäisesti käyttämällä stack.compiler -sovelluksen syntaksitarkistus yhteensopiville aaltosulkeille toteutetaan käyttämällä stack.support rekursioon
Toteutus
Luokkien vakiokirjastossa tietotyyppipino on adapter -luokka, mikä tarkoittaa, että pino on rakennettu muiden tietorakenteiden päälle. Pinon taustarakenne voi olla taulukko, vektori, ArrayList, linkitetty luettelo tai muu kokoelma. Riippumatta taustalla olevan tietorakenteen tyypistä, pinon on toteutettava sama toiminto.Tämä saavutetaan tarjoamalla ainutlaatuinen käyttöliittymä:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
seuraava kuva osoittaa ajatuksen toteutuksesta sommittelun mukaan .
Toinen toteutusvaatimus (yllä olevan käyttöliittymän lisäksi) on, että kaikkien pino-operaatioiden on suoritettava
vakioaika O (1)
. Vakioaika tarkoittaa, että vakiota k on olemassa niin, että operaatio vie k nanosekuntia laskennallista aikaa pinon koosta riippumatta.
Matriisipohjainen toteutus
Taulukkoihin perustuvassa toteutuksessa ylläpidetään seuraavia kenttiä: taulukon A oletuskoko (≥ 1 ), muuttuja top , joka viittaa pinon yläosaan ja kapasiteettiin viittaa taulukon kokoon. Muuttuja top vaihtuu arvosta -1 arvoon capacity - 1. Sanomme, että pino on tyhjä, kun top = -1, ja pino on täynnä, kun top = capacity-1.
Kiinteässä -kokoinen pinonotto, kapasiteetti pysyy muuttumattomana, joten kun top saavuttaa kapasiteetin , pino objekti heittää poikkeuksen.
Dynaamisessa pinonotossa, kun yläosa saavuttaa kapasiteetin , kaksinkertaistamme pinon koon.
Linkitettyyn luetteloon perustuva toteutus
Linkitettyyn luetteloon perustuva toteutus tarjoaa parhaan (tehokkuuden kannalta) dynaamisen pinon toteutuksen.
Lähde – Pinot ja jonot