Department of computer science

Assignment

Course Title: computer Architecture and organization

Course Code:cosc 2021

Rekik Tamrat……………………………………………..RCD/0599/2013
What is Stack Organization?
Computer ArchitectureComputer ScienceNetwork

Stack is also known as the Last In First Out (LIFO) list. It is the most important feature in the CPU. It saves
data such that the element stored last is retrieved first. A stack is a memory unit with an address
register. This register influence the address for the stack, which is known as Stack Pointer (SP). The stack
pointer continually influences the address of the element that is located at the top of the stack.

It can insert an element into or delete an element from the stack. The insertion operation is known as
push operation and the deletion operation is known as pop operation. In a computer stack, these
operations are simulated by incrementing or decrementing the SP register.

Register Stack

The stack can be arranged as a set of memory words or registers. Consider a 64-word register stack
arranged as displayed in the figure. The stack pointer register includes a binary number, which is the
address of the element present at the top of the stack. The three-element A, B, and C are located in the
stack.

The element C is at the top of the stack and the stack pointer holds the address of C that is 3. The top
element is popped from the stack through reading memory word at address 3 and decrementing the
stack pointer by 1. Then, B is at the top of the stack and the SP holds the address of B that is 2. It can
insert a new word, the stack is pushed by incrementing the stack pointer by 1 and inserting a word in
that incremented location.

The stack pointer includes 6 bits, because 26 = 64, and the SP cannot exceed 63 (111111 in binary). After
all, if 63 is incremented by 1, therefore the result is 0(111111 + 1 = 1000000). SP holds only the six least
significant bits. If 000000 is decremented by 1 thus the result is 111111.

Therefore, when the stack is full, the one-bit register ‘FULL’ is set to 1. If the stack is null, then the one-
bit register ‘EMTY’ is set to 1. The data register DR holds the binary information which is composed into
or readout of the 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 element is inserted using the push operation.

The push operation is executed as follows −

SP←SP + 1 It can increment stack pointer

K*SP+ ← DR It can write element on top of the stack

If (SP = 0) then (FULL ← 1) Check if stack is full

EMTY ← 0 Mark the stack not empty

The stack pointer is incremented by 1 and the address of the next higher word is saved in the SP. The
word from DR is inserted into the stack using the memory write operation. The first element is saved at
address 1 and the final element is saved 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
final element is saved at address 0. During an element is saved at address 0, there are no more empty
registers in the stack. The stack is full and the ‘EMTY’ is set to 0.

A new element is deleted from the stack if the stack is not empty (if EMTY = 0). The pop operation
includes the following sequence of micro-operations −

DR←K*SP+ It can read an element from the top of the stack

SP ← SP – 1 It can decrement the stack pointer

If (SP = 0) then (EMTY ← 1) Check if stack is empty

FULL ← 0 Mark the stack not full

The top element from the stack is read and transfer to DR and thus 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
element in location 1 is read out and the SP is decremented by 1.

What is Memory Stack in Computer Architecture?

Computer ArchitectureComputer ScienceNetwork
A stack can be executed in the CPU by analyzing an area of the computer memory to a stack operation
and utilizing a processor register as a stack pointer. In this method, it is performed in a random access
memory connected to the CPU.

An area of the computer memory is broken into three segments such as program, data, and stack. The
address of the next instruction in the program is saved in the pointer Program Counter (PC). The Address
Register (AR) points to an array of the information. SP continually influences the address of the element
present at the top of the stack.

The three registers that are linked to the common bus are PC, AR, and SP. PC can read the instruction
during the fetch stage. An operand is read during execute stage using the address register. An element is
pushed into or popped from the stack using a stack pointer.

The data register can read an element into or from the stack. It can use push operation to insert a new
element into the stack.

SP ← SP – 1

K ← SP *DR+

It can insert another element into the stack, the stack pointer is decremented by 1. It can point to the
address of the next location/word. A word from DR is inserted into the top of the stack using memory
write operation.

It can delete an element from the stack. It can use the pop operation which is as follows −

DR ← K *SP+

SP ← SP + 1

The top element is read into the DR and then the stack pointer is decremented to point to the next
element in the stack.

Two processor registers can check the stack limits. One processor register influence the upper limit
(1000) and the other influence 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.

What is Stack/Stack Pointer : Types & Its Applications

The stack is nothing but the linear data structure where insertion and deletion take place only at one
end. The insertion operation is having a special name known as PUSH and the deletion operation is also
having a special name known as POP. The PUSH and POP are two fundamental operations that could be
carried out only in a particular stack. It is a group of memory locations and the memory locations are
related to either read memory or write memory. This is used for storing binary information during the
execution of the program, when we are executing any program then the contents of that program are
going to store in the stack. It follows Last In First Out (LIFO) and it is used only for storing and retrieving
the data but not used for storing the data. The brief explanation of the stack/stack pointer is discussed
below.

What is Stack/Stack Pointer?

Definition: The stack is a storage device, used for storing information or data in a manner of LIFO (Last In
First Out). Whenever we enter the data in the form of LIFO manner, the element that has to be deleted
first is the last inserter element, so the last inserted element is taken out first. It is the memory unit
within an address register called stack pointer (SP). The stack pointer always indicates the top element
in the stack that means which location the data has to be inserted.

Types of Stack
There are two types of stacks they are register stack and the memory stack.

Register Stack

The register stack is also a memory device present in the memory unit, but it handles only a small
amount of data. The stack depth is always limited in the register stack because the size of the register
stack s very small compared to the memory.

Push Operation in Register Stack

Step1: The stack pointer increments by 1.

SP←SP+1

Step2: Enter the data into the stack.

M*SP+←DR

Where DR is the Data Register

Step3: Check whether the stack is full or not

if (sp=0) then (full←1)

Step4: Mark not empty

empty←0
Pop Operation in Register Stack

Step1: Read data from the stack.

DR←M*SP]

Step2: Decrement stack point.

SP←SP-1

Step3: Check whether the stack is empty or not

if sp=0 then empty←1

The stack organization of the 64-bit register stack is shown in the below figure.

Register Stack Organization

Register Stack Organization

Memory Stack

In the memory stack, the stack depth is flexible. It occupies a large amount of memory data, whereas in
the register stack only a finite number of memory words will be stored.

Push Operation in Memory Stack

Step1: SP←SP+1

Step2: M*SP+←DR

Pop operation in Memory Stack

Step1: DR←M*SP+

Step2: SP←SP-1

Memory Stack

The total memory unit is divided into three parts, the first memory unit has the program (nothing but
instructions), the second part is data (operands) and the third part is stack. The program instructions
always store in the program counter (PC), the data registers are identified by the address register (AR).
The address 3000 to 4001 used for the stack and the first item or element is stored at 4001.

Stack/Stack Pointer in 8085 Microprocessor

The programmer view of 8085 microprocessor contains general-purpose registers and special-purpose
registers. The general-purpose registers are A, B, C, D, E, H, L, and the special purpose registers are SP
(Stack Pointer) and PC (Program Counter). The programmer view of 8085 microprocessor is shown in the
below figure.

Programmer View of 8085

Programmer View of 8085

The stack pointer is a 16-bit register contains memory address, suppose stack pointer (SP) contents are
FC78H, then the microprocessor 8085 interprets it. The memory locations have useful information from
FC78H to FFFH and from FC77H to 0000H the memory location doesn’t have useful information. The
interpretation of the stack pointer is shown in the below figure.

Interpretation of Stack Pointer

Interpretation of Stack Pointer

Basic Operations of Stack/Stack Pointer

There are two operations of the stack they are: PUSH operation and POP operation.

PUSH Operation

The PUSH means pushing or inserting an element into the stack. The PUSH operation always increments
the stack pointer and the POP operation always decrements the stack pointer. In the case of a push
operation, we have to check whether there is a free space is available or not. If free space is available,
we can go to the push operation, if free space is not available then error message occurs that is overflow.
The overflow is to be check in case of push operation respectively. The basic operation of push and pop
is shown in the below figure.

Basic Operation of PUSH and POP

Basic Operation of PUSH and POP

Figure (a) is the stack. If you want to push the element that is an inserting the element into the stack,
you have to push(s, a), where ‘s’ is nothing but a stack. In the stack, we are placing the ‘a’ element and
this operation is shown in figure (b). See the figure (3), suppose stack contains three elements a, b,c, and
the stack is filled with an element.

If you want to insert a fourth element-‘d’ using push(s, d), but there is no space available to insert the
element then it indicates that the stack is overflow. The overflow terminology is used when the stack is
full and the algorithm of push operation is shown below.

push(stack[], top, max stack, item)

if(top==maxstack-1)
{

print “overflow”

else

top=top+1

stack[top]=item

End

POP Operation

The POP means deleting the element at the top of the stack. In the case of pop operation, we have to
check whether the stack is initially empty or not. If the stack is initially empty then there occurs an
underflow situation. Suppose the stack is empty still you want to pop the elements in the stack but
there are no elements in the stack then it leads to stack underflow.

The underflow is to be check in case of pop operation respectively. In pop operation whatever the top
element is present in the stack that should be popped or deleted, so no need to mention which element
will be popped, by default the topmost element will be popped. The algorithm of pop operation is
shown below.

pop(stack[], top, item)

if(top==-1)

print “underflow”

else

item=stack[top]

top=top-1}
So this is the explanation of how the elements are inserted and deleted in the stack by using push and
pop operation.

Applications

The applications of the stack/stack pointer are

String reversal

Balanced parenthesis

UNDO/DED

System stack for activation records