Stack Implementation Using Array in DSA C++ - Time & Space Complexity

Time Complexity: Stack Implementation Using Array

O(1)

Understanding Time Complexity

We want to understand how fast the main operations of a stack work when using an array.

Specifically, how the time to push or pop items changes as the stack grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Stack {
  int arr[1000];
  int top = -1;
public:
  void push(int x) {
    if (top < 999) arr[++top] = x;
  }
  void pop() {
    if (top >= 0) top--;
  }
  int peek() {
    if (top >= 0) return arr[top];
    return -1;
  }
};
    

This code shows a stack using a fixed-size array with push, pop, and peek operations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each push or pop changes the top index once.
• How many times: Each operation runs once per call, no loops or recursion inside.

How Execution Grows With Input

Each push or pop does a simple step regardless of stack size.

Input Size (n)	Approx. Operations
10	10 steps for 10 pushes
100	100 steps for 100 pushes
1000	1000 steps for 1000 pushes

Pattern observation: The time grows directly with the number of operations, but each operation is constant time.

Final Time Complexity

Time Complexity: O(1)

This means each push or pop takes the same small amount of time no matter how many items are in the stack.

Common Mistake

[X] Wrong: "Push or pop takes longer as the stack gets bigger because it has to move many items."

[OK] Correct: The stack only changes the top index and stores or removes one item, no moving of all items happens.

Interview Connect

Knowing that stack operations are constant time helps you explain efficient data handling in many problems.

Self-Check

"What if the stack was implemented using a linked list instead of an array? How would the time complexity change?"

Practice

1. What is the main purpose of using an array in stack implementation?

easy

A. To store elements in a fixed-size linear structure

B. To allow random access to elements anywhere

C. To sort elements automatically

D. To store elements in a tree-like structure

Solution

1. Step 1: Understand stack storage

   A stack stores elements in a linear order, last-in first-out (LIFO).

2. Step 2: Role of array in stack

   An array provides a fixed-size linear structure to hold stack elements efficiently.

3. Final Answer:

   To store elements in a fixed-size linear structure -> Option A

4. Quick Check:

   Stack uses array for fixed linear storage [OK]

Hint: Stack uses array for fixed linear storage [OK]

Common Mistakes:

• Confusing stack with queue or tree
• Thinking array sorts elements automatically
• Assuming stack allows random access

2. Which of the following is the correct syntax to declare a stack array of size 10 in C++?

easy

A. stack int[10];

B. int stack[10];

C. int stack();

D. array stack[10];

Solution

1. Step 1: Recall C++ array declaration syntax

   In C++, arrays are declared as: type name[size];

2. Step 2: Match with options

   int stack[10]; matches correct syntax: int stack[10];

3. Final Answer:

   int stack[10]; -> Option B

4. Quick Check:

   C++ array declaration = int stack[10]; [OK]

Hint: Array declaration: type name[size]; [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Wrong order of type and name
• Using non-existent 'array' keyword

3. What will be the output after executing the following code?

int stack[5];
int top = -1;
// Push 10
stack[++top] = 10;
// Push 20
stack[++top] = 20;
// Pop
int x = stack[top--];
// Push 30
stack[++top] = 30;
// Print top element
std::cout << stack[top];

medium

A. Runtime error

B. 20

C. 10

D. 30

Solution

1. Step 1: Trace stack operations step-by-step

   Initially top = -1.
   Push 10: top=0, stack[0]=10
   Push 20: top=1, stack[1]=20
   Pop: x=stack[1]=20, top=0
   Push 30: top=1, stack[1]=30

2. Step 2: Identify top element after operations

   Top is 1, stack[1] = 30, so output is 30.

3. Final Answer:

   30 -> Option D

4. Quick Check:

   Last pushed after pop is 30 [OK]

Hint: Track top index changes carefully [OK]

Common Mistakes:

• Confusing push and pop order
• Not updating top correctly
• Assuming pop removes element permanently

4. Identify the error in the following stack push function using array:

void push(int stack[], int &top, int size, int value) {
  if (top == size) {
    std::cout << "Stack Overflow";
    return;
  }
  stack[++top] = value;
}

medium

A. No error, function is correct

B. The increment of top should be after assignment

C. The condition should be 'top == size - 1' to check overflow

D. The function should return a value

Solution

1. Step 1: Understand overflow condition

   Array indices go from 0 to size-1, so top can be max size-1.

2. Step 2: Check condition in code

   Condition 'top == size' is wrong; it should be 'top == size - 1' to prevent overflow.

3. Final Answer:

   The condition should be 'top == size - 1' to check overflow -> Option C

4. Quick Check:

   Overflow check uses top == size - 1 [OK]

Hint: Array max index = size - 1 for overflow check [OK]

Common Mistakes:

• Checking top == size instead of size - 1
• Incrementing top incorrectly
• Ignoring overflow condition

5. Given a stack implemented using an array of size 4, what will be the state of the stack after these operations?

push(5); push(10); pop(); push(15); push(20); push(25); pop();

Assume stack is initially empty and top = -1. Choose the correct stack content from bottom to top.

hard

A. 5 -> 15 -> 20 -> null

B. 5 -> 10 -> 15 -> 20 -> null

C. 5 -> 15 -> 20 -> 25 -> null

D. 10 -> 15 -> 20 -> null

Solution

1. Step 1: Execute operations step-by-step

   Start: top = -1, stack empty.
   push(5): top=0, stack[0]=5
   push(10): top=1, stack[1]=10
   pop(): removes 10, top=0
   push(15): top=1, stack[1]=15
   push(20): top=2, stack[2]=20
   push(25): top=3, stack[3]=25 (stack full)
   pop(): removes 25, top=2

2. Step 2: Final stack content

   Stack from bottom to top: 5 (index 0), 15 (index 1), 20 (index 2). So output is 5 -> 15 -> 20 -> null.

3. Final Answer:

   5 -> 15 -> 20 -> null -> Option A

4. Quick Check:

   Track push/pop changes carefully [OK]

Hint: Write each push/pop step to track stack state [OK]

Common Mistakes:

• Ignoring pop effects on top
• Assuming stack grows beyond size
• Confusing order of elements