Applications of Lists
Lists can be used to represent more complex structures, such as stacks and queues.
Short Recap
Stacks and queues are abstract data structures that define specific ways to store and access data.
- Stacks follow a Last-In, First-Out (LIFO) order.
- Queues follow a First-In, First-Out (FIFO) order.
Note
Stacks and queues can be implemented using lists, which provide a dynamic.
Stacks
Example
import java.util.LinkedList;
class Stack {
private LinkedList<Integer> list = new LinkedList<>();
// push: add to top
public void push(int item) {
list.addFirst(item);
}
// pop: remove from top
public int pop() {
return list.removeFirst();
}
// check if empty
public boolean isEmpty() {
return list.isEmpty();
}
public void print(){
String res = "";
for (int item : this.list){
res += item + " ";
}
System.out.println(res);
}
public static void main(String[] args){
Stack stack = new Stack();
// test isEmpty()
System.out.println(stack.isEmpty());
// test push()
for (int i = 1; i<= 5; i++){
stack.push(i);
}
stack.print();
// test pop()
int popped = stack.pop();
System.out.println("Popped: " + popped);
stack.print();
}
}
Hint
LinkedList methods such as:
- addFirst()
- removeFirst()
- getFirst() (without removing)
- addLast()
- removeLast()
- getLast() (without removing)
are very useful for implementing queues and stacks.
Queues
Example
import java.util.LinkedList;
class Queue {
private LinkedList<Integer> list = new LinkedList<>();
// enqueue: insert in the end
public void enqueue(int item) {
list.addLast(item);
}
// dequeue: remove from the beginning
public int dequeue() {
return list.removeFirst();
}
// check if empty
public boolean isEmpty() {
return list.isEmpty();
}
public void print(){
String res = "";
for (int item : this.list){
res += item + " ";
}
System.out.println(res);
}
public static void main(String[] args){
Queue q = new Queue();
// test isEmpty()
System.out.println(q.isEmpty());
// test enqueue()
for (int i = 1; i<= 5; i++){
q.enqueue(i);
}
q.print();
// test dequeue()
int popped = q.dequeue();
System.out.println("Dequeued: " + popped);
q.print();
}
}
Self review
Try to implement more methods, such as:
- peek() for stacks
- getFront() for queues
- size() for both queues and stacks
