Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Implementing Stack Data Structure
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Stacks are a Last-In, First-Out (LIFO) data structure that supports four main operations: Push, Pop, Peek (Top), and IsEmpty. In this lesson, we will first explain these operations in detail and then implement a stack using arrays and linked lists.

1. Stack Operations

1.1 Push Operation (Adding an Element to the Stack)

The Push operation adds an element to the top of the stack. If the stack is full (for a fixed-size array implementation), it results in a stack overflow error.

Steps for Push Operation:

  1. Check if the stack is full.
  2. If not full, increment the top index.
  3. Insert the new element at the top index.
  4. The new element becomes the topmost element in the stack.

Example Push:

Image
  • Time Complexity: O(1) → Directly inserting at the end.
  • Space Complexity: O(1) → No extra space required.

1.2 Pop Operation (Removing the Top Element)

The Pop operation removes the topmost element from the stack. If the stack is empty, it results in a stack underflow error.

Steps for Pop Operation:

  1. Check if the stack is empty.
  2. Retrieve the top element.
  3. Remove the top element by decrementing the top index.
  4. Return the removed element.

Example Pop:

Image
  • Time Complexity: O(1) → Directly removing the last element.
  • Space Complexity: O(1) → No extra space required.

1.3 Peek (Top) Operation (Viewing the Top Element Without Removing It)

The Peek operation allows us to look at the top element without modifying the stack.

Steps for Peek Operation:

  1. Check if the stack is empty.
  2. Return the topmost element without removing it.

Example Peek:

Stack: [10, 20, 30, 40]  (Top = 40)
Peek() → Returns 40
Stack remains unchanged.
  • Time Complexity: O(1) → Direct index access.
  • Space Complexity: O(1) → No extra space required.

1.4 IsEmpty Operation (Checking If the Stack is Empty)

The IsEmpty operation checks whether the stack contains any elements.

Steps for IsEmpty Operation:

  1. If the stack has no elements, return true.
  2. Otherwise, return false.

Example IsEmpty Operation:

Stack: [10, 20, 30]  
IsEmpty() → Returns False

Stack: []  
IsEmpty() → Returns True
  • Time Complexity: O(1)
  • Space Complexity: O(1)

2. Implementing Stack Using an Array in Java

An array-based stack provides O(1) time complexity for all operations. However, it has a fixed size, which may lead to stack overflow if it runs out of space.

Code

Python3
Python3
. . . .

3. Implementing Stack Using a Linked List in Java

A linked list-based stack overcomes the fixed-size limitation of an array, allowing for dynamic memory allocation.

Code

Python3
Python3
. . . .

4. Key Takeaways

  • Array-based stacks are simple but have a fixed size.
  • Linked list-based stacks provide dynamic memory but require extra space for pointers.
  • Both implementations offer O(1) time complexity for all operations.

Understanding stack operations and implementations is crucial for solving coding problems efficiently!

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible