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

Compare to the register unit, the memory unit stores a large amount of data. The memory stack figure is shown in the below figure.

Memory Stack
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

}

Example

The elements are inserted in the order as A, B, C, D, E, it represents the stack of five elements. In figure (a), we want to push ‘A’ element on the stack then the top becomes zero (top=0), similarly the top=1 when ‘B’ element is pushed, top=2 when the ‘C’ element is pushed, top=3 when the ‘D’ element is pushed, and top=4 when the ‘E’ element is pushed.

So whatever the elements I have taken is placed in the stack, now the stack is full. If you want to push another element there is no place in the stack, so it indicates the overflow. Now the stack is full if you want to pop the element ‘E’ element has to be deleted first. The push operation is shown in the below figure.

Push Operation
Push Operation

We have to use the pop operation to delete the elements in the stack. So just mention pop() don’t write arguments in the pop because by default it deletes the top element. The first ‘E’ element is deleted next ‘D’ element…..’ A’. When the top elements are deleting then the top value decreases. When top=-1 the stack indicates underflow. The pop operation is shown in the below figure.

POP Operation
POP Operation

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/DEDO
  • System stack for activation records
  • Infix, prefix, postfix, expression

FAQs

1). What is the stack pointer in the arm?

The stack pointer register (R13) used as a pointer to the active stack in ARM.

2). Why stack pointer is 16 bit?

The stack pointer (SP) and the program counter (PC) utilized to store the previous location and the memory location address is 16 bits, so stack pointer (SP) is also of 16 bit.

3). What is the role of the stack pointer?

The role of the stack pointer (SP) is to indicate the top of the element in the stack.

4). Which stack is used in 8085?

The stack used in 8085 is Last In First Out (LIFO).

5). Is stack pointer a register?

Yes, the stack pointer (SP) is an address register which always indicates the top of the element in the stack.

In this article what is stack/stack pointer (SP), push operation, and pop operation with an example, register stack and memory stack with diagrams, stack, and stack pointer in 8085 and applications are discussed. Here is a question for you what is the use of stack/stack pointer?

Comments are closed.