Understanding Stack Data Structure for Interviews

If you are a software engineer or developer preparing for a technical interview, brushing up on data structures and algorithms should be a key part of your prep. Being well-versed with these topics is crucial for cracking tech interviews at FAANG and other top tech companies. In this article, we’ll be covering the basics of the stack data structure.

We’ll cover:

• What is a stack?
• Basic operations on a stack
• How insertion and deletion work in stacks
• Stack in Java
• Stack in Python
• Stack Time Complexity and Space Complexity
• Advantages and disadvantages of stack data structure

What Is Stack?

Stack is a linear data structure with only one end to access the elements and works similar to the real-world stack. We can insert or delete elements from one end only. Stack follows the LIFO (last in first out) principle. Whenever an element is added to the stack, it is added to the top, and similarly, whenever an element is deleted, it is removed from the top.

A can of Pringles is a good example of a stack. If you want to eat a chip, you pick up the one on top.

The element at the top of the stack is called the top element. The operation of inserting an element is called push(), and that of deleting an element is called pop().

When we delete the top element of the stack, if the stack is still non-empty, then the element just below the previous top element becomes the new top element of the stack. Similarly, when we insert the new element, the new element inserted will become the top element.

For example: In the can of Pringles, when you take out the chip on top, the next chip becomes the new “top.”

Following are some applications of the stack data structure:

• Browsers use the stack data structure to keep track of the last visited sites.
• Undo/Redo stacks in Excel or Word.
• Stack is also used in some scheduling algorithms.
• Stacks are also used for evaluating expressions.

Features of a stack:

• Stack is a dynamic data structure, that is, its size is not fixed and can be increased or decreased dynamically.
• As it is a dynamic data structure, it does not take up a fixed amount of memory like arrays.
• The size of a stack changes with every push() or pop() operation.

Basic Operations on a Stack

Following are the basic operations you can perform on a stack:

• push(): Adds an element to the top of the stack.
• pop(): Removes elements from the top of the stack.
• isEmpty(): Returns true if the stack is empty; else, returns false.
• isFull(): Returns true if the stack is full; else, returns false.
• top: Used to get the value of the top-most element of the stack.

How Insertion and Deletion Work in Stacks

We need to keep track of the “top” of the stack to perform insertion or deletion. While initializing the stack, we set the value of top to -1 — we can use this to check whether the stack is empty.

• While inserting a new element, we increment the value of top and place a new element at the position pointed by top after the increment.
• While removing an element, we decrease top and return the element pointed by top.
• For every push operation, we need to check whether our stack is full or not.
• For every pop operation, we need to check whether our stack is empty or not.

Here, the array arr is used to store the stack.

Stack Data Structure in Java

We’ve used a fixed-size array here to implement the stack, which makes it non-dynamic (meaning its size is fixed).

// Stack implementation in Java

class Stack {

// array used to store the stack elements

private int arr[];

// variable top to keep the track of top element of stack

private int top;

// capacity is the max size of stack

private int capacity;

 

// Creating a stack of size n and updating the top pointer.

Stack(int n) {

arr = new int[n];

capacity = n;

top = -1;

}

// push() operation to add the new element – p to stack

public void push(int p) {

// checking whether the stack is full or not.

if (isFull()) {

System.out.println(“Overflow”);

System.exit(1);

}

// inserting element p in a stack

System.out.println(“Inserting ” + p);

// incrementing the top pointer

top++;

// updating the value at new top pointer

arr[top] = p;

}

// pop() operation to remove the element from stack and return the removed element.

public int pop() {

// check if stack is empty or not

if (isEmpty()) {

System.out.println(“Stack is Empty”);

System.exit(1);

}

System.out.println(“Removing ” + arr[top]);

// decrementing the top pointer

top–;

// return the popped element.

return arr[top+1];

}

// function used to return the size of stack

public int size() {

return top + 1;

}

// function used to check whether the stack is empty or not.

public Boolean isEmpty() {

return top == -1;

}

// function used to check if the stack is full or not.

public Boolean isFull() {

return top == capacity – 1;

}

// function used to print the whole stack (from top to bottom).

public void printStack() {

System.out.println(“nFinal Stack:”);

for (int i = top; i >= 0; i–) {

System.out.println(arr[i]);

}

}

public static void main(String[] args) {

// creating new stack of size 4

Stack stack = new Stack(4);

// pushing elements in stack

stack.push(1);

stack.push(2);

stack.push(3);

stack.push(4);

// popping element.

stack.pop();

// printing the final stack.

stack.printStack();

}

}

Stack Data Structure in Python

We’ve used Python’s list to create the stack, which is a dynamic array in Python.

# Stack implementation in python

# Function used to create an empty stack

def CreateStack():

stack = []

return stack

# Function used to check whether the stack is empty or not.

def isEmpty(stack):

return len(stack) == 0

# Function used to push an element into a stack.

def Push(stack, item):

stack.append(item)

print(“Inserting: ” + item)

# Function used to pop element from the stack

def pop(stack):

# Check is the stack is empty or not

if (isEmpty(stack)):

return “Stack is Empty”

return stack.pop()

# Array used to store the stack elements

stack = CreateStack()

# pushing elements in the stack

Push(stack, str(1))

Push(stack, str(2))

Push(stack, str(3))

Push(stack, str(4))

# popping element from the stack

print(“popped item: ” + pop(stack))

# printing the whole stack

print(“stack after popping an element: ” + str(stack))

Stack Time Complexity and Space Complexity

The push() and pop() operations take constant time. Also, isEmpty() and CreateStack() have constant time complexity.

Space complexity is linear corresponding to the size of the stack because we are storing the number of elements equal to the size of the stack.

Advantages and Disadvantages of Stack Data Structures

Advantages:

• In stacks, memory can be dynamically allocated, that is, we can allocate memory to a particular object on runtime.
• It follows the last-in-first-out (LIFO) order; we can add and remove elements from the top of the stack, unlike arrays.

Disadvantages:

• It lacks scalability.
• Random access is not possible.

FAANG Interview Questions on Stack Data Structure

Following are some of the commonly asked questions on stack:

1. Implement a stack using the queue data structure
2. Implement a queue using the stack data structure
3. Reverse a string using a stack data structure
4. Find duplicate parenthesis in an expression
5. Check if an expression is balanced or not
6. Reverse a stack using recursion
7. Find the previous smaller element for each array element

FAQs on Stack Data Structures

Question 1: Why do we need a stack?

Answer: Stack is used for implementing functions, evaluating expressions, and backtracking algorithms. Because of its last-in-first-out (LIFO) property, it has many advantages over other data structures, such as it can be used in cases where we only need to access or remove elements from one end.

Question 2: Can stack can be implemented using linked lists?

Answer: Yes. A stack can be implemented using linked lists. We can use a list instead of a dynamic array. The head of the linked list will be the top element of the stack. We can dynamically push elements in it and also pop elements from it using delete a node and insert new node operations in linked lists.

Looking for a Tech Interview Prep Coach?

Interview Kickstart offers the best technical interview prep courses that make you a better engineer and help you nail tech interviews.

As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

For more information on what it takes to prepare for and succeed at FAANG tech interviews, sign up for our free webinar.

————

Article contributed by Omkar Deshmukh