Stack Data Structure

The stack data structure is a fundamental abstract data type commonly used in computer science and software engineering. It follows the Last-In, First-Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. Think of it like a stack of plates: you can only add or remove plates from the top of the stack.

Basic Operations

• Push: Adding an element to the top of the stack.
• Pop: Removing the top element from the stack.
• Peek (or Top): Viewing the top element of the stack without removing it.
• isEmpty: Checking if the stack is empty.
• Size: Returning the number of elements currently in the stack.

Implementations

• Stacks can be implemented using various data structures, including arrays and linked lists.
• Arrays are commonly used for implementing stacks due to their simplicity and constant-time access to elements.
• Linked lists can also be used, providing dynamic memory allocation and flexibility.

A stack implemented using an array

class Stack:
	def __init__(self, data):
		self.stack = []
		if data:
			self.stack.append(data)

	def add(self, data):
		self.stack.append(data)

	def pop(self):
		return self.stack.pop()

	def peek(self):
		if self.isEmpty():
			raise ValueError("The stack is empty")
		return self.stack[-1]

	def isEmpty(self):
		return len(self.stack) == 0

type DataType interface{}

type Stack []DataType

func (s *Stack) Size() int {
	return len(*s)
}

func (s *Stack) IsEmpty() bool {
	return len(*s) == 0
}

func (s *Stack) Push(d DataType) {
	*s = append(*s, d)
}

func (s *Stack) Pop() DataType {
	if s.IsEmpty() {
		return ""
	} else {
		index := len(*s) - 1   
		element := (*s)[index] 
		*s = (*s)[:index]      
		return element
	}
}

func (s *Stack) Peek() DataType {
	if s.IsEmpty() {
		return ""
	}
	return (*s)[len(*s)-1]
}

class Stack {
    constructor() {
      this.stack = [];
    }
    
    push(data) {
        this.stack.push(data);
    }
    
    pop() {
        return this.stack.pop();
    }
    
    peek() {
        return this.stack[this.stack.length-1];
    }
    
    isEmpty() {
        return this.stack.length === 0;
    }
}

class Stack {
private:
	vector<string> stack;
public:
	void push(string data) {
		stack.push_back(data);
	}

	string pop() {
		string temp = stack.back();
		stack.pop_back();
		return temp;
	}

	string peek() {
		return stack.back();
	}

	bool empty() {
		return stack.empty();
	}
};

class Stack {
    private ArrayList<Integer> stack;

    Stack (int size) {
        stack = new ArrayList<Integer>(size);
    }

    public void push(int data) {
        stack.add(data);
    }

    public int pop() {
        int temp = stack.get(stack.size()-1);
        stack.remove(stack.size()-1);
        return temp;
    }

    public int peek() {
        return stack.get(stack.size()-1);
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}

A stack implemented using a Linked List.

class Node:
	def __init__(self, value=None):
		self.value = value
		self.next = None

class LinkedList:
	def __init__(self, value=None):
		if value:
			new_node = Node(value)
			length = 1
		else:
			new_node = None
			length = 0

		self.head = new_node
		self.length = length

	def isEmpty(self):
		return self.length == 0

	def insert(self, value=None, position=None):
		if not value:
			raise ValueError("Value cannot be empty.")

		if not self.head:
			self.head = Node(value)
			self.length += 1
		elif position == 0:
			new_node = Node(value)
			new_node.next = self.head
			self.head = new_node
			self.length += 1
		elif position is not None:
			curr = self.head
			prev = None
			index = 0
			while index != position:
				if not curr:
					raise ValueError("Index out of range.")
				prev = curr
				curr = curr.next
				index += 1

			new_node = Node(value)
			new_node.next = curr

			if prev:
				prev.next = new_node
			else:
				self.head = new_node
			self.length += 1
		else:
			curr = self.head
			while curr.next:
				curr = curr.next

			curr.next = Node(value)
			self.length += 1

	def popFront(self):
		self.length -= 1
		temp = self.head.value
		self.head = self.head.next
		return temp

	def peekFront(self):
		if not self.head:
			raise ValueError("List is empty.")
		else:
			return self.head.value

class Stack:
	def __init__(self):
		self.stack = LinkedList()

	def push(self, value):
		self.stack.insert(value, 0)

	def pop(self):
		return self.stack.popFront()

	def peek(self):
		return self.stack.peekFront()

	def isEmpty(self):
		return self.stack.isEmpty()

type DataType interface{}

type node struct {
	data DataType
	next *node
}

type Stack struct {
	head *node
	length int
}

func (l *Stack) Size() int {
	return l.length
}

func (l *Stack) IsEmpty() bool {
	return l.length == 0
}

func (l *Stack) Push(d DataType) {
	l.length++
	if l.head == nil {
		l.head = &node{d, nil}
	} else {
		temp := &node{d, nil}
		temp.next = l.head
		l.head = temp
	}
}

func (l *Stack) Pop() DataType {
	if l.IsEmpty() {
		return nil
	} else {
		l.length--
		temp := l.head.data
		l.head = l.head.next
		return temp
	}
}

class Node {
    constructor(data, next=null) {
        this.data = data;
        this.next = next;
    }
}
  
class LinkedList {
    constructor(head=null) {
        this.head = head;
    }

    push(item) {
        if (this.head === null) {
            this.head = new Node(item);
        } else {
            let temp = new Node(item);
            temp.next = this.head;
            this.head = temp;
        }
    }
    
    pop() {
        let curr_node = this.head;
        if (curr_node.next !== null) {
            this.head = curr_node.next;
        } else {
            this.head = null;
        }
        return curr_node.data;
    }

    peek() {
        return this.head.data;
    }
}

export class Stack {
    constructor() {
      this.stack = new LinkedList();
      this.stack_len = 0;
    }
    
    push(data) {
        this.stack.push(data);
        this.stack_len++;
    }
    
    pop() {
        this.stack_len--;
        return this.stack.pop();
    }
    
    peek() {
        return this.stack.peek();
    }
    
    isEmpty() {
        return this.stack_len === 0;
    }
}

int binarySearch(vector nums, int x) {
	int left = 0;
	int right = nums.size();

	while (left <= right) {
		int mid = left + (right - left) / 2;

		if (nums[mid] == x)
			return mid;
		if (nums[mid] < x)
			left = mid + 1;
		else
			right = mid - 1;
  	}
  	return -1;
}

public class BinarySearch {

    public static int search(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] == target) {
                return mid;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

}

Time Complexity

Array Implementation

For the list/array/vector implementation of the stack the average time complexity of the push and pop operations are O(1). However, if the array needs to be resized the complexity will become O(n) where n is the number of elements in the stack.

Linked List Implementation

A summarization of the best, average, and worst-case time and space complexities for common operations on the stack data structure using a linked list:

Explanation:

• Push: Adding an element to the top of the stack involves inserting the element at the top position. This operation has a constant time complexity of (O(1)) in all cases. The space complexity is also (O(1)) since only one element is added.

• Pop: Removing the top element from the stack involves deleting the element at the top position. This operation has a constant time complexity of (O(1)) in all cases. The space complexity is also (O(1)) since only one element is removed.

• Peek: Viewing the top element of the stack without removing it has a constant time complexity of (O(1)) in all cases. This operation does not modify the stack, so the space complexity is (O(1)).

• isEmpty: Checking if the stack is empty involves verifying whether the stack contains any elements. This operation has a constant time complexity of (O(1)) in all cases. The space complexity is also (O(1)) since it only requires checking a flag or variable.

• Size: Determining the number of elements in the stack depends on the underlying implementation.

  • For an array-based implementation where the size is maintained explicitly, both the best, average, and worst-case time complexities for the Size operation are (O(1)). The space complexity is also (O(1)) since the size variable is maintained separately.
  • For a linked list-based implementation, traversing the entire linked list to count the elements results in a time complexity of (O(n)) in the best, average, and worst cases. The space complexity is also (O(n)) since the stack size is directly proportional to the number of elements stored in the linked list.

In summary, stack operations are typically very efficient, with constant time complexities for basic operations like Push, Pop, Peek, and isEmpty. The space complexity depends on the underlying implementation and whether the size of the stack is maintained explicitly.

Applications of Stack Data Structure

A stack is a simple but very powerful data structure and has many uses. Some of those uses are:

• Arithmetic Expression Evaluation, a stack is very effective in evaluating arithmetic expressions.
• They can also be used for Backtracking. Backtracking is an algorithmic technique that is used to search all possible solutions for a problem.
• Tracking function calls, whenever a call is made from one function to another the address of the calling function gets stored on the stack.

Challenges

• Implement a queue using the stack data structure.
• Check valid parentheses.
• Reverse a string.