-
Notifications
You must be signed in to change notification settings - Fork 21.3k
Expand file tree
/
Copy pathStackOfLinkedList.java
More file actions
135 lines (121 loc) · 3.39 KB
/
Copy pathStackOfLinkedList.java
File metadata and controls
135 lines (121 loc) · 3.39 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package com.thealgorithms.datastructures.stacks;
import java.util.NoSuchElementException;
/**
* A stack implementation using a singly linked list.
*
* <p>This class provides methods to push, pop, and peek elements in a Last-In-First-Out (LIFO) manner.
* It keeps track of the number of elements in the stack and allows checking if the stack is empty.
*
* <p>This implementation does not allow null elements to be pushed onto the stack.
*/
final class StackOfLinkedList {
private StackOfLinkedList() {
}
}
// A node class for the linked list
class Node {
public int data;
public Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
/**
* A class that implements a stack using a linked list.
*
* <p>This stack supports basic operations:
* <ul>
* <li>push: Adds an element to the top of the stack</li>
* <li>pop: Removes and returns the top element of the stack</li>
* <li>peek: Returns the top element without removing it</li>
* <li>isEmpty: Checks if the stack is empty</li>
* <li>getSize: Returns the current size of the stack</li>
* </ul>
*/
class LinkedListStack {
private Node head; // Top of the stack
private int size; // Number of elements in the stack
/**
* Initializes an empty stack.
*/
LinkedListStack() {
head = null;
size = 0;
}
/**
* Adds an element to the top of the stack.
*
* @param x the element to be added
* @return <tt>true</tt> if the element is added successfully
*/
public boolean push(int x) {
Node newNode = new Node(x);
newNode.next = head;
head = newNode;
size++;
return true;
}
/**
* Removes and returns the top element of the stack.
*
* @return the element at the top of the stack
* @throws NoSuchElementException if the stack is empty
*/
public int pop() {
if (size == 0) {
throw new NoSuchElementException("Empty stack. Nothing to pop");
}
Node destroy = head;
head = head.next;
int retValue = destroy.data;
destroy = null; // Help garbage collection
size--;
return retValue;
}
/**
* Returns the top element of the stack without removing it.
*
* @return the element at the top of the stack
* @throws NoSuchElementException if the stack is empty
*/
public int peek() {
if (size == 0) {
throw new NoSuchElementException("Empty stack. Nothing to peek");
}
return head.data;
}
@Override
public String toString() {
Node cur = head;
StringBuilder builder = new StringBuilder();
while (cur != null) {
builder.append(cur.data).append("->");
cur = cur.next;
}
return builder.replace(builder.length() - 2, builder.length(), "").toString(); // Remove the last "->"
}
/**
* Checks if the stack is empty.
*
* @return <tt>true</tt> if the stack is empty, <tt>false</tt> otherwise
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Returns the current size of the stack.
*
* @return the number of elements in the stack
*/
public int getSize() {
return size;
}
/**
* Removes all elements from the stack.
*/
public void makeEmpty() {
head = null;
size = 0;
}
}