Implement a Stack Using an Array

65.9k
0

Design a stack data structure by using an array. A stack follows the Last In, First Out (LIFO) property, so the newest inserted value must be removed before older values.

The stack must support push, pop, peek, isEmpty, and size operations. A fixed capacity is given during stack creation. Push operations must report overflow when the array has no free cell. Pop and peek operations must report underflow or empty-stack behavior when no value is present.

The full-capacity check belongs to the array implementation only. isFull() is not a default stack operation, but the same check is useful inside push to prevent writing outside the array.

Example 1

Input: capacity = 4, operations = push(10), push(20), push(30), peek(), size(), pop(), peek(), size(), isEmpty()
Output: ["Pushed 10", "Pushed 20", "Pushed 30", "Top = 30", "Size = 3", "Popped 30", "Top = 20", "Size = 2", "Is Empty = false"]
Explanation: After three pushes, the top value equals 30 and the stack size equals 3. The pop operation removes 30, so the next top value equals 20 and the stack size becomes 2.

Example 2

Input: capacity = 2, operations = pop(), size(), push(5), push(6), push(7), peek(), size()
Output: ["Stack Underflow", "Size = 0", "Pushed 5", "Pushed 6", "Stack Overflow", "Top = 6", "Size = 2"]
Explanation: The first pop operation fails because the stack is empty. After two successful pushes, the array reaches full capacity, so the next push reports overflow. The size remains 2.

Approach

A stack needs access only to the most recently inserted value. An array already provides direct access by index, so one integer pointer can remember the current top position and preserve LIFO order.

The variable top starts at -1, meaning no cell is occupied. During push, top moves one step forward before storing the new value. During pop, the value at top is returned first, then top moves one step backward. Peek reads the same position without changing the stack, and size is always top + 1.

The full-capacity check is only an internal guard for the fixed array. Beginner stack APIs commonly expose push, pop, peek, isEmpty, and size; the array guard simply keeps push operations inside valid bounds.

Algorithm

  • Begin with a fixed-size array, a capacity value, and top = -1 so the empty stack state has a clear marker.

    • The array stores values from bottom to top.

    • The top pointer marks the latest inserted value.

  • For push(value), the array boundary is protected before insertion because a full array has no valid write position.

    • If top == capacity - 1, overflow is reported.

    • Otherwise, top is increased and value is stored.

  • For pop(), the empty-stack state is rejected before removal because no value exists at the top position.

    • If top == -1, underflow is reported.

    • Otherwise, the top value is saved and top is decreased.

  • For peek(), the same empty-stack guard is checked because reading from an empty stack has no valid answer.

    • If top == -1, empty-stack behavior is reported.

    • Otherwise, the value at top is returned unchanged.

  • For isEmpty(), the answer is taken from top == -1 so the stack state is checked without scanning the array.

    • A true result means no occupied stack cell exists.

    • A false result means at least one value is present.

  • For size(), the occupied-cell count is returned as top + 1 because valid stack values occupy indices 0 through top.

    • Empty stack size becomes 0.

    • After every successful push or pop, the count changes by one.

Dry Run

Stack Using Array

Stack Using Array

Solution

#include <bits/stdc++.h>
using namespace std;
class ArrayStack {
private:
vector<int> values;
int capacity;
int top;
public:
// Build an empty stack with fixed capacity.
ArrayStack(int cap) {
// Stack values are stored in fixed array order.
values.resize(cap);
// Capacity gives the maximum allowed stack size.
capacity = cap;
// Top starts before index 0 to mark emptiness.
top = -1;
}
// Insert a value at the stack top.
void push(int value, vector<string>& output) {
// Full capacity blocks another stack value.
if (top == capacity - 1) {
output.push_back("Stack Overflow");
return;
}
// Top moves forward to the next free position.
top = top + 1;
// New value becomes the latest stack value.
values[top] = value;
// Output records the successful push action.
output.push_back("Pushed " + to_string(value));
}
// Remove and return the current stack top.
void pop(vector<string>& output) {
// Empty stack blocks removal.
if (top == -1) {
output.push_back("Stack Underflow");
return;
}
// Top value is saved before pointer movement.
int removedValue = values[top];
// Top moves backward after removal.
top = top - 1;
// Output records the removed value.
output.push_back("Popped " + to_string(removedValue));
}
// Read the current stack top without removal.
void peek(vector<string>& output) {
// Empty stack has no readable top value.
if (top == -1) {
output.push_back("Stack is Empty");
return;
}
// Top value is read without pointer movement.
output.push_back("Top = " + to_string(values[top]));
}
// Check whether the stack has no values.
bool isEmpty() {
// Top at -1 means no stack value exists.
return top == -1;
}
// Return the current number of stack values.
int size() {
// Occupied cells equal top plus one.
return top + 1;
}
};
class Solution {
public:
// Return all observed stack operation results.
vector<string> runStackOperations() {
// Operation output is collected for the sample.
vector<string> output;
// Stack capacity bounds the array storage.
ArrayStack stack(4);
stack.push(10, output);
stack.push(20, output);
stack.push(30, output);
stack.peek(output);
output.push_back("Size = " + to_string(stack.size()));
stack.pop(output);
stack.peek(output);
output.push_back("Size = " + to_string(stack.size()));
output.push_back(string("Is Empty = ") + (stack.isEmpty() ? "true" : "false"));
return output;
}
};
// Driver code
int main() {
Solution obj;
vector<string> result = obj.runStackOperations();
for (string line : result) {
cout << line << "\n";
}
return 0;
}

Complexity Analysis

Time Complexity: O(1), each stack operation checks or updates only the top pointer and at most one array cell.

Space Complexity: O(cap), the fixed array stores up to cap values, where cap is the capacity supplied during stack creation. Extra pointer storage is O(1).

Interview follow-up Questions

The top pointer stores the index of the latest inserted value. Push, pop, and peek can reach the correct array cell directly through the pointer.

Stack

Read Similar Blogs

Stack

Sum of Subarray Ranges

Given an integer array nums , define the range of a non-empty contiguous subarray as the maximum element minus the minimum element. Return the sum of the ranges of all non-empty contiguous subarray...

86.7k
Stack

Introduction to Stack

Imagine a stack of plates in a kitchen. Whenever you add a new plate, you place it on the top. When you need a plate, you also take it from the top. You never remove a plate from the...

69.3k
Two PointerStackString

Reverse Every Word in a String

Input: s = "hello world" Output: "olleh dlrow" Explanation: hello becomes olleh , and world becomes dlrow . Input: s = " DSA is fun " Output: " ASD si nuf " Explanation: Each word is reversed, but...

83.2k
Comments0