[笔记]算法复习笔记---栈、队列、链表（上）

发表于 | 分类于
字数统计 1,309 | 阅读时长 6

一、什么是栈

栈，又叫做堆栈（Stack），但是它和堆没有关系。实际上堆和栈是两种不同的概念，栈是一种只能在一端进行插入和删除的线性数据结构。

栈的特点：先进先出（LIFO，Last In First Out），也可以说是先进后出（FILO，First In Last Out），我们只能从一端去操作元素。

一般来说，栈主要有两种操作：一个是进栈（Push），又叫做入栈，压栈；另一个是出栈（POP），或者叫退栈。

我们可以用数组去实现一个简单的栈，在下面栈的实现代码中，以整型元素为例，在Java等高级语言中，数据类型中，可以换成对象。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public class Stack {
	
	private int size = 0;
	
	
	private int[] array;
	
	public Stack() {
		this(10);
	}
	public Stack(int init) {
		
		if (init <= 0) {
			init = 10;
		}
		
		array = new int[init];
	}
	
	/**
	 * 入栈
	 * @param item 入栈元素
	 */
	public void push(int item) {
		
		if (size == array.length) {
			array = Arrays.copyOf(array, size*2);
		}
		
		array[size++] = item;
	}
	
	/**
	 * 获取栈顶元素，但是没有出栈
	 * @return 栈顶元素
	 */
	public int peek() {
		
		if (size ==0) {
			throw new IndexOutOfBoundsException("栈里已经为空");
		}
		
		return array[size -1];
	}
	
	/**
	 * 出栈，同时获取栈顶元素
	 * @return 栈顶元素
	 */
	public int pop() {
		int item = peek();
		size --;
		return item;
	}
	
	/**
	 * 栈是否满了？
	 * @return 
	 */
	public boolean isFull() {
		return size == array.length;
	}
	
	/**
	 *栈是否为空栈 ？ 
	 * @return
	 */
	public boolean isEmpty() {
		return size ==0;
	}
	
	
	public int size() {
		return size;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class StackTest {
		
	public static void main(String[] args) {
		
		Stack stack = new Stack(1);
		stack.push(1);
		stack.push(2);
		System.out.println(stack.size());//栈内元素个数为2，当前数组长度也为2
		
		stack.push(3);
		System.out.println(stack.size());//栈内元素个数为3，当前数组长度为4
		System.out.println(stack.peek());//获取栈顶元素为3，但没有出栈
		System.out.println(stack.size());//元素个数还为3
		
		System.out.println(stack.pop());//栈顶元素出栈，返回3
		System.out.println(stack.pop());//栈顶元素出栈，返回2
		System.out.println(stack.size());//两次出栈之后，当前元素个数为1
	}
}

###栈的适用场景

  1. 逆序输出

由于栈有先进先出的特点，把元素顺序入栈，然后顺序出栈，就可以轻松得到逆序输出。

  1. 语法检查，符号成对出现

在编程语言中，{ } [ ] ( ) < > 等都是成对出现的，当遇到符号的前半部分，就进行入栈操作（PUSH），当遇到后半部分就与栈顶元素匹配（PEEK），如果相匹配，就出栈（POP），否则匹配出错。

  1. 数值转换

我们在进行数值转换时，最后的商需要逆序输出，用栈就可以简单的实现。当然，栈还有许多应用，比如经常听到的“函数栈”就是我们在调用方法时，计算机会执行PUSH方法，记录调用，在return的时候。就是在方法结束后，执行POP方法，完成前后对应。

二、什么是队列

队列也是一种操作受限的数据结构，插入操作只能从一端进行，这个叫队尾，移除操作只能从另一端操作，这个叫队头。

一般来说，队列的实现方式有两种，数组和链表。数组来实现有两种方式：顺序队列和循环队列。用数组实现队列，若出现队满的情况，当有新的元素需要入队的时候，可是没有位置，这时候，要么丢掉，不管它，要么等待，等待时间由程序来控制。

实现顺序队列：

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class ArrayQueue {
	
	private final Object[] items;
	
	private int head = 0;
	
	private int tail = 0;
	
	/**
	 * 初始化队列
	 * @param capacity 队列长度
	 */
	public ArrayQueue(int capacity) {
		this.items = new Object[capacity];
	}
	
	/**
	 * 入队
	 * @param item
	 * @return
	 */
	public boolean put(Object item) {
		if (head == ((tail + 1) % items.length)) {
			//说明队满
			return false;
		}
		
		items[tail] = item;
		tail = (tail + 1) % items.length; //tail标记后移一位
		return true;
	}
	
	/**
	 * 获取队列头元素，不出队
	 * @return
	 */
	public Object peek() {
		if (head == tail) {
			//s说明对空
			return null;
		}
		
		return items[head];
	}
	
	/**
	 * 出队
	 * @return
	 */
	public Object poll() {
		if (head == tail) {
			//说明队空
			return null;
		}
		Object item = items[head];
		items[head] = null;//没用的元素赋空值，当然不设置也可以，反正标记移动之后会被覆盖
		head = (head +1 ) % items.length;//head标记后移一位
		return item;
	}
	
	public boolean isFull() {
		return head == (tail + 1) % items.length;
	}
	
	public boolean isEmpty() {
		return head == tail;
	}
	
	public int  Size() {
		if (tail >= head) {
			return tail - head;
		}else {
			return tail + items.length - head;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class ArrayQueueTest {
	
	public static void main(String[] args) {
		
		
		ArrayQueue queue = new ArrayQueue(4);
		System.out.println(queue.put("A"));//true
		System.out.println(queue.put("B"));//true
		System.out.println(queue.put("C"));//true
		System.out.println(queue.put("D"));//false
		
		System.out.println(queue.isFull());//true,队列已经满了，队列长度为4，因为是循环队列，最大存3个元素
		
		System.out.println(queue.Size());//3
		
		System.out.println(queue.peek());//A 获取队头元素，不出队
		System.out.println(queue.poll());//A
		System.out.println(queue.poll());//B
		System.out.println(queue.poll());//C
		
		System.out.println(queue.isEmpty());//true ,当前队列为空
	}
}

###队列的适用场景：

  1. 买东西，秒杀

    我们很容易想到这个场景，从网购秒杀商品，到排队买早餐。先进先出，先来先走

  2. 生产者和消费者模式

    还记得生产者和消费者模式吗? 生产者负责生产，生产之后放到传送带，消费者拿下来，这个模式实现起来，无非就是存在一个队列，若干个生产者向队列增加元素，若干个消费者从队列中获取元素。

世界再嘈杂，匠人的内心，绝对是必须是安静的、安定的。