Stack Organization
Stack Organization
Stack Organization
Stack, also called as Last In First Out (LIFO) list, is the most useful feature in the CPU. It stores
information such that the item stored last is retrieved first. Stack is a memory unit with an
address register. This register holds the address for the stack, which is called as Stack Pointer
(SP). The stack pointer always holds the address of the item that is placed at the top of the
stack. You can insert an item into or delete an item from the stack. The insertion operation is
called as push operation and the deletion operation is called as pop operation. In a computer
stack, these operations are simulated by incrementing or decrementing the SP register.
REGISTER STACK:-
First the SP is set to 0, EMTY is set to 1, and FULL is set to 0. Now, as the stack is not full
(FULL = 0), a new item is inserted using the push operation. The push operation is performed
as below:
The stack pointer is incremented by 1 and the address of the next higher word is stored in the
SP. The word from DR is inserted into the stack using the memory write operation. As per
figure 5.3, the first item is stored at address 1 and the last item is stored at address 0. If the
stack pointer is at 0, then the stack is full and ‘FULL’ is set to 1. This is the condition when the
SP was in location 63 and after incrementing SP , the last item is stored at address 0. Once an
item is stored at address 0, there are no more empty registers in the stack. The stack is full and
the ‘EMTY’ is set to 0.
You can perform pop operation (deletion) only if the stack is not empty. To delete an item from
the stack, the following micro-operations are performed.
The top item from the stack is read and sent to DR and then the stack pointer is decremented.
If the stack pointer reaches 0, then the stack is empty and ‘EMTY’ is set to 1. This is the
condition when the item in location 1 is read out and the SP is decremented by 1.
MEMORY STACK:-
Stack can be implemented in the CPU by allotting a portion of the computer memory to a stack
operation and using a processor register as a stack pointer. In this case, it is implemented in a
random access memory attached to the CPU. In figure 7.4, a portion of the computer memory
is divided into three segments: program, data and stack. The address of the next instruction in
the program is stored in the pointer Program Counter (PC). The Address Register (AR) points
to an array of the data. SP always holds the address of the item present at the top of the stack.
The three registers that are connected to the common bus are PC, AR, and SP. PC is used to
read the instruction during fetch phase. An operand is read during execute phase using address
register. An item is pushed into or popped from the stack using stack pointer. Figure 7.4 depicts
the memory stack.
In figure 7.4, the SP points to an initial value ‘2001’. Here, the stack grows with decreasing
addresses. The first item is stored at address 2000, the next item is stored at address 1999 and
the last item is stored at address 1000.
As we already know, data register is used to read an item into or from the stack. You use push
operation to insert a new item into the stack.
SP SP -1
K[SP] DR
To insert another item into the stack, the stack pointer is decremented by 1 so that it points at
the address of the next location/word. A word from DR is inserted into the top of the stack
using memory write operation.
To delete an item from the stack, you need to use the pop operation:
DR K[SP]
SP SP + 1
The top item is read into the DR and then the stack pointer is decremented to point to the next
item in the stack.
Here, two processor registers are used to check the stack limits. One processor register holds
the upper limit (1000) and the other holds the lower limit (2001). During push operation, the
SP is compared with the upper limit to check if the stack is full. During pop operation, the SP
is compared with the lower limit to check if the stack is empty.
An item in the stack is pushed or popped using two micro-operations. They are:
2. Updating SP
A stack pointer is initially loaded with the bottom address of the stack in memory. Thereafter,
SP is automatically incremented or decremented depending on the operation performed (push
or pop). As the address is automatically updated in the stack pointer, the CPU can refer to the
memory stack without specifying the address.