数据结构与算法(4)_栈

发表于 | 分类于

如何理解栈

后进先出,先进后出,这就是典型的栈结构.就像一摞盘子叠在一起,从下往上一个一个放,从上往下一个一个取.

栈是一种”操作受限”的线性表,只允许在一段插入和删除数据.

当某个数据集合只涉及一端插入和删除数据,并且满足后进先出,先进后出的特性,我们就应该首选”栈”这种结构

如何实现一个栈

栈既可以用数组来实现,也可以用链表实现.用数组实现的栈叫顺序栈.用链表实现的栈,叫做链式栈.

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
//基于数组实现
public class  ArrayStack{
	private String[] items; //数组
	private int count;  //栈中元素
	private int n;	//栈的大小

	public ArrayStack(int n){
		items = new String[n];
		this.n = n;
		this.count = 0;
	}

	//入栈操作
	public boolean push(String item){
		if(count >= n) return false;
		items[count] = item;
		count++;
		return true;
	}

	//出栈操作
	public String pop(){
		if(count == 0) return null;
		String tmp = items[count - 1];
		count--;
		return tmp;
	}
}

//基于链表实现
public class StackBasedLinkedList{
	private Node top = null;
	
	//入栈操作
	public void push(int value){
		Node newNode = new Node(value,null);
		if(top == null){
			top = newNode;
		}else{
			newNode.next = top;
			top = newNode;
		}
	}
	
	//出栈操作, -1表示栈中无数据
	public int pop(){
		if(top == null) return -1;
		int value =  top.data;
		top = top.next;
		return value;
	}

	private static class Node {
		private int data;
		private Node next;

		public Node(int data, Node next) {
			this.data = data;
			this.next = next;
		}

		public int getData() {
			return data;
		}
	}
}

在入栈出栈的过程中,只需要一两个临时变量的存储空间,所以空间复杂度为O(1); 我们所说的空间复杂度,是指原本数据存储空间外,算法运行还需要的额外空间

不管顺序栈还是链式栈,入栈出栈只涉及栈顶个别数据操作所以,时间复杂度为O(1);

支持动态扩容的顺序栈

只需依赖一个动态扩容的数组就行.

  • 出栈的时间复杂度还是O(1).
  • 入栈的最好情况复杂度是O(1),最坏情况时间复杂度是O(n).平均时间复杂度(均摊)为O(1).