数据结构之----栈、队列、双向队列_先入后出的线性结构是

数据结构之----栈、队列、双向队列

什么是栈？

栈是一种遵循先入后出的逻辑的线性数据结构。

我们可以将栈类比为桌面上的一摞盘子，如果需要拿出底部的盘子，则需要先将上面的盘子依次取出。将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈数据结构。

如图所示，我们把堆叠元素的顶部称为 栈顶 ，底部称为 栈底 。将把元素添加到栈顶的操作叫做入栈，删除栈顶元素的操作叫做 出栈 。

栈常用操作

栈的常用操作如表所示，具体的方法名需要根据所使用的编程语言来确定。在此，我们以常见的 push ( ) 、pop ( ) 、peek ( ) 命名为例。

一般情况下，我们可以直接使用编程语言内置的栈类。然而，某些语言可能没有专门提供栈类，这时我们可以将该语言的数组或链表视作栈来使用，并在程序逻辑上忽略与栈无关的操作。

如：

/* 初始化栈 */
Stack<Integer> stack = new Stack<>();

/* 元素入栈 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);

/* 访问栈顶元素 */
int peek = stack.peek();

/* 元素出栈 */
int pop = stack.pop();

/* 获取栈的长度 */
int size = stack.size();

/* 判断是否为空 */
boolean isEmpty = stack.isEmpty();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

栈的实现

栈遵循先入后出的原则，因此我们只能在栈顶添加或删除元素。

然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以被视为一种受限制的数组或链表。换句话说，我们可以 屏蔽 数组或链表的部分无关操作，使其对外表现的逻辑符合栈的特性。

1.基于链表来实现

使用链表来实现栈时，我们可以将链表的头节点视为栈顶，尾节点视为栈底。

如图所示，对于入栈操作，我们只需将元素插入链表头部，这种节点插入方法被称为 头插法。而对于出栈操作，只需将头节点从链表中删除即可。



以下是基于链表实现栈的示例代码：

/* 基于链表实现的栈 */
class LinkedListStack {
	private ListNode stackPeek; // 将头节点作为栈顶
	private int stkSize = 0; // 栈的长度
	public LinkedListStack() {
		stackPeek = null;
	}

	/* 获取栈的长度 */
	public int size() {
		return stkSize;
	}

	/* 判断栈是否为空 */
	public boolean isEmpty() {
		return size() == 0;
	}

	/* 入栈 */
	public void push(int num) {
		ListNode node = new ListNode(num);
		node.next = stackPeek;
		stackPeek = node;
		stkSize++;
	}

	/* 出栈 */
	public int pop() {
		int num = peek();
		stackPeek = stackPeek.next;
		stkSize--;
		return num;
	}

	/* 访问栈顶元素 */
	public int peek() {
		if (isEmpty())
		throw new IndexOutOfBoundsException();
		return stackPeek.val;
	}

	/* 将 List 转化为 Array 并返回 */
	public int[] toArray() {
		ListNode node = stackPeek;
		int[] res = new int[size()];
		for (int i = res.length - 1; i >= 0; i--) {
			res[i] = node.val;
			node = node.next;
		}
		return res;
	}
}
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

2.基于数组的实现

使用数组实现栈时，我们可以将数组的尾部作为栈顶。

如图所示，入栈与出栈操作分别对应在数组尾部添加元素与删除元素，时间复杂度都为