Here is the concept of stack and Stack Organization
Quick View of Stack:
A stack is a data storage structure in which the most recent thing deposited is the most recent item retrieved. It is based on the LIFO concept (Last-in-first-out).
The stack is a collection of memory locations containing a register that stores the top-of-element address in digital computers.
Stack’s operations are:
- Push: Adds an item to the top of the stack
- Pop: Removes one item from the stack’s top
Stack Organization:
The Last In First Out (LIFO) list is another name for stack. It is the CPU’s most crucial feature. It saves information so that the last element saved is retrieved first. A memory space with an address register is called a stack.
- This register, known as the Stack Pointer, affects the stack’s address (SP).
- The address of the element at the top of the stack is continuously influenced by the stack pointer.
Implementation of Stack:
The stack can be implemented using two ways:
1.) Register Stack:
A register stack is a data structure used in computer architecture and microprocessor design to store data temporarily.
• It typically consists of a set of registers organized in a stack-like manner, where data can be pushed onto the stack or popped off the stack.
• A stack of memory words or registers may be placed on top of each other. Consider a 64-word register stack like the one shown in the diagram. A binary number, which is the address of the element at the top of the stack, is stored in the stack pointer register. The stack has the three elements A, B, and C.
• The stack pointer holds C’s address, which is 3. C is at the top of the stack. The top element is removed from the stack by reading the memory word at address 3 and decreasing the stack pointer by one. As a result, B is at the top of the stack, and the SP is aware of B’s address, which is 2. It may add a new word to the stack by increasing the stack pointer and inserting a word in the newly increased location.
• Because 26 = 64 and the SP cannot exceed 63, the stack pointer has 6 bits (111111 in binary). After all, if you multiply 63 by 1, the outcome is 0(111111 + 1 = 1000000). Only the six least important bits are stored in SP. The result of decrementing 000000 by one is 111111.
• As a result, the one-bit register ‘FULL’ is set to 1 when the stack is full. The binary information constructed into or readout of the stack is stored in the data register DR.
• First, the SP is set to 0, the EMTY to 1, and the FULL to 0. The push operation is used to insert a new piece because the stack is not yet full (FULL = 0).
• The stack pointer is raised by one, and the location of the next higher word is stored in the stack pointer. The memory write operation is used to place the word from DR onto the stack. The first and last elements are kept at addresses 1 and 0, respectively. When the stack pointer reaches 0, the stack is full, and the value of ‘FULL’ is set to 1. When the SP was at location 63, the last element was stored at address 0 after incrementing the SP. There are no more empty registers on the stack when an element is stored at address 0. The ‘EMTY’ is set to 0 since the stack is full.
• If the stack is not empty (if EMTY = 0), a new element is added. The pop operation consists of the following micro-operations:
• As the top element from the stack is read and moved to DR, the stack pointer is decremented. When the stack pointer approaches 0, ‘EMTY’ is set to 1, and the stack is empty. This is where the element in location 1 is read out, and the SP is decremented by one.
2.) Memory Stack:
Memory Stack is a region of memory where data is stored and retrieved in a last-in, first-out (LIFO) manner.
• In other words, the last item that was added to the stack is the first one to be removed.
• A stack may be implemented in a computer’s random access memory (RAM). A stack is implemented in the CPU by allocating a chunk of memory to a stack operation and utilizing a processor register as a stack pointer. The stack pointer is a CPU register that specifies the stack’s initial memory address.
•A portion of memory is assigned to a stack operation to implement the stack in the CPU. Here the processor register is used as a Stack Pointer (SP).
The above figure shows the portion of computer memory divided into three segments: Program Instructions, Data, and Stack.
Program Counter(PC):
It is a register that points to the address of the next instruction that is going to be executed in the program.
Address Register:
This register points at the collection of data and is used during the execute phase to read an operand.
Stack Pointer:
It points at the top of the stack and is used to push or pop the data items in or from the stack.
• As we can see in the figure, these three registers are connected to a common address bus and either one of them can provide an address for memory. Stack Pointer is first going to point at the address 3001, and then the stack will grow with the decreasing addresses. It means that the first item is going to be stored at address 3001, the second item at address 3000, and the items can keep getting stored in the stack until it reaches the last address 2000 where the last item will be held. Here the data which is getting inserted into the Stack is obtained from the Data Register and the data retrieved from the Stack is also read by the Data Register.
Reverse Polish Notation:
The reverse polish notation in the stack is also known as postfix expression. Here, we use stack to solve the postfix expression.
From the postfix expression, when some operand is found, we push it into the stack, and when some operator is found, we pop elements from the stack, and after that, the operation is performed in the correct sequence, and the result is also stored in the stack.
The Polish Mathematician Lukasiewicz showed the mathematic expressions can be represented in prefix notation. This representation, often referred to as polish notation, place the operator before the operands.
The postfix notation referred to as reverse polish notation(RPN), places the operator after the operands.
The following examples demonstrates the tree representation:
A+B Infix Notation
+AB Prefix or Polish Notation
AB+ Post or Reverse Polish Notation
The reverse polish notation is in a form suitable for stack implementation. The expression: A*B+C+D is written as AB*CD*+. and is evaluated as follows:
scan the expression from left to right. When an operator is reached, perform the operation with the two operands found on the left side of the operator. Remove the two operands and the operator and replace them by the number obtained from the result of the operation. Continue the scan the expression and repeat the procedure for every operator encountered until there are no more option.
Conversion of to RPN(Reverse Polish Notation):
• The conversion from infix notation to reverse polish notation must take into consideration the operational hierarchy adopted for the infix notation. This hierarchy dictates that we first perform all arithmetic inside inner parentheses, then inside outer parentheses, and do multiplication and division operations before adding and subtraction.
Consider the expression: (A+B)*[(C*(D+E)+F]
• To evaluate the expression we must first perform the arithmetic inside the parentheses (A+B) and (D+E). Next we must calculate the expression inside the square brackets. The multiplication of C*(D+E) must be done prior to the addition of F since multiplication has precedence over addition. The last operation is the multiplication of the two terms between the parentheses and brackets. The expression can be converted to reserve polish notation, without the use of parentheses, by taking into consideration the operation hierarchy.
The converted expression is: AB+DE+C*F+ *
Proceeding from left to right, we first add A and B, then add D and E. At this point we are left with:
(A+B)(D+E)C*F+*
Evaluation of Arithmetic Expression:
The stack organization is very effective in evaluating arithmetic expressions.
• Expressions are usually represented in what is known as Infix notation, in which each operator is written between two operands (i.e., A + B). With this notation, we must distinguish between ( A + B )*C and A + ( B * C ) by using either parentheses or some operator-precedence convention.
• Thus, the order of operators and operands in an arithmetic expression does not uniquely determine the order in which the operations are to be performed.
Polish Notation(Prefix notation):
• It refers to the notation in which the operator is placed before its two operands.
• Here no parentheses are required, i.e., +AB.
Reverse Polish Notation(Postfix notation):
• It refers to the analogous notation in which the operator is placed after its two operands.
• Again, no parentheses is required in Reverse Polish notation, i.e., AB+
Stack-organized computers are better suited for post-fix notation than the traditional infix notation. Thus, the infix notation must be converted to the postfix notation. The conversion from infix notation to postfix notation must take into consideration the operational hierarchy.
There are 3 levels of precedence for 5 binary operators as given below:
Highest: Exponentiation (^) Next highest: Multiplication (*) and division (/) Lowest: Addition (+) and Subtraction (-)
For example :
Infix notation: (A-B)*[C/(D+E)+F] Post-fix notation: AB- CDE +/F +*
Here, we first perform the arithmetic inside the parentheses (A-B) and (D+E). The division of C/(D+E) must be done prior to the addition with F. After that multiply the two terms inside the parentheses and bracket.
Now we need to calculate the value of these arithmetic operations by using a stack.
The procedure for getting the result is:
- Convert the expression in Reverse Polish notation( post-fix notation).
- Push the operands into the stack in the order they appear.
- When any operator encounters then pop two topmost operands for executing the operation.
- After execution push the result obtained into the stack.
- After the complete execution of expression, the final result remains on the top of the stack.
For example :
Infix notation: (2+4) * (4+6) Post-fix notation: 2 4 + 4 6 + * Result: 60
