Linear Stack
A Stack is a fundamental data structure in computer science that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. A stack is used in scenarios where you need to manage data in a reverse or nested order, such as function call management in programming, undo/redo features, and expression evaluation.
A stack has several key characteristics that make it unique and useful in various computational scenarios. Here are its main characteristics:
- LIFO Principle: Stacks operate based on the Last In, First Out (LIFO) principle, where the most recently added element is the first one to be removed.
- Single Access Point: Stacks have a single access point, typically referred to as the top of the stack, where all push and pop operations occur.
- Efficient Operations: Push, pop, and peek operations on stacks typically have a time complexity of \(O(1)\), making them efficient for certain applications.
- Limited Access: Stacks support limited access to elements. In most cases, only the top element of the stack is accessible for modification or removal.
Suppose we want to store the elements in a stack and let's assume that stack is empty. We have taken the stack of size 3 in which we are pushing the elements one by one until the stack becomes full.
Since our stack is full as the size of the stack is 3. In the above cases, we can observe that it goes from the top to the bottom when we were entering the new element in the stack. The stack gets filled up from the bottom to the top.
When we perform the delete operation on the stack, there is only one way for entry and exit as the other end is closed. It follows the LIFO pattern, which means that the value entered first will be removed last. In the above case, the value 3 is entered first, so it will be removed only after the deletion of all the other elements.
When classifying Linear Stacks based on their implementation, there are two main types:
- Fixed Size Linear Stack: A fixed size linear stack has a fixed size and cannot grow or shrink dynamically. If the stack is full and an attempt is made to add an element to it, an overflow error occurs. If the stack is empty and an attempt is made to remove an element from it, an underflow error occurs. This type of stack is implemented using an array. The array size is fixed, so elements are added sequentially in the array.
- Dynamic Size Linear Stack: A dynamic size linear stack can grow or shrink dynamically. When the stack is full, it automatically increases its size to accommodate the new element, and when the stack is empty, it decreases its size. This type of stack is implemented using a linked list, as it allows for easy resizing of the stack.
When classifying Linear Stacks based on the types of data they handle, they can be categorized into:
- Homogeneous Stack: A stack where all the elements are of the same data type.
- Heterogeneous Stack (Generic Stack): A stack that can handle different data types, allowing elements of various types (e.g., integers, floats, strings, or custom objects) to coexist.
Array-based Linear Stack
An Array-based Linear Stack is a stack implementation that uses an array to store elements in a linear order.
Here's a detailed breakdown of common stack operations implemented using an array-based stack:
push():
- Description: Adds an element to the top of the stack. If the stack is full then the overflow condition occurs.
- Time complexity: constant time i.e. \(O(1)\), it simply adds an element to the top of the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
pop():
- Description: Removes the element from the top of the stack and returns it. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
- Time complexity: constant time i.e. \(O(1)\), it simply remove an element from the top of the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
isEmpty():
- Description: Checks whether the stack is empty.
- Time complexity: constant time i.e. \(O(1)\), it simply checks the index of the top pointer is empty.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
isFull():
- Description: Checks if the stack has reached its maximum capacity.
- Time complexity: constant time i.e. \(O(1)\), it simply checks the index of the top pointer is at the maximum capacity of the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
peek():
- Description: Returns the element at the top of the stack without removing it.
- Time complexity: constant time i.e. \(O(1)\), it simply accesses the top of the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
size():
- Description: Returns the number of elements currently in the stack.
- Time complexity: constant time i.e. \(O(1)\), it simply gets the number of elements in the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
clear():
- Description: Resets the stack to its initial empty state.
- Time complexity: constant time i.e. \(O(1)\), it simply decrements the top pointer of the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
display():
- Description: Prints all the elements available in the stack.
- Time complexity: linear time i.e. \(O(n)\), it performs loop through the elements in the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
Array-based Homogeneous Linear Stack Implementation
Here is the Array-based Homogeneous Linear Stack implementation in C:
#include <stdio.h>
#include <stdlib.h>
struct Stack {
int* stack;
int top;
int maxSize;
}
struct Stack* createStack(int size) {
struct Stack* s = (struct Stack*)malloc(sizeof(struct Stack));
s->maxSize = size;
s->stack = (int*)malloc(s->maxSize * sizeof(int));
s->top = -1;
return s;
}
void push(struct Stack* s, int element) {
if (s->top == s->maxSize - 1) {
printf("Stack Overflow\n");
return;
}
printf("Pushed %d to stack\n", element);
s->stack[++(s->top)] = element;
}
int pop(struct Stack* s) {
if (s->top == -1) {
printf("Stack Underflow\n");
return -1;
}
printf("Popped %d from stack\n", s->stack[s->top]);
return s->stack[(s->top)--];
}
int isFull(struct Stack* s) {
return s->top == s->maxSize - 1;
}
int isEmpty(struct Stack* s) {
return s->top == -1;
}
int peek(struct Stack* s) {
if (isEmpty(s)) {
return -1;
}
return s->stack[s->top];
}
int size(struct Stack* s) {
return s->top + 1;
}
void clear(struct Stack* s) {
s->top = -1;
printf("Stack is cleared!\n");
}
void display(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
} else {
for (int i = 0; i <= s->top; i++) {
if (i == s->top)
printf("%d", s->stack[i]);
else
printf("%d, ", s->stack[i]);
}
printf("\n");
}
}
void freeStack(struct Stack* s) {
free(s->stack);
free(s);
}Here is the Array-based Homogeneous Linear Stack implementation in C++:
#include <iostream>
using namespace std;
class Stack {
private:
int* stack;
int top;
int maxSize;
public:
Stack(int size) {
maxSize = size;
stack = new int[maxSize];
top = -1;
}
~Stack() {
delete[] stack;
}
void push(int element) {
if (top == maxSize - 1) {
cout << "Stack Overflow" << endl;
return;
}
cout << "Pushed " << element << " to stack" << endl;
stack[++top] = element;
}
int pop() {
if (IsEmpty()) {
cout << "Stack Underflow" << endl;
return -1;
}
cout << "Popped " << stack[top] << " from stack" << endl;
return stack[top--];
}
bool isFull() {
return top == maxSize - 1;
}
bool isEmpty() {
return top == -1;
}
int peek() {
if (IsEmpty()) {
return -1;
}
return stack[top];
}
int size() {
return top + 1;
}
void clear() {
top = -1;
cout << "Stack is cleared!" << endl;
}
void display() {
if (IsEmpty()) {
cout << "Stack is empty!" << endl;
} else {
for (int i = 0; i <= top; i++) {
if (i == top)
cout << stack[i];
else
cout << stack[i] << ", ";
}
cout << endl;
}
}
}Here is the Array-based Homogeneous Linear Stack implementation in Java:
import java.lang;
public class Stack {
private int[] stack;
private int top;
private int maxSize;
public Stack(int size) {
maxSize = size;
stack = new int[maxSize];
top = -1;
}
public void push(int element) {
if (top == maxSize - 1) {
System.out.println("Stack Overflow");
return;
}
System.out.println("Pushed " + element + " to stack");
stack[++top] = element;
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow");
return -1;
}
System.out.println("Popped " + stack[top] + " from stack");
return stack[top--];
}
public boolean isFull() {
return top == maxSize - 1;
}
public boolean isEmpty() {
return top == -1;
}
public int peek() {
if (isEmpty()) {
return -1;
}
return stack[top];
}
public int size() {
return top + 1;
}
public void clear() {
top = -1;
System.out.println("Stack is cleared!");
}
public void display() {
if (isEmpty()) {
System.out.println("Stack is empty!");
} else {
for (int i = 0; i <= top; i++) {
if (i == top)
System.out.print(stack[i]);
else
System.out.print(stack[i] + ", ");
}
System.out.println();
}
}
}Here is the Array-based Homogeneous Linear Stack implementation in C#:
using System;
class Stack {
private int[] stack;
private int top;
private int maxSize;
public Stack(int size) {
maxSize = size;
stack = new int[maxSize];
top = -1;
}
public void Push(int element) {
if (top == maxSize - 1) {
Console.WriteLine("Stack Overflow");
return;
}
Console.WriteLine($"Pushed {element} to stack");
stack[++top] = element;
}
public int Pop() {
if (isEmpty()) {
Console.WriteLine("Stack Underflow");
return -1;
}
Console.WriteLine($"Popped {stack[top]} from stack");
return stack[top--];
}
public bool IsFull() {
return top == maxSize - 1;
}
public bool IsEmpty() {
return top == -1;
}
public int Peek() {
if (isEmpty()) {
return -1;
}
return stack[top];
}
public int Size()
{
return top + 1;
}
public void Clear()
{
top = -1; // Reset the stack to its initial empty state
Console.WriteLine("Stack is cleared!");
}
public void Display()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
}
else
{
for (int i = 0; i <= top; i++)
{
if (i == top)
Console.Write(stack[i]);
else
Console.Write(stack[i] + ", ");
}
Console.WriteLine();
}
}
}Array-based Heterogeneous/Generic Linear Stack Implementation
C does not support generics directly, unlike languages such as C++ or Java. However, you can still implement generic-like behavior in C by using void* pointers and other techniques, like function pointers, to achieve flexibility with different data types.
Here is the Array-based Generic Linear Stack implementation in C:
#include <stdio.h>
#include <stdlib.h>
struct StackElement {
void* data;
char* toString;
};
struct Stack {
struct StackElement* stack;
int top;
int maxSize;
};
struct Stack* createStack(int size) {
struct Stack* s = (struct Stack*)malloc(sizeof(struct Stack));
s->maxSize = size;
s->stack = (struct StackElement*)malloc(s->maxSize * sizeof(struct StackElement));
s->top = -1;
return s;
}
void push(struct Stack* s, struct StackElement element) {
if (s->top == s->maxSize - 1) {
printf("Stack Overflow\n");
return;
}
printf("Pushed %s to stack\n", (char*)element.toString);
s->stack[++(s->top)] = element;
}
struct StackElement pop(struct Stack* s) {
if (s->top == -1) {
printf("Stack Underflow\n");
struct StackElement emptyElement;
emptyElement.data = NULL;
emptyElement.toString = "";
return emptyElement;
}
printf("Popped %s from stack\n", (char*)s->stack[s->top].toString);
return s->stack[s->top--];
}
int isFull(struct Stack* s) {
return s->top == s->maxSize - 1;
}
int isEmpty(struct Stack* s) {
return s->top == -1;
}
struct StackElement peek(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
struct StackElement emptyElement;
emptyElement.data = NULL;
emptyElement.toString = "";
return emptyElement;
}
return s->stack[s->top];
}
int size(struct Stack* s) {
return s->top + 1;
}
void clear(struct Stack* s) {
s->top = -1;
printf("Stack is cleared!\n");
}
void display(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
} else {
for (int i = 0; i <= s->top; i++) {
printf("%s", (char*)s->stack[s->top].toString);
if (i < s->top) printf(", ");
}
printf("\n");
}
}
void freeStack(struct Stack* s) {
free(s->stack);
free(s);
}
struct Car {
char model[20];
int year;
};
struct Person {
char name[20];
int age;
};
int main() {
struct Car tesla = {"Tesla", 2020};
struct Car toyota = {"Toyota", 2019};
struct Car honda = {"Honda", 2020};
struct StackElement carElement;
struct Stack* carStack = createStack(5);
carElement.data = &tesla;
carElement.toString = "Car{model:\"Tesla\",year:2020}";
push(carStack, carElement);
carElement.data = &toyota;
carElement.toString = "Car{model:\"Toyota\",year:2019}";
push(carStack, carElement);
carElement.data = &honda;
carElement.toString = "Car{model:\"Honda\",year:2020}";
push(carStack, carElement);
pop(carStack);
display(carStack);
freeStack(carStack);
struct Person alice = {"Alice", 30};
struct Person john = {"John", 19};
struct Person albert = {"Albert", 28};
struct Person robert = {"Robert", 20};
struct StackElement personElement;
struct Stack* personStack = createStack(5);
personElement.data = &alice;
personElement.toString = "Person{name:\"Alice\",age:30}";
push(personStack, personElement);
personElement.data = &john;
personElement.toString = "Person{name:\"John\",age:19}";
push(personStack, personElement);
personElement.data = &albert;
personElement.toString = "Person{name:\"Albert\",age:28}";
push(personStack, personElement);
personElement.data = &robert;
personElement.toString = "Person{name:\"Robert\",age:20}";
push(personStack, personElement);
pop(personStack);
display(personStack);
freeStack(personStack);
return 0;
}In C++, you can easily implement a generic stack using templates. Templates allow the creation of classes, functions, and even member functions that can work with any data type, specified when the object or function is instantiated. Templates in C++ allow you to define generic classes and functions that can work with any data type.
Here is the Array-based Generic Linear Stack implementation in C++:
#include <iostream>
using namespace std;
template <typename T>
class Stack {
private:
T* stack;
int top;
int maxSize;
public:
Stack(int size) {
maxSize = size;
stack = new T[maxSize];
top = -1;
}
~Stack() {
delete[] stack;
}
void push(T element) {
if (top == maxSize - 1) {
cout << "Stack Overflow" << endl;
return;
}
stack[++top] = element;
cout << "Pushed " << element << " to stack" << endl;
}
T pop() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
return T();
}
cout << "Popped " << stack[top] << " from stack" << endl;
return stack[top--];
}
bool isFull() {
return top == maxSize - 1;
}
bool isEmpty() {
return top == -1;
}
T peek() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
return T();
}
return stack[top];
}
int size() {
return top + 1;
}
void clear() {
top = -1;
cout << "Stack is cleared!" << endl;
}
void display() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
} else {
for (int i = 0; i <= top; i++) {
if (i == top)
cout << stack[i];
else
cout << stack[i] << ", ";
}
cout << endl;
}
}
};
int main() {
// Integer stack
Stack<int> intStack(5);
intStack.push(10);
intStack.push(20);
intStack.display();
intStack.pop();
intStack.display();
// String stack
Stack<string> stringStack(3);
stringStack.push("Hello");
stringStack.push("World");
stringStack.display();
stringStack.pop();
stringStack.display();
// Double stack
Stack<double> doubleStack(4);
doubleStack.push(99.9);
doubleStack.push(123.45);
doubleStack.display();
doubleStack.pop();
doubleStack.display();
return 0;
}In Java, you can create a generic stack using Generics, which allows you to define a stack that can hold elements of any type.
Here is the Array-based Generic Linear Stack implementation in Java:
import java.lang;
public class Stack<T> {
private T[] stack;
private int top;
private int maxSize;
public Stack(int size) {
maxSize = size;
stack = (T[]) new Object[maxSize];
top = -1;
}
public void push(T element) {
if (top == maxSize - 1) {
System.out.println("Stack Overflow");
return;
}
stack[++top] = element;
System.out.println("Pushed " + element + " to stack");
}
public T pop() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return;
}
System.out.println("Popped " + stack[top] + " from stack");
return stack[top--];
}
public boolean isFull() {
return top == maxSize - 1;
}
public boolean isEmpty() {
return top == -1;
}
public T peek() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return;
}
return stack[top];
}
public int size() {
return top + 1;
}
public void clear() {
top = -1;
System.out.println("Stack is cleared!");
}
public void display() {
if (isEmpty()) {
System.out.println("Stack is empty!");
} else {
for (int i = 0; i <= top; i++) {
if (i == top)
System.out.print(stack[i]);
else
System.out.print(stack[i] + ", ");
}
System.out.println();
}
}
}
class Program {
static void Main() {
Stack<Person> personStack = new Stack<Person>(5);
Person p1 = new Person("Alice", 30);
Person p2 = new Person("Bob", 25);
personStack.Push(p1);
personStack.Push(p2);
}
}In C#, you can implement a generic stack using generics, which allows the stack to hold elements of any data type.
Here is the Array-based Generic Linear Stack implementation in C#:
using System;
class Stack<T>
{
private T[] stack;
private int top;
private int maxSize;
public Stack(int size)
{
maxSize = size;
stack = new T[maxSize];
top = -1;
}
public void Push(T element)
{
if (top == maxSize - 1)
{
Console.WriteLine("Stack Overflow");
return;
}
Console.WriteLine($"Pushed {element} to stack");
stack[++top] = element;
}
public T Pop()
{
if (IsEmpty())
{
Console.WriteLine("Stack Underflow");
return default(T);
}
Console.WriteLine($"Popped {stack[top]} from stack");
return stack[top--];
}
public bool IsFull() {
return top == maxSize - 1;
}
public bool IsEmpty()
{
return top == -1;
}
public T Peek()
{
if (IsEmpty())
{
return default(T);
}
return stack[top];
}
public int Size()
{
return top + 1;
}
public void Clear()
{
top = -1;
Console.WriteLine("Stack is cleared!");
}
public void Display()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
}
else
{
for (int i = 0; i <= top; i++)
{
if (i == top)
Console.Write(stack[i]);
else
Console.Write(stack[i] + ", ");
}
Console.WriteLine();
}
}
}
class Program
{
static void Main()
{
Stack<int> intStack = new Stack<int>(5);
intStack.Push(10);
intStack.Push(20);
intStack.Pop();
intStack.Pop();
intStack.Pop();
Stack<string> stringStack = new Stack<string>(5);
stringStack.Push("Hello");
stringStack.Push("World");
stringStack.Pop();
stringStack.Pop();
stringStack.Pop();
}
}Linked list-based Linear Stack
A linked list-based linear stack is a stack implementation that uses a linked list to store elements instead of an array. This type of stack offers dynamic memory allocation, meaning the size of the stack can grow or shrink dynamically as elements are pushed and popped, unlike array-based stacks which have a fixed size.
Here's a detailed breakdown of common stack operations implemented using an array-based stack:
push():
- Description: Adds an element to the top of the stack. If the stack is full then the overflow condition occurs.
- Time complexity: constant time i.e. \(O(1)\), it simply adds an element to the top of the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
pop():
- Description: Removes the element from the top of the stack and returns it. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
- Time complexity: constant time i.e. \(O(1)\), it simply remove an element from the top of the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
isEmpty():
- Description: Checks whether the stack is empty.
- Time complexity: constant time i.e. \(O(1)\), it simply checks the index of the top pointer is empty.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
peek():
- Description: Returns the element at the top of the stack without removing it.
- Time complexity: constant time i.e. \(O(1)\), it simply accesses the top of the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
size():
- Description: Returns the number of elements currently in the stack.
- Time complexity: constant time i.e. \(O(1)\), it simply gets the number of elements in the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
clear():
- Description: Resets the stack to its initial empty state.
- Time complexity: linear time i.e. \(O(n)\), it performs loop through the elements in the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
display():
- Description: Prints all the elements available in the stack.
- Time complexity: linear time i.e. \(O(n)\), it performs loop through the elements in the stack.
- Space complexity: constant space i.e. \(O(1)\), no extra space is required.
Linked list-based Homogeneous Linear Stack Implementation
Here is the Linked list-based Homogeneous Linear Stack implementation in C:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Stack {
struct Node* top;
int size;
};
struct Stack* createStack() {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->top = NULL;
stack->size = 0;
return stack;
}
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void push(struct Stack* stack, int data) {
struct Node* newNode = createNode(data);
newNode->next = stack->top;
stack->top = newNode;
stack->size++;
printf("Pushed %d to stack\n", data);
}
int pop(struct Stack* stack) {
if (stack->top == NULL) {
printf("Stack Underflow\n");
return -1;
}
struct Node* temp = stack->top;
int poppedData = temp->data;
stack->top = temp->next;
free(temp);
stack->size--;
printf("Popped %d from stack\n", poppedData);
return poppedData;
}
int peek(struct Stack* stack) {
if (stack->top == NULL) {
printf("Stack is empty\n");
return -1;
}
return stack->top->data;
}
int isEmpty(struct Stack* stack) {
return stack->top == NULL;
}
int size(struct Stack* stack) {
return stack->size;
}
void clear(struct Stack* stack) {
while (!isEmpty(stack)) {
pop(stack);
}
printf("Stack is cleared!\n");
}
void display(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return;
}
struct Node* temp = stack->top;
while (temp != NULL) {
printf("%d", temp->data);
if (temp->next != NULL) {
printf(" -> ");
}
temp = temp->next;
}
printf("\n");
}
void freeStack(struct Stack* stack) {
clear(stack);
free(stack);
}
int main() {
struct Stack* stack = createStack();
push(stack, 10);
push(stack, 20);
push(stack, 30);
display(stack);
pop(stack);
display(stack);
printf("Top element is: %d\n", peek(stack));
printf("Size of stack: %d\n", size(stack));
clear(stack);
display(stack);
freeStack(stack);
return 0;
}Here is the Linked list-based Homogeneous Linear Stack implementation in C++:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class Stack {
private:
Node* top;
int size;
public:
Stack() {
top = nullptr;
size = 0;
}
~Stack() {
while (top != nullptr) {
pop();
}
}
void push(int element) {
Node* newNode = new Node();
newNode->data = element;
newNode->next = top;
top = newNode;
size++;
cout << "Pushed " << element << " to stack" << endl;
}
int pop() {
if (isEmpty()) {
cout << "Stack Underflow" << endl;
return -1;
}
Node* temp = top;
int poppedData = temp->data;
top = top->next;
delete temp;
size--;
cout << "Popped " << poppedData << " from stack" << endl;
return poppedData;
}
int peek() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
return -1;
}
return top->data;
}
bool isEmpty() {
return top == nullptr;
}
void clear() {
while (!isEmpty()) {
pop();
}
cout << "Stack is cleared!" << endl;
}
void display() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
} else {
Node* current = top;
while (current != nullptr) {
cout << current->data;
if (current->next != nullptr)
cout << ", ";
current = current->next;
}
cout << endl;
}
}
int getSize() {
return size;
}
};
int main() {
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
stack.display(); // Outputs: 30, 20, 10
stack.pop(); // Outputs: Popped 30 from stack
stack.display(); // Outputs: 20, 10
cout << "Top element is: " << stack.peek() << endl; // Outputs: 20
cout << "Stack size is: " << stack.getSize() << endl; // Outputs: 2
stack.clear();
stack.display(); // Outputs: Stack is empty!
return 0;
}Here is the Linked list-based Homogeneous Linear Stack implementation in C#:
using System;
class Node {
public int data;
public Node next;
}
class Stack {
private Node top;
private int size;
public Stack() {
top = null;
size = 0;
}
public void Push(int element) {
Node newNode = new Node();
newNode.data = element;
newNode.next = top;
top = newNode;
size++;
Console.WriteLine($"Pushed {element} to stack");
}
public int Pop() {
if (IsEmpty()) {
Console.WriteLine("Stack Underflow");
return -1;
}
int poppedData = top.data;
top = top.next;
size--;
Console.WriteLine($"Popped {poppedData} from stack");
return poppedData;
}
public int Peek() {
if (IsEmpty()) {
Console.WriteLine("Stack is empty!");
return -1;
}
return top.data;
}
public bool IsEmpty() {
return top == null;
}
public int Size() {
return size;
}
public void Clear() {
top = null;
size = 0;
Console.WriteLine("Stack is cleared!");
}
public void Display() {
if (IsEmpty()) {
Console.WriteLine("Stack is empty!");
} else {
Node current = top;
while (current != null) {
Console.Write(current.data);
if (current.next != null) {
Console.Write(", ");
}
current = current.next;
}
Console.WriteLine();
}
}
}
class Program {
static void Main() {
Stack stack = new Stack();
stack.Push(10);
stack.Push(20);
stack.Push(30);
stack.Display(); // Outputs: 30, 20, 10
stack.Pop(); // Outputs: Popped 30 from stack
stack.Display(); // Outputs: 20, 10
Console.WriteLine("Top element is: " + stack.Peek()); // Outputs: 20
Console.WriteLine("Stack size is: " + stack.Size()); // Outputs: 2
stack.Clear();
stack.Display(); // Outputs: Stack is empty!
}
}Here is the Linked list-based Homogeneous Linear Stack implementation in Java:
import java.lang;
public class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class Stack {
private Node top;
private int size;
public Stack() {
top = null;
size = 0;
}
public void push(int element) {
Node newNode = new Node(element);
newNode.next = top;
top = newNode;
size++;
System.out.println("Pushed " + element + " to stack");
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow");
return -1; // Return -1 if the stack is empty
}
int poppedData = top.data;
top = top.next;
size--;
System.out.println("Popped " + poppedData + " from stack");
return poppedData;
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return -1;
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
public int size() {
return size;
}
public void clear() {
top = null;
size = 0;
System.out.println("Stack is cleared!");
}
public void display() {
if (isEmpty()) {
System.out.println("Stack is empty!");
} else {
Node current = top;
while (current != null) {
System.out.print(current.data);
if (current.next != null) {
System.out.print(", ");
}
current = current.next;
}
System.out.println();
}
}
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.display(); // Outputs: 30, 20, 10
stack.pop(); // Outputs: Popped 30 from stack
stack.display(); // Outputs: 20, 10
System.out.println("Top element is: " + stack.peek()); // Outputs: 20
System.out.println("Stack size is: " + stack.size()); // Outputs: 2
stack.clear();
stack.display(); // Outputs: Stack is empty!
}
}Linked list-based Heterogeneous/Generic Linear Stack Implementation
Here is the Linked list-based Heterogeneous/Generic Linear Stack implementation in C:
#include <stdio.h>
#include <stdlib.h>
struct StackElement {
void* data;
char* toString;
};
struct Node {
struct StackElement element;
struct Node* next;
};
struct Stack {
struct Node* top;
int size;
};
struct Stack* createStack() {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->top = NULL;
stack->size = 0;
return stack;
}
struct Node* createNode(struct StackElement element) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->element = element;
newNode->next = NULL;
return newNode;
}
void push(struct Stack* stack, struct StackElement element) {
struct Node* newNode = createNode(element);
newNode->next = stack->top;
stack->top = newNode;
stack->size++;
printf("Pushed %s to stack\n", element.toString);
}
struct StackElement pop(struct Stack* stack) {
if (stack->top == NULL) {
printf("Stack Underflow\n");
struct StackElement emptyElement = {NULL, ""};
return emptyElement;
}
struct Node* temp = stack->top;
struct StackElement poppedElement = temp->element;
stack->top = temp->next;
free(temp);
stack->size--;
printf("Popped %s from stack\n", poppedElement.toString);
return poppedElement;
}
int isEmpty(struct Stack* stack) {
return stack->top == NULL;
}
struct StackElement peek(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
struct StackElement emptyElement = {NULL, ""};
return emptyElement;
}
return stack->top->element;
}
int size(struct Stack* stack) {
return stack->size;
}
void clear(struct Stack* stack) {
while (!isEmpty(stack)) {
pop(stack);
}
printf("Stack is cleared!\n");
}
void display(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return;
}
struct Node* temp = stack->top;
while (temp != NULL) {
printf("%s", temp->element.toString);
if (temp->next != NULL) {
printf(" -> ");
}
temp = temp->next;
}
printf("\n");
}
void freeStack(struct Stack* stack) {
clear(stack);
free(stack);
}
struct Car {
char model[20];
int year;
};
struct Person {
char name[20];
int age;
};
int main() {
struct Car tesla = {"Tesla", 2020};
struct Car toyota = {"Toyota", 2019};
struct Car honda = {"Honda", 2020};
struct StackElement carElement;
struct Stack* carStack = createStack(5);
carElement.data = &tesla;
carElement.toString = "Car{model:\"Tesla\",year:2020}";
push(carStack, carElement);
carElement.data = &toyota;
carElement.toString = "Car{model:\"Toyota\",year:2019}";
push(carStack, carElement);
carElement.data = &honda;
carElement.toString = "Car{model:\"Honda\",year:2020}";
push(carStack, carElement);
pop(carStack);
display(carStack);
freeStack(carStack);
struct Person alice = {"Alice", 30};
struct Person john = {"John", 19};
struct Person albert = {"Albert", 28};
struct Person robert = {"Robert", 20};
struct StackElement personElement;
struct Stack* personStack = createStack(5);
personElement.data = &alice;
personElement.toString = "Person{name:\"Alice\",age:30}";
push(personStack, personElement);
personElement.data = &john;
personElement.toString = "Person{name:\"John\",age:19}";
push(personStack, personElement);
personElement.data = &albert;
personElement.toString = "Person{name:\"Albert\",age:28}";
push(personStack, personElement);
personElement.data = &robert;
personElement.toString = "Person{name:\"Robert\",age:20}";
push(personStack, personElement);
pop(personStack);
display(personStack);
freeStack(personStack);
return 0;
}Here is the Linked list-based Heterogeneous/Generic Linear Stack implementation in C++:
#include <iostream>
using namespace std;
template <typename T>
class Node {
public:
T data;
Node* next;
Node(T data) {
this->data = data;
this->next = nullptr;
}
};
template <typename T>
class Stack {
private:
Node<T>* top;
int size;
public:
Stack() {
top = nullptr;
size = 0;
}
~Stack() {
clear();
}
void push(T element) {
Node<T>* newNode = new Node<T>(element);
newNode->next = top;
top = newNode;
size++;
cout << "Pushed " << element << " to stack" << endl;
}
T pop() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
return T();
}
Node<T>* temp = top;
T poppedElement = top->data;
top = top->next;
delete temp;
size--;
cout << "Popped " << poppedElement << " from stack" << endl;
return poppedElement;
}
bool isEmpty() {
return top == nullptr;
}
T peek() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
return T();
}
return top->data;
}
int getSize() {
return size;
}
void clear() {
while (!isEmpty()) {
pop();
}
cout << "Stack is cleared!" << endl;
}
void display() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
return;
}
Node<T>* temp = top;
while (temp != nullptr) {
cout << temp->data;
if (temp->next != nullptr)
cout << " -> ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
// Integer stack
Stack<int> intStack;
intStack.push(10);
intStack.push(20);
intStack.display();
intStack.pop();
intStack.display();
// String stack
Stack<string> stringStack;
stringStack.push("Hello");
stringStack.push("World");
stringStack.display();
stringStack.pop();
stringStack.display();
// Double stack
Stack<double> doubleStack;
doubleStack.push(99.9);
doubleStack.push(123.45);
doubleStack.display();
doubleStack.pop();
doubleStack.display();
return 0;
}Here is the Linked list-based Heterogeneous/Generic Linear Stack implementation in C#:
using System;
class Node<T>
{
public T data { get; set; }
public Node<T> next { get; set; }
public Node(T data)
{
data = data;
next = null;
}
}
class Stack<T>
{
private Node<T> top;
private int size;
public Stack()
{
top = null;
size = 0;
}
public void Push(T element)
{
Node<T> newNode = new Node<T>(element);
newNode.next = top;
top = newNode;
size++;
Console.WriteLine($"Pushed {element} to stack");
}
public T Pop()
{
if (IsEmpty())
{
Console.WriteLine("Stack Underflow");
return default(T);
}
T poppedElement = top.data;
top = top.next;
size--;
Console.WriteLine($"Popped {poppedElement} from stack");
return poppedElement;
}
public bool IsEmpty()
{
return top == null;
}
public T Peek()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
return default(T);
}
return top.data;
}
public int Size()
{
return size;
}
public void Clear()
{
top = null;
size = 0;
Console.WriteLine("Stack is cleared!");
}
public void Display()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
}
else
{
Node<T> current = top;
while (current != null)
{
Console.Write(current.data);
if (current.next != null)
Console.Write(" -> ");
current = current.next;
}
Console.WriteLine();
}
}
}
class Program
{
static void Main()
{
// Integer stack
Stack<int> intStack = new Stack<int>();
intStack.Push(10);
intStack.Push(20);
intStack.Pop();
intStack.Pop();
intStack.Pop(); // This will print "Stack Underflow"
// String stack
Stack<string> stringStack = new Stack<string>();
stringStack.Push("Hello");
stringStack.Push("World");
stringStack.Display();
stringStack.Pop();
stringStack.Display();
stringStack.Pop();
stringStack.Pop(); // This will print "Stack Underflow"
}
}Here is the Linked list-based Heterogeneous/Generic Linear Stack implementation in Java:
import java.lang;
public class Node<T> {
public T data;
public Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
public class Stack<T> {
private Node<T> top;
private int size;
public Stack() {
top = null;
size = 0;
}
public void push(T element) {
Node<T> newNode = new Node<T>(element);
newNode.next = top;
top = newNode;
size++;
System.out.println("Pushed " + element + " to stack");
}
public T pop() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return null;
}
T poppedElement = top.data;
top = top.next;
size--;
System.out.println("Popped " + poppedElement + " from stack");
return poppedElement;
}
public boolean isEmpty() {
return top == null;
}
public T peek() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return null;
}
return top.data;
}
public int size() {
return size;
}
public void clear() {
top = null;
size = 0;
System.out.println("Stack is cleared!");
}
public void display() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return;
}
Node<T> current = top;
while (current != null) {
System.out.print(current.data);
if (current.next != null) {
System.out.print(" -> ");
}
current = current.next;
}
System.out.println();
}
}
public class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Person{name='" + name + "', age=" + age + '}';
}
}
public class Program {
public static void main(String[] args) {
Stack<Person> personStack = new Stack<Person>();
Person p1 = new Person("Alice", 30);
Person p2 = new Person("Bob", 25);
personStack.push(p1);
personStack.push(p2);
personStack.display(); // Displays all elements in the stack
personStack.pop(); // Removes the top element from the stack
personStack.display(); // Displays the stack after pop
}
}
