Stack

Innehåll- 1. Allmänt - 2. Datalogi

1. Allmänt

En stack är en uppkastad hög. höstack, myrstack.

2. Datalogi

En stack används för att hantera data enligt modellen LIFO (Last In, First Out).En stack är ofta, men inte alltid, belägen i en process stacksegment.

När man lägger in data i en stack så brukar man kalla för att pusha data på stacken.Operationen som trycker in information i det rör som LIFOn i princip utgör kallas för push och operationen att ta bort data från stacken kallas för pop. Följande kod borde generera strängen "foo".

stack s;spush( "o" );spush( "o" );spush( "f" );write( spop() );write( spop() );write( spop() );

Hur stacken ovan implementeras är väldigt svårt att veta. Det kan lika gärna vara en länkad lista som en "riktig" stack.En riktig stack kan bestå, som hos Intel¹, av ett minnessegment och en stackpekare. När ett element pushas på stacken så skrivs minnet som finns på stacksegmentets basadress plus värdet på stackpekaren över, varpå stackpekaren ökas med det pushade värdets storlek.När ett element poppas från stacken så utspelar sig samma sak i omvänd ordning. Således måste man i förväg veta storleken för nästa element på stacken, annars riskerar stacken korrumpering.

¹ Motorolas arkitektur M68k använder en enklare teknologi där stackpekaren direkt anger minnets fysiska adress. Ursprungligen med 24-bitars adressbuss men från modellen MC68020 så gick man över till ren 32-bitars adressering. Intel hakade senare på med sin modell 80386 som även den använder en 32-bit adressbuss.

Följande exempel förutsätter att stackpekaren räknar i bytes.

move.w #1, d0; flytta värdet 1 till register d0move.w #2, d1; flytta värdet 2 till register d1push.b d0; pusha en byte från register d0 på stacken ; en byte med värdet 1 skrivs och stackpekaren ökas med ettpush.w d1; pusha ett word (2 bytes) på stacken från register d1 på stacken ; två bytes, ett word med värde 2, skrivs och stackpekaren ökas med tvåpop.wd2; popa ett word från stacken till register d2, det värde som var i d1 ; stackpekaren minskas med två och ett word läses in i register d2pop.wd3; popa ett word från stacken till register d3, men bara en liten ; hälften av det som läses av från stacken är pushat i den här kodsnutten ; stacken är korrumperad.

Redigera?

Artikeln skriven 2009-01-17 av Learning4sharing

Inga kategorier för denna artikel än...

Intresserad av fler artiklar?

Vägnät
Centrala Bilregistret
Cherbourg
Øresundsbro Konsortiet
Presentation Manager
Zilog
Z80
Dan Wolgers
Agnostiker