Algorithm for Stack ADT
1. Create a new stack data structure (e.g., an array or linked list) and set the stack pointer to -1 to indicate an empty stack.
2. Define the push operation to add a new element to the top of the stack:
a. Check if the stack is full (i.e., if the stack pointer is equal to the size of the stack minus 1).
b. If the stack is full, raise an error or resize the stack to allow for more elements.
c. If the stack is not full, increment the stack pointer and insert the new element at the position pointed to by the stack pointer.
3. Define the pop operation to remove the element from the top of the stack:
a. Check if the stack is empty (i.e., if the stack pointer is equal to -1).
b. If the stack is empty, raise an error or return a special value to indicate an empty stack.
c. If the stack is not empty, retrieve the value at the position pointed to by the stack pointer, decrement the stack pointer, and return the value.
4. Define the peek operation to retrieve the value of the top element without removing it:
a. Check if the stack is empty (i.e., if the stack pointer is equal to -1).
b. If the stack is empty, raise an error or return a special value to indicate an empty stack.
c. If the stack is not empty, retrieve the value at the position pointed to by the stack pointer and return the value.
5. Define the isEmpty operation to check if the stack is empty:
a. Check if the stack pointer is equal to -1.
b. If the stack pointer is equal to -1, return true to indicate an empty stack.
c. If the stack pointer is not equal to -1, return false to indicate a non-empty stack.
These operations can be implemented using various data structures, such as arrays or linked lists, and different programming languages have different syntax for implementing these operations.
stack_array[MAX_SIZE]
top = -1
function push(element):
if top == MAX_SIZE - 1:
print "Stack overflow"
return
top = top + 1
stack_array[top] = element
function pop():
if top == -1:
print "Stack underflow"
return
element = stack_array[top]
top = top - 1
return element
function peek():
if top == -1:
print "Stack is empty"
return
return stack_array[top]
function isEmpty():
return top == -1
C Program
#include <stdio.h>
#define MAX_SIZE 100
int stack_array[MAX_SIZE];
int top = -1;
void push(int element) {
if (top == MAX_SIZE - 1) {
printf("Stack overflow\n");
return;
}
top = top + 1;
stack_array[top] = element;
}
int pop() {
int element;
if (top == -1) {
printf("Stack underflow\n");
return -1;
}
element = stack_array[top];
top = top - 1;
return element;
}
int peek() {
if (top == -1) {
printf("Stack is empty\n");
return -1;
}
return stack_array[top];
}
int isEmpty() {
return top == -1;
}
int main() {
push(10);
push(20);
push(30);
printf("Top element is %d\n", peek());
printf("Popped element is %d\n", pop());
printf("Popped element is %d\n", pop());
printf("Top element is %d\n", peek());
return 0;
}
CPP Program
#include <iostream>
#define MAX_SIZE 100
using namespace std;
class Stack {
private:
int stack_array[MAX_SIZE];
int top;
public:
Stack() {
top = -1;
}
void push(int element) {
if (top == MAX_SIZE - 1) {
cout << "Stack overflow" << endl;
return;
}
top = top + 1;
stack_array[top] = element;
}
int pop() {
int element;
if (top == -1) {
cout << "Stack underflow" << endl;
return -1;
}
element = stack_array[top];
top = top - 1;
return element;
}
int peek() {
if (top == -1) {
cout << "Stack is empty" << endl;
return -1;
}
return stack_array[top];
}
bool isEmpty() {
return top == -1;
}
};
int main() {
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
cout << "Top element is " << stack.peek() << endl;
cout << "Popped element is " << stack.pop() << endl;
cout << "Popped element is " << stack.pop() << endl;
cout << "Top element is " << stack.peek() << endl;
return 0;
}
JAVA Program
public class Stack {
private int[] stackArray;
private int top;
private int maxSize;
public Stack(int size) {
maxSize = size;
stackArray = new int[maxSize];
top = -1;
}
public void push(int element) {
if (top == maxSize - 1) {
System.out.println("Stack overflow");
return;
}
top++;
stackArray[top] = element;
}
public int pop() {
int element;
if (top == -1) {
System.out.println("Stack underflow");
return -1;
}
element = stackArray[top];
top--;
return element;
}
public int peek() {
if (top == -1) {
System.out.println("Stack is empty");
return -1;
}
return stackArray[top];
}
public boolean isEmpty() {
return top == -1;
}
public static void main(String[] args) {
Stack stack = new Stack(100);
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Top element is " + stack.peek());
System.out.println("Popped element is " + stack.pop());
System.out.println("Popped element is " + stack.pop());
System.out.println("Top element is " + stack.peek());
}
}