Implementing a Stack using Array
A stack can be implemented efficiently using a fixed size array. Operations like push and pop have O(1) time complexity.
Java example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public class MyStack {
private int[] arr;
private int top;
public MyStack(int capacity) {
arr = new int[capacity];
}
public void push(int item) {
if (top == arr.length - 1) {
// Handle stack overflow
}
arr[++top] = item;
}
public int pop() {
if (top == -1) {
// Handle stack underflow
}
return arr[top--];
}
// Other methods like isFull(), isEmpty() etc.
}
|
C++ example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class MyStack {
private:
int arr[MAX_SIZE];
int top;
public:
MyStack() {
top = -1;
}
void push(int item) {
if (top == MAX_SIZE - 1) {
// handle overflow
}
arr[++top] = item;
}
int pop() {
if (top == -1) {
// handle underflow
}
return arr[top--];
}
// Other methods
};
|
Python example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class MyStack:
def __init__(self, capacity):
self.arr = [None] * capacity
self.capacity = capacity
self.top = -1
def push(self, item):
if self.top == self.capacity - 1:
# Handle overflow
self.top += 1
self.arr[self.top] = item
def pop(self):
if self.top == -1:
# Handle underflow
item = self.arr[self.top]
self.top -= 1
return item
# Other methods
|
Modeling a stack with array provides simple and efficient implementation.
A Stack is a Last-In-First-Out (LIFO) data structure, which means that the last element added is the first one to be removed. Implementing a stack using an array involves using an array to hold the elements and an integer to keep track of the stack’s top position. The primary operations are push, which adds an element to the top, and pop, which removes the top element. Optionally, a peek operation can retrieve the top element without removing it.
Example Code
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| public class Stack {
private int[] arr;
private int top;
public Stack(int size) {
arr = new int[size];
top = -1;
}
public void push(int value) {
if (top == arr.length - 1) {
System.out.println("Stack is full");
return;
}
arr[++top] = value;
}
public int pop() {
if (top == -1) {
System.out.println("Stack is empty");
return -1;
}
return arr[top--];
}
public int peek() {
if (top == -1) {
System.out.println("Stack is empty");
return -1;
}
return arr[top];
}
}
|
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
using namespace std;
class Stack {
private:
int* arr;
int top;
int size;
public:
Stack(int size) : size(size), top(-1) {
arr = new int[size];
}
void push(int value) {
if (top == size - 1) {
cout << "Stack is full" << endl;
return;
}
arr[++top] = value;
}
int pop() {
if (top == -1) {
cout << "Stack is empty" << endl;
return -1;
}
return arr[top--];
}
int peek() {
if (top == -1) {
cout << "Stack is empty" << endl;
return -1;
}
return arr[top];
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Stack:
def __init__(self, size):
self.arr = [None] * size
self.top = -1
self.size = size
def push(self, value):
if self.top == self.size - 1:
print("Stack is full")
return
self.top += 1
self.arr[self.top] = value
def pop(self):
if self.top == -1:
print("Stack is empty")
return None
val = self.arr[self.top]
self.top -= 1
return val
def peek(self):
if self.top == -1:
print("Stack is empty")
return None
return self.arr[self.top]
|
These examples show how to implement a stack using an array in Java, C++, and Python. The array’s length sets the stack’s maximum capacity, and an integer top is used to indicate the current stack top. The push, pop, and peek operations manipulate this top variable accordingly.