复习一下数据结构，巩固一下基础。
之后打算再学一下算法，之前刷题总感觉摸不清门道，应该是概念没彻底搞明白。
栈
import java.util.Arrays;
public class Stack {
private int size;
private int[] array;
public Stack() {
this(10);
}
public Stack(int init) {
if(init <= 0) {
init = 10;
}
array = new int[init];
}
public void push(int item) {
if(size == array.length) {
array = Arrays.copyOf(array, size * 2);
}
array[size++] = item;
}
public int peek() {
if(size == 0) {
throw new ArrayIndexOutOfBoundsException("栈已经空啦");
}
return array[size - 1];
}
public int pop() {
int item = peek();
size--;
return item;
}
public boolean isFull() {
return size == array.length;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
}
队列
public class ArrayQueue {
private final Object[] items;
private int head;
private int tail;
public ArrayQueue(int capacity) {
this.items = new Object[capacity];
}
public boolean put(Object item) {
if(head == (tail + 1) % items.length) {
return false;
}
items[tail] = item;
tail = (tail + 1) % items.length;
return true;
}
public Object peek() {
if(head == tail) {
return null;
}
return items[head];
}
public Object poll() {
if(head == tail) {
return null;
}
Object item = items[head];
items[head] = null;
head = (head + 1) % items.length;
return item;
}
public boolean isFull() {
return head == (tail + 1) % items.length;
}
public boolean isEmpty() {
return head == tail;
}
public int size() {
if(head <= tail) {
return tail - head;
}
return tail - head + items.length;
}
}
用栈来模拟队列
public class Stack2Queue {
private Stack stack1;
private Stack stack2;
private int maxLength;
public Stack2Queue(int capacity) {
maxLength = capacity;
stack1 = new Stack(capacity);
stack2 = new Stack(capacity);
}
public boolean put(int item) {
if(stack1.isFull() || size() == maxLength) {
return false;
}
stack1.push(item);
return true;
}
public int poll() {
if(!stack2.isEmpty()) {
return stack2.pop();
}else {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
public int size() {
return stack1.size() + stack2.size();
}
}
用队列来模拟栈
public class Queue2Stack {
private ArrayQueue queue1;
private ArrayQueue queue2;
private int maxLength;
public Queue2Stack(int capacity) {
maxLength = capacity;
queue1 = new ArrayQueue(capacity);
queue2 = new ArrayQueue(capacity);
}
public boolean push(Object item) {
if(size() == maxLength) {
return false;
}
if(queue2.isEmpty()) {
queue1.put(item);
}else {
queue2.put(item);
}
return true;
}
public Object pop() {
if(size() == 0) {
// return null;
throw new IndexOutOfBoundsException("栈里空啦");
}
if(queue2.isEmpty()) {
while(queue1.size() > 1) {
queue2.put(queue1.poll());
}
return queue1.poll();
}else {
while(queue2.size() > 1) {
queue1.put(queue2.poll());
}
return queue2.poll();
}
}
public int size() {
return queue1.size() + queue2.size();
}
}
链表
public class Node {
private int data;
private Node next;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public class Link {
private int size = 0;
private Node first;
private Node last;
public Link() {
}
public void addFirst(int data) {
if(size == 0) {
fillStart(data);
}else {
Node node = new Node();
node.setData(data);
node.setNext(first);
first = node;
size++;
}
}
public void addLast(int data) {
if(size == 0) {
fillStart(data);
}else {
Node node = new Node();
node.setData(data);
last.setNext(node);
last = node;
size++;
}
}
public void add(int data, int index) {
if(size > index) {
if(size == 0) {
fillStart(data);
}else if(index == 0) {
addFirst(data);
}else if (index == size -1) {
addLast(data);
}else {
Node node = new Node();
node = get(index - 1);
Node temp = new Node();
temp.setData(data);
temp.setNext(node.getNext());
node.setNext(temp);
size++;
}
}else {
throw new IndexOutOfBoundsException("链表没有这么长");
}
}
public void removeFirst() {
if(size == 0) {
throw new IndexOutOfBoundsException("链表中没有元素");
}else if(size == 1) {
clear();
}else {
Node node = first;
first = first.getNext();
node = null;
size--;
}
}
public void removeLast() {
if(size == 0) {
throw new IndexOutOfBoundsException("链表中没有元素");
}else if(size == 1) {
clear();
}else {
Node node = get(size -2);
node.setNext(null);
last = node;
size--;
}
}
public void removeMiddle(int index) {
if(size == 0) {
throw new IndexOutOfBoundsException("链表中没有元素");
}else if(size == 1) {
clear();
}else {
Node node = get(index - 1);
Node temp = node.getNext();
node.setNext(temp.getNext());
size--;
}
}
public int size() {
return size;
}
public void clear() {
first = null;
last = null;
size = 0;
}
public Node get(int index) {
Node temp = first;
for(int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
private void fillStart(int data) {
first = new Node();
first.setData(data);
last = first;
size++;
}
public void printAll() {
Node temp = first;
System.out.println(temp.getData());
for(int i = 0; i < size - 1; i++) {
temp = temp.getNext();
System.out.println(temp.getData());
}
}
}
暂时先复习了这么多，本文持续更新~
如果有啥觉得可以补充或者建议，可以留言噢~
参考：
- 《轻松学算法》赵烨
