Stack Data Structure

A stack is a linear data structure that holds a collection of elements. It has two primary operations: Push (adds an element to the collection) and Pop (removes the most recently added element from the collection). By following this order it is a LIFO (last in, first out) collection and can be thought of as a stack of pancakes.

Basic Operations

push() - adds an item to the stack.
pop() - removes an item from the top of the stack.
peek() - returns the value of the top element without removing it.
isEmpty() - check if the stack is empty.

Implementations

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

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.

In the linked list implementation the time complexity of the push and pop operations are O(1) (constant time).

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.

Posted on Jun 27, 2022 by bmcculley Posted in:

Data Structures