Stack Organization

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

What is 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:

• Register Stack 
• Memory Stack

Register 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).

SP←SP + 1    // increments the stack pointer
K[SP] ← DR   // writes the element on the top of the stack
If (SP = 0) then (FULL ← 1) // to check if the stack is full
EMTY ← 0  // to mark that stack is not empty

 

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:

DR←K[SP]    // to read an element from the top of the stack
SP ← SP - 1   // to decrement the stack pointer
If (SP = 0) then (EMTY ← 1)   // to check if the stack is empty
FULL ← 0  // to mark that stack is not full

 

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.

Memory Stack

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.

Reverse Polish Notation In Stack

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. 

For example, we are given this expression in the form of an array,

["18", "5", "*", "6", "/"]

 

From the given array we can deduce expression as,

((18 * 5) / 6) = 15

 

Approach

1. We will access all the elements of the array one by one. While accessing all the elements, we will check if the current element is matching with the special character ('+', '*', '/', '-').
2. If the element does not match with any of the given special characters, then we will push that element into the stack.
3. After that, if any element is matched with the special character, we will pop the first two elements from the stack and we will perform the action and then push the result obtained by the operation into the stack again.
4. We will perform steps 1, 2, 3 for every array element.
5. In the end, we will pop the final result from the stack and will print the result

Advantages of Stack Organization

• Complex arithmetic statements may be rapidly calculated
• Instruction execution is rapid because operand data is stored in consecutive memory areas
• The instructions are minimal since they don't contain an address field

Disadvantages of Stack Organization

• The size of the program increases when we use a stack
• It's in memory, and memory is slower in several ways than CPU registers. It generally has a lesser bandwidth and a longer latency. Memory accesses are more difficult to accelerate