【数据结构】模拟实现栈和队列

栈（Stack）

栈的概念

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除操作，进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈的数据遵循后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做压栈/进栈/入栈，入的数据在栈顶。

出栈：栈的删除操作叫做出栈，出的数据在栈顶。

栈的常用方法

//入栈
public void push(int val)
    
//将栈顶元素出栈并返回
public int pop()
    
//获取栈顶元素
public int peek()
    
//检测栈是否为空
public boolean isEmpty()
1
2
3
4
5
6
7
8
9
10
11

模拟实现栈

构造一个空栈

public class MyStack {
    private int[] elem;
    private int usedSize;//栈的实际元素个数
    private static final int DEFAULT_CAPACITY = 10;

    //初始化栈的大小为DEFAULT_CAPACITY
    public MyStack() {
        this.elem = new int[DEFAULT_CAPACITY];
    }
}
1
2
3
4
5
6
7
8
9
10

实现push方法（入栈）

public void push(int val) {
	//判断栈是否已满 满就扩容
	if (this.elem.length == usedSize) {
		this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
	}
	this.elem[usedSize] = val;
	usedSize++;
}
1
2
3
4
5
6
7
8

实现pop方法（将栈顶元素出栈并返回）

如果栈为空，返回栈顶元素就会报错，我们可以自定义一个异常用来解决报错问题

public class emptyException extends RuntimeException {
    public emptyException() {
    }

    public emptyException(String message) {
        super(message);
    }
}
1
2
3
4
5
6
7
8

public int pop() {
    //如果为空栈就抛出一个异常
	if (usedSize==0){
		throw new emptyException();
	}
	int oldVal = this.elem[usedSize-1];
	usedSize--;
	return oldVal;
}
1
2
3
4
5
6
7
8
9

实现peek方法（获取栈顶元素）

public int peek() {
    //如果为空栈就抛出一个异常
	if (usedSize==0){
		throw new emptyException();
	}
	return this.elem[usedSize-1];
}
1
2
3
4
5
6
7

实现isEmpty方法（检测栈是否为空）

public boolean isEmpty() {
    //判断栈是否为空 只需要判断栈的实际元素个数是否为0即可
	return usedSize==0;
}
1
2
3
4

队列（Queue）

队列的概念

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列遵循先进先出FIFO（First in First Out）的原则。在Java里面Queue 是一个接口，底层是通过链表实现的。

入队列：进行插入的一端称为队尾。

出队列：进行删除的一端称为队头。

队列的常用方法

//入队
public void offer(int x)
    
//出队
public int poll()

//获取队头元素x
public int peek()

//获取队列中有效元素的个数
public int size()
    
//检测队列是否为空
public boolean isEmpty()
1
2
3
4
5
6
7
8
9
10
11
12
13
14

队列的模拟实现

双链表模拟实现队列

public class MyQueue {
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode prev;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode front;//队头
    public ListNode rear;//队尾
    public int usedSize = 0;//队列实际元素个数
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

实现offer方法（入队）

public void offer(int x) {
	ListNode node = new ListNode(x);
    //队列为空
	if (front==null){
		front=rear=node;
	}else {
		node.next=front;
		front.prev=node;
		front=node;
	}
	usedSize++;
}
1
2
3
4
5
6
7
8
9
10
11
12

实现poll方法（出队）

public int poll(){
    //队列为空
	if (front==null){
		return -1;
	}
	int ret = rear.val;
    //队列中只有一个元素
	if (front==rear){
		front=null;
		rear=null;
		usedSize--;
		return ret;
	}
	//删除尾节点
	rear=rear.prev;
	rear.next=null;
	usedSize--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

实现peek方法（获取队头元素）

public int peek(){
	if (front==null){
		return -1;
	}
	return front.val;
}
1
2
3
4
5
6

实现size方法（获取队列中有效元素的个数）

public int size(){
	return usedSize;
}
1
2
3

实现isEmpty方法（检测队列是否为空）

public boolean isEmpty(){
	return front==null;
}
1
2
3

循环队列模拟实现

public class MyCircularQueue {
    public int[] elem;
    public int front;//队头
    public int rear;//队尾

    //构造循化队列
    public MyCircularQueue(int len) {
        this.elem = new int[len+1];
    }

    //入队
    public boolean enQueue(int val){
        //判断队列是否装满
        if (isFull()){
            return false;
        }
        elem[rear] = val;
        rear = (rear+1)%elem.length;
        return true;
    }

    //检测队列是否装满
    private boolean isFull() {
        return (rear+1)%elem.length==front;
    }

    //出队
    public boolean deQueue(){
        if (isFull()){
            return false;
        }
        front = (front+1)%elem.length;
        return true;
    }

    //获取队头元素
    public int getFront(){
        if (isEmpty()){
            return -1;
        }
        return elem[front];
    }

    //检测队列是否为空
    public boolean isEmpty(){
        return front==rear;
    }
}
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