Implementation of Stack Using Array
Before moving forward to implementation of stack using array, we must know more about stack.
A stack is defined as a linear data structure that follows LIFO (Last In First Out) method, that means the elements added at end of the stack will be removed first and the new order cannot be updated or changed.
A stack can be implemented in multiple ways.
Stack implementation using an array includes the following operation methods:
- Push (): It adds the element at the top of the stack in O (n) time.
- Pop (): It removes the top element from stack in O (n) time.
- Peak (): It is used for accessing the top element of stack by returning it in O(n) time.
Push Operation: Adding an Element to the Stack
This operation adds an element at the top of the stack and is known as the push operation.
It works in the following steps:
- It increments the top variable (the pointer that points to the top of the stack) and then starts to point towards a new memory location.
- Then, it adds the element at the new top, the new memory location and this increases the size of the stack.
Algorithm:
start
if top == n; ( implies the stack is full)
else
t = t + 1; (t=top)
stack (t) = new__item;
stop
Time Complexity:
Push operation in stack occurs in O(1) time.
Pop Operation: Deleting an Element from the Stack
This operation fetches the value by removing it from the top of the stack and is known as the pop() operation.
In the stack data structure while implementation of pop () operation in the array, instead of removing the data from the stack, the pointer shifts to a lower position in the stack and points to the further value, and similarly the size decreases.
*The pop () function returns the removed value.
Algorithm:
start
if t == 0; (that means the stack is empty)
else
top_item = stack(t);
t = t - 1;
stop
Peek Operation: Accesses the Top Element of Stack
By peek operation, the value of the element which is present at the top of the stack is returned without making any changes to it. If we try to use peek over an empty stack, then the stack goes underflow.
Algorithm:
start
if t == -1; (that means stack is empty)
else
item = stack[t];
return item;
stop
Code of Stack using Array in C:
#include <stdio.h>
#include <stdlib.h>
#define SIZE 4
int top = -1, inp_array[SIZE];
void push();
void pop();
void peek();
int main()
{
int choice;
while (1)
{
printf("\nPerform operations on the stack:");
printf("\n1.Push the element\n2.Pop the element\n3.peek\n4.End");
printf("\n\nEnter the choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
exit(0);
default:
printf("\nInvalid choice!!");
}
}
}
void push()
{
int x;
if (top == SIZE - 1)
{
printf("\nOverflow!!");
}
else
{
printf("\nEnter the element to be added onto the stack: ");
scanf("%d", &x);
top = top + 1;
inp_array[top] = x;
}
}
void pop()
{
if (top == -1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nPopped element: %d", inp_array[top]);
top = top - 1;
}
}
void peek()
{
if (top == -1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nElements present in the stack: \n");
for (int i = top; i>= 0; --i)
printf("%d\n", inp_array[i]);
}
}
Output:
Perform operations on the stack:
1.Push the element
2.Pop the element
3.peek
4.End
Enter the choice:
Now, you can enter the choices. Suppose, you enter 1 (push the element). Now, you enter the element to be added onto the stack is 3. So, the program execution, when you enter the choice 3 (peek the element), you can see that it shows “element present in the stack is 3.
Enter the choice: 1
Enter the element to be added onto the stack: 3
Perform operations on the stack:
1.Push the element
2.Pop the element
3.peek
4.End
Enter the choice: 3
Elements present in the stack:
3
Perform operations on the stack:
1.Push the element
2.Pop the element
3.peek
4.End
Enter the choice:
Java Example:
// Stack implementation in Java
class Stack {
// store elements of stack
private int arr[];
// represent top of stack
private int top;
// total capacity of the stack
private int capacity;
// Creating a stack
Stack(int size) {
// initialize the array
// initialize the stack variables
arr = new int[size];
capacity = size;
top = -1;
}
// push elements to the top of stack
public void push(int x) {
if (isFull()) {
System.out.println("Stack OverFlow");
// terminates the program
System.exit(1);
}
// insert element on top of stack
System.out.println("Inserting " + x);
arr[++top] = x;
}
// pop elements from top of stack
public int pop() {
// if stack is empty
// no element to pop
if (isEmpty()) {
System.out.println("STACK EMPTY");
// terminates the program
System.exit(1);
}
// pop element from top of stack
return arr[top--];
}
// return size of the stack
public int getSize() {
return top + 1;
}
// check if the stack is empty
public Boolean isEmpty() {
return top == -1;
}
// check if the stack is full
public Boolean isFull() {
return top == capacity - 1;
}
// display elements of stack
public void printStack() {
for (int i = 0; i<= top; i++) {
System.out.print(arr[i] + ", ");
}
}
public static void main(String[] args) {
Stack stack = new Stack(5);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.print("Stack: ");
stack.printStack();
// remove element from stack
stack.pop();
System.out.println("\nAfter popping out");
stack.printStack();
}
}
Output:
Inserting 1
Inserting 2
Inserting 3
Stack: 1, 2, 3,
After popping out 1, 2,
.