Learn

Stack Data Structure

2022-06-27

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.

Linked List Data Structure
2019-03-26
A linked list is a linear collection of data elements, their order is not given by their physical placement in memory. Instead they are constructed in such a way that each element points to the next. It is a data structure that consists of a collection of nodes which together represents a sequence.
Nodes linked together
Linked lists can be singly or doubly linked.

Stack Data Structure

Basic Operations

Implementations

A stack implemented using an array

Linked List Data Structure