图片来自 unsplash
栈 , 队列 , 背包
- **栈 : **栈 , 在之前的一篇文章里面已经讲过了 , 遵从先入后出原则 (FILO) .
- **队列 : **队列 , 顾名思义 , 就像排队一样 , 先排队的人先处理 , 遵从先入先出原则 (FIFO) .
- **背包 : **在这里的背包 , 就像平时用的背包一样 , 用来装东西 , 但是里面的东西顺序不重要 . 而 栈 和 队列 是有序的 . 得注意的是 , 背包 , 只能添加元素节点 , 而不能删除元素节点 .
方法列表
- 栈 ( Stack )
-
void push(Item item): 添加一个元素节点 . -
Item pop(): 删除栈顶元素节点 . -
boolean isEmpty(): 判断栈是否为空 . -
int size(): 返回栈长度 .
-
- 队列 ( Queue )
-
void enqueue(Item item): 加入新元素节点到队列 . -
Item dequeue(): 删除最早进入队列的元素节点 . -
boolean isEmpty(): 判断队列是否为空 . -
int size(): 返回队列长度 .
-
- 背包 ( Bag )
-
void add(Item item): 添加新元素节点到背包 . -
boolean isEmpty(): 判断背包是否为空 . -
int size(): 返回背包大小 .
-
链表实现栈 , 队列 , 背包
链表在之前的文章里已经将过了 , 这里就不多说了 .
链表实现栈
public class Stack<Item> implements Iterable<Item> {
private Node head = null;
private int length = 0;
public Stack(){}
public void push(Item item) {
Node node = new Node(item);
node.next = this.head;
this.head = node;
length++;
}
public Item pop() {
Node node = this.head;
this.head = this.head.next;
this.length--;
return node.item;
}
public int size() {
return this.length;
}
public boolean isEmpty() {
return this.length == 0;
}
private class Node {
public Item item;
public Node next;
public Node(Item item) {
this.item = item;
}
}
@Override
public Iterator<Item> iterator() {
return new ListIterator<>();
}
private class ListIterator<Item> implements Iterator<Item> {
private Node current = head;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = (Item) current.item;
current = current.next;
return item;
}
@Override
public void remove() {}
}
@Override
public Spliterator<Item> spliterator() {
return null;
}
}
链表实现队列
public class Queue<Item> implements Iterable<Item> {
private Node head = null; //最先入队的元素
private int length = 0; //队列长度
private Node last = null; //最后入队的元素
private class Node {
public Item item = null;
public Node next = null;
public Node(Item item) {
this.item = item;
}
}
public Queue() {
}
public boolean isEmpty() {
return this.length == 0;
}
public int size() {
return this.length;
}
public void enqueue(Item item) {
Node node = new Node(item);
if (isEmpty()) {
this.head = this.last = node;
}else{
this.last.next = node;
this.last = node;
}
this.length++;
}
public Item dequeue() {
Item item = this.head.item;
this.head = this.head.next;
if (size()==1){
last =null;
}
this.length--;
return item;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator<>();
}
private class ListIterator<Item> implements Iterator<Item> {
private Node current = head;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = (Item) current.item;
current = current.next;
return item;
}
@Override
public void remove() {}
}
}
链表实现背包
public class Bag<Item> implements Iterable<Item> {
private int length = 0;
private Node head;
public Bag(){}
private class Node {
public Item item = null;
public Node next = null;
public Node(Item item) {
this.item = item;
}
}
public int size(){
return this.length;
}
public boolean isEmpty(){
return this.length == 0;
}
public void add(Item item){
Node node = new Node(item);
if (isEmpty()){
this.head = node;
}else {
Node current = this.head;
while (current.next!=null){
current = current.next;
}
current.next = node;
}
this.length++;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator<>();
}
private class ListIterator<Item> implements Iterator<Item> {
private Node current = head;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = (Item) current.item;
current = current.next;
return item;
}
@Override
public void remove() {}
}
}
