User:DAndC/Stack organization
 | This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. For guidance on developing this draft, see Wikipedia:So you made a userspace draft. Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Stack is a Storage device added to a computer's central processing unit(CPU).[1]
In a CPU, Stack acts as a storage space. It is programmed in such a way that data that is entered last into a list can be retrieved first.[1]
Stack is used in digital computers too and is an essential part of the memory unit. An address register is maintained along with Stack. It is used to hold addresses for Stack. This register is known as a stack pointer(SP). The adding and deletion in Stack always takes place from the top of a list so that the point Stack is accessed from is always from the top.[1]
There are two operations associated with Stack, Push and Pop. The adding of data into Stack is known as Push and the removal of data is known as Pop. These two operations take place by the incrementing or decrementing stack pointer, and that is, from the top.[1]
Register stack
[edit]
A Stack can be constructed by using a portion of the memory or registers.[1] As shown in the diagram on the right, the SP contains the binary equivalent of the address of the TOP to which the SP is always pointing to. A,B and C are the three elements that are added to the stack. SP contains the address of the letter C and its value is three. Remove the item on the top of the Stack will decrease the address in the SP. Once C is removed, the SP will point to the location B. Insertion of a letter can done by increasing the SP and adding an element to the location SP is pointing to.[1]
In the 64-word stack, the SP contains a 6-bit address that has 6 binary numbers. It is needed to indicate the 64 address memory location: 2^6=64(from 0-63(000000-111111)). The lowest address is 0 and the highest is 63. The two registers empty and full is used to indicate whether the stack is empty or full. When the stack is full, the register full is set to 1. When it is empty or partially filled, it is cleared to 0. The full and empty registers are only needed to store two values of 0, meaning a single bit is needed to store those values. Therefore full and empty are single bit registers. The remaining box, DR means data register. It is used to store data to be written into or read out from the stack.[1]
Push operation
[edit]An SP is initially set to 0. That means the Stack is empty so the empty register is 1 and the full register is 0 . The SP is pointing to the 0 and data can be inserted into the Stack because full is not 1. A new item can be inserted into stack by a push operation. A push operation takes place by the following steps:[1]
| sp<-sp+1 //incrementing sp
m[sp]<-DR //pushing item if(sp=0) then FULL=1 //check if stack is full EMPTY=0 //mark stack is not empty |
The stack pointed is then incremented so that it is moved to next location or to the next higher word.[1]
Write operation
[edit]In a write operation the SP is first moved to a higher word and the data in the data register is written to the word to which the SP is currently pointing to. The code m[sp] denotes the word to which the SP is pointing to. The SP is incremented first so that the zeroth word is left blank and data is entered to the first word. The item then inserted to the first word and the last item, to the zeroth word.[1]
Pop operation
[edit]When the Stack is not empty it is known by the following [EMPTY=0]. Data can be removed from the Stack through the Pop operation. A pop operation can take place by the following steps:[1]
| DR<-m[sp] //inserting data to data register
sp<-sp-1 //decrementing sp if(sp=0) EMPTY=1//check if stack is empty FULL=0//mark the stack not full |
The first item is Popped from the zeroth word and the last item, from the word having 1 as its address.[1]
Memory Stack
[edit]
A stack an exist as a stand alone unit or it can implemented by RAM attached to memory.The stack is implemented in CPU by assigning a processor register as stack pointer and some portion of memory for stack.As in figure memory is divided into three parts:Program it contain instructions for performing various tasks,Data is the field which contain operands,and the stack .[1]
Each of three has a register associated with them. The program counter (PC) contains the address of the instruction that is to be executed next,The address register which pointing to the words of data,The stack pointer (sp) pointing to the top of the stack it helps in push and pop operation.[1] As in figure the starting location of the stack is 4000 when we going to higher location is stack the address is decreasing it is opposite to addressing of register stack.The first item is stored in 5000 and second item is stored in 4999 the last address or location that can be used as stack is 4000.[1]
push operation
[edit]As in register stack here also push means adding an item into stack.A new item can insert into stack by the following steps:[1]
sp<-sp-1 //decreasing sp m[sp]<-DR//Adding an item from Dr to stack
Here sp is decreasing in push because the next higher words address is one less than the current.A memory write operation can insert data from DR to stack[1]
pop Operation
[edit]pop is removing an item from stack.A pop operation take place by following instructions:[1]
DR<-m[sp] //Adding data to DR from Stack sp<-sp+1//incrementing sp
The item on the top of the stack is write into the DR.The stack pointer then incremented to next location.[1]
The push an pop operations always add or remove words of data from the stack never bytes in the 8086-80286 microprocessors.The 80380/80486 allow word or double word to push or pop from the stack.[2]
References
[edit]3.http://www.electronics.dit.ie/staff/tscarff/stack/stack.htm