Last Updated on September 22, 2023 by Mayank Dham
The stack pointer, a fundamental concept in computer science and programming, plays a pivotal role in managing memory and controlling program execution. As a core component of the stack data structure, the stack pointer serves as a reference point that determines the top of the stack’s current position in memory. Through its dynamic manipulation, the stack pointer facilitates the orderly storage and retrieval of data, function calls, and program state.
Understanding the intricacies of the stack pointer is essential for grasping memory management, function execution, and the flow of data within a program. This discussion delves into the significance of the stack pointer, its interaction with the stack, and its broader implications in various programming paradigms.
What is a Stack?
A stack is a data structure or a storage device that follows LIFO or FILO i.e. Last in First Out or First In Last Out principle. This means that the element that is inserted at last in a stack is removed first and vice versa. For instance, consider an empty stack shown below.
Now, let us push the elements 10, 20, 30, 40, and 50 in the same order as mentioned.
The operation of adding an element into the stack is known as the push operation. Now, if we want to remove an element from the stack, the topmost element gets removed as shown below.
The operation of removing an element from the stack always removes the topmost element and is called the pop operation.
Now that we have understood what a stack is and how it works, let us now understand what a stack pointer is.
What is a Stack Pointer?
As already discussed above, a stack is a memory device or memory organization that follows the LIFO principle. This means that the element at the top of the stack is the one that gets removed from the stack first and the insertion in a stack also occurs at the top of the stack. So, in a stack, the top is a very important aspect.
Stack Pointer is a pointer that always points to the top of the stack. In microprocessors, a stack pointer is a memory unit in the address register that stores the address of the top of the stack. We will discuss this concept in detail in the later sections of this discussion.
Before discussing the types of stack pointers, let us understand how the stack operations are performed with the help of the stack pointer using a program.
Basic Stack/Stack Pointer Operations
We know that push and pop are the 2 main operations of a stack. Here, we will learn how a stack can be created in a program and how the push and pop operations are actually performed in a program.
First, we need to understand that a stack can be created using an array or a list. A list provides the flexibility of the dynamic size of the stack however an array limits the size of the stack. Depending on our needs, we can implement any of them. However, the work remains the same. So, we have an empty list/array. Now, let us see how the push and pop operations are performed.
The stack pointer will be set to -1. This is because the stack is empty initially and the stack pointer points to the top element of the stack.
Push Operation: We simply increment the value of the stack pointer and insert the new value where the stack pointer is now pointing after incrementing. The time complexity of this operations is O(1). This is shown below.
Pop Operation: We remove the element at the stack pointer position from the stack and decrement the value of the stack pointer. The time complexity of this operation is O(1). The pop operation is shown below.
Peek/Top: The peek or top operation is just to get the topmost element of the stack. Here, we return the top of the stack. The time complexity of the peek operation is O(1).
The program for the above operations is shown below.
class MyStack {
private int arr[];
private int top;
private int capacity;
MyStack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
public void push(int x) {
if (isFull()) {
System.out.println("Stack OverFlow");
System.exit(1);
}
System.out.println("Inserting " + x);
arr[++top] = x;
}
public int pop() {
if (isEmpty()) {
System.out.println("STACK EMPTY");
System.exit(1);
}
return arr[top--];
}
public Boolean isEmpty() {
return top == -1;
}
public Boolean isFull() {
return top == capacity - 1;
}
public void printStack() {
for (int i = 0; i <= top; i++) {
System.out.print(arr[i] + ", ");
}
}
}
public class Main {
public static void main(String[] args) {
MyStack stack = new MyStack(5);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.print("Stack: ");
stack.printStack();
stack.pop();
System.out.println("\nAfter popping out");
stack.printStack();
}
} Types of Stack/Stack Pointers
There are 2 main types of stacks. We have a register stack and a memory stack. Let us discuss these stacks and their respective stack pointer in detail.
Register Stack/Stack Pointer
This memory device is present in the Memory Unit (MU) of the processor. The register stack size is very small because there is limited memory available as compared to the memory stack. Lte us see how push operation happens in a register stack.
Register Stack/Stack Pointer Push Operation
The stack pointer is incremented by 1
SP ← SP + 1
The data present in the data register is entered into the stack
M[SP] ← DR
Checking if the stack is full or not
if(sp=0) then (full←1)
Mark the stack not empty as an element is pushed into it.
empty ← 0
Register Stack/Stack Pointer Pop Operation
Read the stack data and collect it in the data register.
DR ← M[SP]
Decrement the stack pointer as the top now moves down.
SP ← SP – 1
Since we removed an element, the stack might be empty. So, check it.
If (sp=0) then empty ← 1
So, this is the push and pop operations using the register stack pointer. The stack organization of a register stack is shown below.
So, the stack pointer is of 6bits size. The stack pointer holds the memory address of the topmost element of the stack memory. FULL and EMPTY are the flag registers.
Now that we have understood the Register Stack, let us now understand the Memory Stack.
Memory Stack/Stack Pointer
The memory stack is of large size as compared to the register stack. Although finite, it still has a flexible stack height/depth which means that a lot more data can be added as compared to the register stack. Let us now look at the push and pop operations of the memory stack.
Memory Stack/Stack Pointer Push Operation
The stack pointer is incremented by 1
SP ← SP + 1
The data present in the data register is entered into the stack
M[SP] ← DR
Memory Stack/Stack Pointer Pop Operation
Read the stack data and collect it in the data register.
DR ← M[SP]
Decrement the stack pointer as the top now moves down.
SP ← SP – 1
The memory unit stack organization is shown below.
The entire memory unit is divided into three parts: the programme (which consists solely of instructions), data (which includes operands), and stack. The program counter (PC) always stores the program instructions, and the address register identifies the data registers (AR). The stack is stored at addresses 3000 to 4001, while the first item or element is kept at address 4001.
Now that we have covered the types and operations of a stack and stack pointer, let us now understand the applications of the same.
Applications of Stack/Stack Pointer
- A stack using the stack pointer and its operations of push and pop can be used to reverse a string.
- A stack is used to solve the balance parenthesis problem i.e. it can be used to check whether the parenthesis of an expression are matching as well as balanced or not.
- The Memory and Register stack/stack pointer in the processors are used to perform the UNDO and REDO operations.
- The Memory stack is also used to maintain the system activation records.
- Expression Evaluation and conversion in the computers i.e. prefix, infix and postfix expression evaluations and conversion of one type into another is done using stack and operations of stack/stack pointer.
So, this was all about the stack pointer, its operations, types and applications. Now, let us answer some of the most frequently asked questions about the stack pointer.
Conclusion
So, we have discussed a lot about the stack pointers in this article. We discussed the operations like push, pop and peek, the applications of stack pointer and the types of stack/stack pointers viz, memory stack and register stack. We hope that you liked the discussion and have understood the concepts. We hope to see you again soon at PrepBytes.
FAQs About Stack/Stack Pointer
1. What is a stack pointer really? Like, is it a register or a device or something else?
Stack Pointer (SP) is a register that is used to store the address of the topmost value of the stack memory of a processor. So, yes, it is a register.
2. Why the Stack Pointer is a 16 bit pointer in 8085?
Since the stack pointer is used to store memory address and the memory address are of 16 bits, hence the stack pointer size is of 16 bits.
3. What is the first address at which an element is stored in the Memory Stack?
4001 is the first memory location at which the stack pointer points and the elements are stored in a memory stack.