A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. In other words, the most recently added item to the stack is the first item to be removed. A stack has two primary operations: push, which adds an item to the top of the stack, and pop, which removes and returns the top item from the stack. Additionally, a stack may have other operations, such as peek, which returns the top item without removing it, and isEmpty, which checks whether the stack is empty. Stacks are often used in programming for tasks such as parsing expressions, evaluating expressions, and implementing recursive algorithms.
class Stack<T> {
private var head: Node<T>? = null
private var size = 0
This implementation uses a singly linked list to represent the stack. The Stack class has a private field head that points to the first node in the list, and a private field size that stores the number of nodes in the list.
fun push(data: T) {
val newNode = Node(data)
newNode.next = head
head = newNode
size++
}The push function adds a new node with the given data to the top of the stack by creating a new Node instance with the data, setting its next field to the current head node, and updating the head field to point to the new node. The size field is incremented to reflect the addition of the new node.
fun pop(): T? {
if (isEmpty()) {
return null
}
val data = head?.data
head = head?.next
size--
return data
}The pop function removes and returns the data of the top node in the stack by checking if the stack is empty, if not it gets the data of the head node, sets the head field to point to the next node in the list, decrements the size field, and returns the data of the original head node.
fun peek(): T? {
if (isEmpty()) {
return null
}
return head?.data
}The peek function returns the data of the top node in the stack without removing it by checking if the stack is empty, if not it returns the data of the head node.
fun isEmpty(): Boolean {
return size == 0
}The isEmpty function checks if the stack is empty by returning true if the size of the stack is zero.
fun size(): Int {
return size
}The size function returns the number of nodes in the stack by returning the size field.
private class Node<T>(val data: T) {
var next: Node<T>? = null
}The Node class is a private inner class that represents a node in the linked list. It has a field data to store the data of the node, and a field next to point to the next node in the list.
class Stack<T> {
private var head: Node<T>? = null
private var size = 0
fun push(data: T) {
val newNode = Node(data)
newNode.next = head
head = newNode
size++
}
fun pop(): T? {
if (isEmpty()) {
return null
}
val data = head?.data
head = head?.next
size--
return data
}
fun peek(): T? {
if (isEmpty()) {
return null
}
return head?.data
}
fun isEmpty(): Boolean {
return size == 0
}
fun size(): Int {
return size
}
private class Node<T>(val data: T) {
var next: Node<T>? = null
}
}
fun main() {
val stack = Stack<Int>()
stack.push(1)
stack.push(2)
stack.push(3)
println(stack.pop()) // prints 3
println(stack.peek()) // prints 2
println(stack.size()) // prints 2
println(stack.isEmpty()) // prints false
stack.pop()
stack.pop()
println(stack.pop()) // prints null
println(stack.peek()) // prints null
println(stack.size()) // prints 0
println(stack.isEmpty()) // prints true
}This example creates a new Stack instance of type Int and pushes the values 1, 2, and 3 onto the stack using the push function. It then prints the result of calling pop to remove and return the top node of the stack, which is 3. It also prints the result of calling peek to return the data of the top node without removing it, which is 2. It prints the size of the stack using the size function, which is 2. It prints whether the stack is empty using the isEmpty function, which is false.
The example then removes the remaining nodes from the stack using the pop function, and prints the result of calling pop on an empty stack, which is null. It also prints the result of calling peek on an empty stack, which is null. It prints the size of the stack, which is 0, and whether the stack is empty, which is true.