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.
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.
There are two types of Linear Stack Data Structure:
- 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.
A stack is a data structure with 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.
In an array-based stack implementation, the push operation is implemented by incrementing the index of the top element and storing the new element at that index. The pop operation is implemented by returning the value stored at the top index and then decrementing the index of the top element.
The following are some common operations implemented on the stack using an array:
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.
C array-based simple stack implementation:
#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);
}To implement a generic stack in C requires using void* pointers and function pointers to manage various data types since C does not support generics directly (like in C++ or Java). C array-based generic stack implementation:
#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;
}C++ array-based simple stack implementation:
#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;
}
}
}To implement a generic stack in C++ that can store any type of object or data type, you can use generics. In C++, generics are implemented 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. C++ array-based generic stack implementation:
#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;
}Java array-based simple stack implementation:
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();
}
}
}To implement a generic stack in Java that can store any type of object or data type, you can use generics. Generics allow you to create classes and methods that work with any data type while maintaining type safety. Java array-based generic stack implementation:
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);
}
}C# array-based simple stack implementation:
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();
}
}
}To implement a generic stack in C# that can store any type of object or data type, you can use generics. Generics allow you to create classes and methods that work with any data type while maintaining type safety. C# array-based generic stack implementation:
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();
}
}In a linked list-based implementation, the push operation is implemented by creating a new node with the new element and setting the next pointer of the current top node to the new node. The pop operation is implemented by setting the next pointer of the current top node to the next node and returning the value of the current top node.
The following are some common operations implemented on the stack using a linked list:
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.
C Linked List-based Simple Stack Implementation:
#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;
}To implement a generic stack in C requires using void* pointers and function pointers to manage various data types since C does not support generics directly (like in C++ or Java). C Linked List-based generic stack implementation:
#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;
}C++ Linked List-based Simple Stack Implementation:
#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;
}To implement a generic stack in C++ that can store any type of object or data type, you can use generics. In C++, generics are implemented 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. C++ Linked List-based generic stack implementation:
#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;
}C# Linked List-based Simple Stack Implementation:
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!
}
}To implement a generic stack in C# that can store any type of object or data type, you can use generics. Generics allow you to create classes and methods that work with any data type while maintaining type safety. C# Linked List-based generic stack implementation:
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"
}
}Java Linked List-based Simple Stack implementation:
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!
}
}To implement a generic stack in Java that can store any type of object or data type, you can use generics. Generics allow you to create classes and methods that work with any data type while maintaining type safety. Java linked list-based generic stack implementation:
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
}
}
