Implement Stack using Array

Implement a stack (last-in, first-out) backed by an array, supporting two operations:

push(x) — add x to the top of the stack.
pop() — remove and return the top element; if the stack is empty, return -1.

You'll be given a sequence of operations; the first names the class (its constructor). Each pop reports its result; push and the constructor report nothing.

Hints

· Stuck? Reveal one nudge at a time.

Which end of an array supports O(1) add and remove?

Treat the last element as the top: push appends, pop removes from the end.

Guard pop against an empty stack by returning -1.

Common doubts

Appending and removing at the end are amortized O(1). Removing from the front would shift every element, costing O(n).

By this problem's convention, it returns -1 instead of raising an error — check the size before removing.

Interview follow-ups

· What an interviewer asks next.

Preallocate an array and keep a top index; push writes at top and increments, pop reads and decrements. You handle overflow yourself.

A linked list pushes/pops at the head with guaranteed O(1) (no resizing), at the cost of a node allocation and pointer per element.

Fun facts

The call stack your program runs on is exactly this structure — push a frame on call, pop it on return.
'Stack' is one of the oldest data structures, formalized alongside the first compilers to evaluate expressions.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: push(5), push(10), pop(), pop(), pop()
Output: 10, 5, -1
Two pushes, then three pops return 10, 5, and -1 (empty).

Example 2

Input: push(7), pop()
Output: 7
Push 7, then pop returns 7.

Constraints

- 1 <= number of operations <= 100 - 1 <= x <= 10^5 - pop() returns -1 if the stack is empty.

A stack is the simplest container with a discipline: last in, first out. Backed by a dynamic array, both operations are trivially O(1) — push appends to the end (the "top"), and pop removes from the end.

Prerequisites

Before you start

· Concepts used directly in the solution.

Dynamic array. An array that grows at the end in amortized O(1) — the natural home for a stack's top.

LIFO discipline. The last element pushed is the first popped.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The contract

“Which end is the top?”

The end of the array — appends and removals both happen there for O(1).

“What does pop return on an empty stack?”

-1, by this problem's convention, rather than erroring.

The ideal opening — say it like this

I'll keep a dynamic array and treat its last element as the top of the stack.

Push appends; pop removes and returns the last element.

If the array is empty, pop returns -1 instead of failing.

Understand the problem

Worked example — operations push 5, push 10, pop, pop, pop

push 5   -> arr = [5]          (null)
push 10  -> arr = [5, 10]      (null)
pop      -> arr = [5]          returns 10
pop      -> arr = []           returns 5
pop      -> arr = []  empty    returns -1

Key observations

1Aha

The array's end is the stack's top

Appending and removing at the end of a dynamic array are both amortized O(1), which is exactly what a stack's push and pop need.

2Aha

Guard the empty case

Popping an empty stack has no element to return, so this problem defines it to return -1 — check the size before removing.

Summary

Key takeaway

A stack is a dynamic array where you only ever touch the end: push appends, pop removes-and-returns the last element (or -1 when empty). Every operation is O(1).

push(x): arr.append(x)
pop():   return -1 if arr is empty else arr.pop()