Stack Organization

A useful feature that is included in the CPU of most computers is a stack or last in first out (LIFO) list. A stack is a storage device that stores information in such a manner that the item stored last is the first item retrieved. The operation of a stack can be compared to a stack of trays. The last tray placed on top of the stack is the first to be taken off.

The register that holds the address for the stack is called a stack pointer (SP) because its value always points at the top item in stack.

The two operation of stack are the insertion and deletion of items.

1. The operation of insertion is called PUSH. 
2. The operation of deletion is called POP.

Register Stack :

The stack pointer register SP contains a binary number whose value is equal to the address of the word that is currently on top of the stack. In a 64-word stack, the stack pointer contains 6 bits because 2⁶ =64. 

The one bit register Full is set to 1 when the stack is full, and the one-bit register EMTY is set to 1 when the stack is empty of items.

The push operation is implemented with the following sequence of micro-operation. 

SP ←SP + 1 (Increment stack pointer) 

M(SP) ← DR (Write item on top of the stack) 

if (sp=0) then (Full ← 1) (Check if stack is full) 

Emty ← 0 ( Marked the stack not empty) 

The pop operation is implemented with the following sequence of micro-operation.

DR← M[SP] Read item from the top of stack 

SP ← SP-1 Decrement stack Pointer 

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

FULL ← 0 Mark the stack not full

Reverse Polish Notation (Postfix Notation):

A stack organization is very effective for evaluating arithmetic expressions. The common mathematical method of writing arithmetic expressions imposes difficulties when evaluated by a computer. The common arithmetic expressions are written in infix notation, with each operator written between the operands. Consider the simple arithmetic expression

A*B+C*D

that arithmetic expressions can be represented in prefix notation . This representation, often referred to as Polish notation, places the operator before the operands. The postfix notation, referred to as reverse Polish notation (RPN), places the operator after the operands. The following examples demonstrate the three representations: 

A+ B Infix notation 

+ AB Prefix or Polish notation 

AB + Postfix or reverse Polish notation 

Evaluation of Arithmetic Expressions: 

Reverse Polish notation, combined with a stack arrangement of registers, is the most efficient way known for evaluating arithmetic expressions.

The following numerical example shows the evaluation of arthematic expressions. Consider the arithmetic expression 

(3 * 4) + (5 * 6) 

In reverse Polish notation, it is expressed as 

34*56*+  

Now consider the stack operation. Each box represents one stack operation and the arrow always points to the top of the stack. Scanning the expression from left to right, we encounter two operands. First the number 3 is pushed into the stack, then the number 4. The next symbol is the multiplication operator *. This causes a multiplication of the two topmost items in the stack. The stack is then popped and the product is placed on top of the stack, replacing the two original operands. Next we encounter the two operands 5 and 6, so they are pushed into the stack. The stack operation that results from the next * replaces these two numbers by their product. The last operation causes an arithmetic addition of the two topmost numbers in the stack to produce the final result of 42.