Stack Implementation Using Array in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a stack in data structures?

A stack is a collection where elements are added and removed in a last-in, first-out (LIFO) order. Think of a stack of plates where you add or remove the top plate only.

beginner

What does the 'push' operation do in a stack implemented using an array?

The 'push' operation adds a new element to the top of the stack (the end of the array).

beginner

What does the 'pop' operation do in a stack implemented using an array?

The 'pop' operation removes and returns the top element from the stack (the last element in the array).

intermediate

Why do we check for 'stack overflow' in an array-based stack?

Because the array has a fixed size, 'stack overflow' happens when we try to push an element but the stack is already full.

beginner

How do you check if the stack is empty in an array implementation?

We check if the top index is -1, which means no elements are in the stack.

In a stack implemented using an array, what does the 'top' variable represent?

A The number of empty spaces

B The index of the last added element

C The first element in the array

D The total size of the array

The 'top' variable points to the index of the last added element in the stack.

What happens if you try to pop from an empty stack?

A Does nothing and returns null

B Returns the bottom element

C Adds a new element

D Causes stack underflow error

Popping from an empty stack causes a stack underflow error because there is no element to remove.

Which operation adds an element to the stack?

A push

B peek

C pop

D delete

'push' adds an element to the top of the stack.

What is the time complexity of push and pop operations in an array-based stack?

A O(1)

B O(n)

C O(log n)

D O(n^2)

Both push and pop operations take constant time O(1) because they only add or remove the top element.

How do you check if the stack is full in an array implementation?

A top == 0

B top == -1

C top == array.length - 1

D array.length == 0

The stack is full when 'top' reaches the last index of the array, which is array.length - 1.

Explain how to implement a stack using an array and how push and pop operations work.

Think about how you add and remove plates from a stack.

Describe what happens when you try to push an element into a full stack and pop from an empty stack.

Consider the limits of the array size and empty condition.

Practice

1. What is the main characteristic of a stack data structure implemented using an array?

easy

A. It stores elements in sorted order

B. It follows First In First Out (FIFO) order

C. It allows random access to elements

D. It follows Last In First Out (LIFO) order

Solution

1. Step 1: Understand stack behavior

   A stack adds and removes elements from the same end, so the last element added is the first to be removed.

2. Step 2: Identify the order type

   This behavior is called Last In First Out (LIFO).

3. Final Answer:

   It follows Last In First Out (LIFO) order -> Option D

4. Quick Check:

   Stack = LIFO [OK]

Hint: Stack always removes the last added item first [OK]

Common Mistakes:

• Confusing stack with queue (FIFO)
• Thinking stack sorts elements
• Assuming random access like arrays

2. Which of the following is the correct way to push an element 'x' onto a stack implemented as an array named stack in TypeScript?

easy

A. stack.insert(x);

B. stack.pop(x);

C. stack.push(x);

D. stack.add(x);

Solution

1. Step 1: Recall array methods for stack push

   In TypeScript, to add an element at the end of an array, use the push method.

2. Step 2: Verify other options

   pop removes elements, insert and add are not valid array methods.

3. Final Answer:

   stack.push(x); -> Option C

4. Quick Check:

   Push uses .push() method [OK]

Hint: Use .push() to add elements to array stack [OK]

Common Mistakes:

• Using pop instead of push
• Using non-existent methods like insert or add
• Confusing push with pop

3. What will be the output of the following TypeScript code implementing a stack using an array?

const stack: number[] = [];
stack.push(10);
stack.push(20);
stack.pop();
stack.push(30);
console.log(stack);

medium

A. [10, 20, 30]

B. [10, 30]

C. [20, 30]

D. [30]

Solution

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

   Initially stack = []. After push(10), stack = [10]. After push(20), stack = [10, 20]. After pop(), top element 20 is removed, stack = [10]. After push(30), stack = [10, 30].

2. Step 2: Determine final stack state

   The console.log prints the current stack array: [10, 30].

3. Final Answer:

   [10, 30] -> Option B

4. Quick Check:

   Push and pop update stack correctly [OK]

Hint: Pop removes last pushed element, then push adds new [OK]

Common Mistakes:

• Forgetting pop removes last element
• Assuming pop removes first element
• Confusing order of push and pop

4. Identify the error in the following TypeScript code for stack pop operation and select the correct fix.

class Stack {
  private items: number[] = [];
  pop(): number {
    return this.items.pop();
  }
}

medium

A. pop() should check if stack is empty before popping

B. items array should be public, not private

C. pop() should return void, not number

D. No error, code is correct

Solution

1. Step 1: Analyze pop method behavior

   The pop() method of array returns number | undefined if empty. Returning directly without check can cause undefined return.

2. Step 2: Identify fix for empty stack

   To avoid returning undefined, pop() should check if items is empty before popping and handle that case.

3. Final Answer:

   pop() should check if stack is empty before popping -> Option A

4. Quick Check:

   Check empty before pop to avoid undefined [OK]

Hint: Always check stack empty before pop to avoid errors [OK]

Common Mistakes:

• Ignoring empty stack check
• Changing return type incorrectly
• Making items public unnecessarily

5. Given a stack implemented using an array, how would you implement a function reverseStack that reverses the elements in the stack without using any extra stack or array? Which approach is correct?

hard

A. Use recursion to pop all elements, then insert them at bottom recursively

B. Use a for loop to swap elements from start and end indices

C. Pop all elements into a new array, then push back in reverse order

D. Use a queue to dequeue and enqueue elements to reverse order

Solution

1. Step 1: Understand constraints

   No extra stack or array allowed, so iterative swapping or extra storage is not possible.

2. Step 2: Use recursion to reverse stack

   Recursion can pop all elements, then insert each element at the bottom of the stack recursively, effectively reversing it.

3. Step 3: Evaluate other options

   Use a for loop to swap elements from start and end indices requires direct index access which is not typical for stack abstraction. Pop all elements into a new array, then push back in reverse order uses extra array. Use a queue to dequeue and enqueue elements to reverse order uses queue, which is extra data structure.

4. Final Answer:

   Use recursion to pop all elements, then insert them at bottom recursively -> Option A

5. Quick Check:

   Recursion reverses stack without extra storage [OK]

Hint: Recursion can reverse stack by inserting at bottom [OK]

Common Mistakes:

• Using extra arrays or stacks against constraints
• Trying to swap elements directly in stack
• Using other data structures like queue