Authored by Tony Feng
Created on March 24th, 2022
Last Modified on March 25th, 2022
Understanding Stacks
Main Concepts
- Stack is an abstract data structure that is similar to queue. Unlike queues, a stack is open at one end.
- First In Last Out (FILO) e.g. Back functionanlity of browsers
Operations
- Access - O(1)
- Access the top of the stack
- Search - O(N)
- Insert - O(1)
- A stack can only be inserted from the top.
- Delete - O(1)
- A stack can only be removed from the top.
Stack Implementation in Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
# Create
stack = []
# Add an element - O(1)
stack.append(1)
stack.append(2)
stack.append(3) # [1,2,3]
# Get the top of the stack - O(1)
top = stack[-1]
# Remove the head of the stack - O(1)
top = stack.pop()
# Get the size of the stack - O(1)
length = len(stack)
# Traverse the stack - O(N)
while len(stack) != 0:
tmp = stack.pop()
print(tmp)
|
Stack Implementation in Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
// Create
Stack<Integer> s = new Stack<>();
// Add - O(1)
s.push(1);
s.push(2);
s.push(3);
// Get the head of the stack - O(1)
int elem = s.peek(); // 1
// Remove the head of the stack - O(1)
int id = s.pop(); // 1
// Get the size of the stack - O(1)
int len = s.size()
// Traverse the stack - O(N)
while (!s.isEmpty()) {
int tmp = s.pop()
System.out.println(tmp)
}
|
Reference