如何实现栈和队列？[数据结构与算法][Java]

栈也是一种线性结构

  • 相比数组，栈相应的操作是数组的子集
  • 只能从一端添加元素，也只能从一端取出元素
    这一端称为栈顶
  • 栈是一种后进先出的数据结构

栈 Stack

  • 栈也是一种线性结构

  • 相比数组，栈相应的操作是数组的子集

  • 只能从一端添加元素，也只能从一端取出元素

    这一端称为栈顶

  • 栈是一种后进先出的数据结构

无处不在的Undo操作（撤销）

栈的应用

  • 程序调用的系统栈

系统调用A，B，C三个函数，调用时依次让A,B,C入栈。开始让A入栈然后中断，开始执行B；指向函数C时，B函数中断，C开始执行

程序调用的系统栈

栈的实现

Interface Stack<E> ArrayStack<E>

  • Void push(E)（添加元素） (implement)
  • E pop()（取出元素）
  • E peek()（查看栈顶元素）
  • int getSize() （查看多少元素）
  • boolean isEmpty() （查看是否为空）
  1. 从用户的角度看，支持这些操作就好
  2. 具体底层实现，用户不关心
  3. 实际底层有多种实现方式

我们在动态数组的基础上实现一个栈：

不要小瞧数组！[数据机构与算法]

1
2
3
4
5
6
7
8
9
10
11
//在动态数组条件下，我们实现一个栈非常方便了
package cn.shuzu;

public interface Stack<E> {

		int getSize();
		boolean isEmpty();
		void push(E e);
		E pop();
		E peek//在动态数组条件下，我们实现一个栈非常方便了
package cn.shuzu;

public interface Stack<E> {

		int getSize();
		boolean isEmpty();
		void push(E e);
		E pop();
		E peek();
}
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
package cn.shuzu;

public class ArrayStack<E> implements Stack<E> {
		
	Array<E> array;
	public ArrayStack(int capacity) {
		array = new Array<>(capacity);
	}
	
	public ArrayStack() {
		array = new Array<>();
	}
	
	@Override
	public int getSize() {
		return array.getsize();
	}
	
	@Override
	public boolean isEmpty() {
		return array.isEmpty();
	}
	
	public int getCapacity() {
		return array.getCapacity();
	}
	
	@Override
	public void push(E e) {
		array.addLast(e);
	}
	
	@Override
	public E pop() {
		return array.removeLast();
	}
	
	@Override
	public E peek() {
		return array.getLast();
	}
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("Stack: ");
		res.append('[');
		for (int i = 0; i < array.getsize(); i++) {
			res.append(array.get(i));
			if (i != array.getsize() - 1) {
				res.append(",");
			}
		}
		res.append("] top");
		return res.toString();
	}
	//Main函数
	public static void main(String[] args) {
		
		ArrayStack<Integer> stack = new ArrayStack<>();
		
		for (int i = 0; i < package cn.shuzu;

public class ArrayStack<E> implements Stack<E> {
		
	Array<E> array;
	public ArrayStack(int capacity) {
		array = new Array<>(capacity);
	}
	
	public ArrayStack() {
		array = new Array<>();
	}
	
	@Override
	public int getSize() {
		return array.getsize();
	}
	
	@Override
	public boolean isEmpty() {
		return array.isEmpty();
	}
	
	public int getCapacity() {
		return array.getCapacity();
	}
	
	@Override
	public void push(E e) {
		array.addLast(e);
	}
	
	@Override
	public E pop() {
		return array.removeLast();
	}
	
	@Override
	public E peek() {
		return array.getLast();
	}
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("Stack: ");
		res.append('[');
		for (int i = 0; i < array.getsize(); i++) {
			res.append(array.get(i));
			if (i != array.getsize() - 1) {
				res.append(",");
			}
		}
		res.append("] top");
		return res.toString();
	}
	//Main函数
	public static void main(String[] args) {
		
		ArrayStack<Integer> stack = new ArrayStack<>();
		
		for (int i = 0; i < 5; i++) {
			stack.push(i);
			System.out.println(stack);
		}
		
		stack.pop();
		System.out.println(stack);
	}
}

1
2
3
4
5
6
7
//我们的输出：
Stack: [0] top
Stack: [0,1] top
Stack: [0,1,2] top
Stack: [0,1,2,3] top
Stack: [0,1,2,3,4] top
Stack: [0,1,2,//我们的输出：
Stack: [0] top
Stack: [0,1] top
Stack: [0,1,2] top
Stack: [0,1,2,3] top
Stack: [0,1,2,3,4] top
Stack: [0,1,2,3] top

栈的复杂度分析

栈的另一个应用：括号匹配

  • 括号匹配 - 编译器

括号匹配

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
package cn.shuzu;
import	 java.util.Stack;

class Solution {

	public boolean isValid(String s) {
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (c == '(' || c == '[' || c == '{') 
				stack.push(c);
			else {
				if (stack.isEmpty()) 
					return false;
					
					char topChar = stack.pop();
					if (c == ')' && topChar != '(') {
						return false;
					}
					
					if (c == ']' && topChar != '[') {
						return false;
					}
					
					if (c == '}' && topChar != '{') {
						return false;
					}
				}
			}
		package cn.shuzu;
import	 java.util.Stack;

class Solution {

	public boolean isValid(String s) {
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (c == '(' || c == '[' || c == '{') 
				stack.push(c);
			else {
				if (stack.isEmpty()) 
					return false;
					
					char topChar = stack.pop();
					if (c == ')' && topChar != '(') {
						return false;
					}
					
					if (c == ']' && topChar != '[') {
						return false;
					}
					
					if (c == '}' && topChar != '{') {
						return false;
					}
				}
			}
		return stack.isEmpty();
	}
}

队列 Queue

  • 队列也是一种线性结构
  • 相比数组，队列对应的操作是数组的子集
  • 只能从一端（队尾）添加元素，只能从另一端（队首）取出元素
  • 队列是一种先进先出的数据结构（先到先得）

Queue<E>

  • void enqueue(E) （入队）
  • E dequeue() （出队）
  • E getFront()（查看队首元素）
  • int getSize() （查看多少元素）
  • boolean isEmpty() （是否为空）
1
2
3
4
5
6
7
8
9
10
package cn.shuzu;

public interface Queue<E> {

		int getSize();
		boolean isEmpty();
		void enqueue(E e);
		E	dequeue();
		E	getFrontpackage cn.shuzu;

public interface Queue<E> {

		int getSize();
		boolean isEmpty();
		void enqueue(E e);
		E	dequeue();
		E	getFront();
}
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
package cn.shuzu;

public class ArrayQueue<E>  implements Queue<E>{

	private Array<E> array;
	
	public ArrayQueue(int capacity) {
		// TODO Auto-generated constructor stub
		array = new Array<>(capacity);
	}

	public ArrayQueue() {
		array = new Array<>();
	}
	
	@Override
	public int getSize() {
		return array.getsize();
	}
	
	@Override
	public boolean isEmpty() {
		return array.isEmpty();
	}
	
	public int getCapacity() {
		return array.getCapacity();
	}
	
	@Override
	public void enqueue(E e) {
		array.addLast(e);
	}
	
	@Override
	public E dequeue() {
		return array.removeFirst();
	}
	
	@Override
	public E getFront() {
		return array.getFirst();
	}
	
	@Override
	public String toString() {
		StringBuilder  res = new StringBuilder();
		res.append("Queue: ");
		res.append("front [");
		for (int i = 0; i < array.getsize(); i++) {
			res.append(array.get(i));
			if (i != array.getsize() -1) {
				res.append(",");
			}
		}
		res.append("] tail");
		return res.toString();
	}
	
	public static void main(String[] args) {
		
		ArrayQueue<Integer> queue = new ArrayQueue<Integer>();
		for (int i = 0; i < 10; i++) {
			queue.enqueue(i);
			System.out.println(queue);
			
			if (i % 3 == package cn.shuzu;

public class ArrayQueue<E>  implements Queue<E>{

	private Array<E> array;
	
	public ArrayQueue(int capacity) {
		// TODO Auto-generated constructor stub
		array = new Array<>(capacity);
	}

	public ArrayQueue() {
		array = new Array<>();
	}
	
	@Override
	public int getSize() {
		return array.getsize();
	}
	
	@Override
	public boolean isEmpty() {
		return array.isEmpty();
	}
	
	public int getCapacity() {
		return array.getCapacity();
	}
	
	@Override
	public void enqueue(E e) {
		array.addLast(e);
	}
	
	@Override
	public E dequeue() {
		return array.removeFirst();
	}
	
	@Override
	public E getFront() {
		return array.getFirst();
	}
	
	@Override
	public String toString() {
		StringBuilder  res = new StringBuilder();
		res.append("Queue: ");
		res.append("front [");
		for (int i = 0; i < array.getsize(); i++) {
			res.append(array.get(i));
			if (i != array.getsize() -1) {
				res.append(",");
			}
		}
		res.append("] tail");
		return res.toString();
	}
	
	public static void main(String[] args) {
		
		ArrayQueue<Integer> queue = new ArrayQueue<Integer>();
		for (int i = 0; i < 10; i++) {
			queue.enqueue(i);
			System.out.println(queue);
			
			if (i % 3 == 2) {
				queue.dequeue();
				System.out.println(queue);
			}
		}
	}
}

数组队列的复杂度分析

循环队列的实现

  • front == tail 队列为空
  • (tail + 1) % capacity == front 队列满
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package cn.shuzu;

public class LoopQueue<E> implements Queue<E> {

	private E[] data;
	private int front,tail;
	private int size;
			
	public LoopQueue(int capacity) {
		// TODO Auto-generated constructor stub
			data = (E[])new Object[capacity + 1];
			front = 0;
			tail = 0;
			size = 0;
	}
	
	public LoopQueue() {
		this(10);
	}
	
	public int getCapacity() {
		return data.length - 1;
	}
	
	@Override
	public boolean isEmpty() {
		return front == tail;
	}
	
	@Override
	public int getSize() {
		return size;
	}

	@Override
	public void enqueue(E e) {
		
		if ((tail+ 1) % data.length == front) {
			resize(getCapacity() * 2);
		}
		
		data[tail] = e;
		tail = (tail + 1) % data.length;
		size ++;
	}
	
	@Override
	public E dequeue() {
		
		if(isEmpty())
			throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
	
		E ret = data[front];
		data[front] = null;
		front = (front + 1) % data.length;
		size --;
		
		if (size == getCapacity() / 4 && getCapacity() / 2 != 0 ) {
			resize(getCapacity() / 2);
		}
		return ret;
	}
	
	@Override
	public E getFront() {
		if (isEmpty()) {
			throw new IllegalArgumentException("Queue is empty.");
		}
		return data[front];
	}
	
	@Override
	public String toString() {
		StringBuilder  res = new StringBuilder();
		res.append(String.format("Queue: size = %d, capacity = %d\n", size,getCapacity()));
		res.append("front [");
		for (int i = front; i != tail ; i = (i + 1) % data.length ) {
			res.append(data[i]);
			if ((i + 1) % data.length != data.length) {
				res.append(",");
			}
		}
		res.append("] tail");
		return res.toString();
	}
	
	private void resize(int  newCapacity) {
		
		E[] newData = (E[])new Object[newCapacity + 1];
		for (int i = 0; i < size; i++) {
			newData[i] = data[(i + front) % data.length];
		}
		
		data = newData;
		front = 0;
		tail = size;
	}
	
	public static void main(String[] args) {
		
		LoopQueue<Integer> queue = new LoopQueue<Integer>();
		for (int i = 0; i < 10; i++) {
			queue.enqueue(i);
			System.out.println(queue);
			
			if (i % 3 == package cn.shuzu;

public class LoopQueue<E> implements Queue<E> {

	private E[] data;
	private int front,tail;
	private int size;
			
	public LoopQueue(int capacity) {
		// TODO Auto-generated constructor stub
			data = (E[])new Object[capacity + 1];
			front = 0;
			tail = 0;
			size = 0;
	}
	
	public LoopQueue() {
		this(10);
	}
	
	public int getCapacity() {
		return data.length - 1;
	}
	
	@Override
	public boolean isEmpty() {
		return front == tail;
	}
	
	@Override
	public int getSize() {
		return size;
	}

	@Override
	public void enqueue(E e) {
		
		if ((tail+ 1) % data.length == front) {
			resize(getCapacity() * 2);
		}
		
		data[tail] = e;
		tail = (tail + 1) % data.length;
		size ++;
	}
	
	@Override
	public E dequeue() {
		
		if(isEmpty())
			throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
	
		E ret = data[front];
		data[front] = null;
		front = (front + 1) % data.length;
		size --;
		
		if (size == getCapacity() / 4 && getCapacity() / 2 != 0 ) {
			resize(getCapacity() / 2);
		}
		return ret;
	}
	
	@Override
	public E getFront() {
		if (isEmpty()) {
			throw new IllegalArgumentException("Queue is empty.");
		}
		return data[front];
	}
	
	@Override
	public String toString() {
		StringBuilder  res = new StringBuilder();
		res.append(String.format("Queue: size = %d, capacity = %d\n", size,getCapacity()));
		res.append("front [");
		for (int i = front; i != tail ; i = (i + 1) % data.length ) {
			res.append(data[i]);
			if ((i + 1) % data.length != data.length) {
				res.append(",");
			}
		}
		res.append("] tail");
		return res.toString();
	}
	
	private void resize(int  newCapacity) {
		
		E[] newData = (E[])new Object[newCapacity + 1];
		for (int i = 0; i < size; i++) {
			newData[i] = data[(i + front) % data.length];
		}
		
		data = newData;
		front = 0;
		tail = size;
	}
	
	public static void main(String[] args) {
		
		LoopQueue<Integer> queue = new LoopQueue<Integer>();
		for (int i = 0; i < 10; i++) {
			queue.enqueue(i);
			System.out.println(queue);
			
			if (i % 3 == 2) {
				queue.dequeue();
				System.out.println(queue);
			}
		}
	}
	
}
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
//打印输出
Queue: size = 1, capacity = 10
front [0,] tail
Queue: size = 2, capacity = 10
front [0,1,] tail
Queue: size = 3, capacity = 10
front [0,1,2,] tail
Queue: size = 2, capacity = 5
front [1,2,] tail
Queue: size = 3, capacity = 5
front [1,2,3,] tail
Queue: size = 4, capacity = 5
front [1,2,3,4,] tail
Queue: size = 5, capacity = 5
front [1,2,3,4,5,] tail
Queue: size = 4, capacity = 5
front [2,3,4,5,] tail
Queue: size = 5, capacity = 5
front [2,3,4,5,6,] tail
Queue: size = 6, capacity = 10
front [2,3,4,5,6,7,] tail
Queue: size = 7, capacity = 10
front [2,3,4,5,6,7,8,] tail
Queue: size = 6, capacity = 10
front [3,4,5,6,7,8,] tail
Queue: size = 7, capacity = 10
front [3,4,5,6,7,8,//打印输出
Queue: size = 1, capacity = 10
front [0,] tail
Queue: size = 2, capacity = 10
front [0,1,] tail
Queue: size = 3, capacity = 10
front [0,1,2,] tail
Queue: size = 2, capacity = 5
front [1,2,] tail
Queue: size = 3, capacity = 5
front [1,2,3,] tail
Queue: size = 4, capacity = 5
front [1,2,3,4,] tail
Queue: size = 5, capacity = 5
front [1,2,3,4,5,] tail
Queue: size = 4, capacity = 5
front [2,3,4,5,] tail
Queue: size = 5, capacity = 5
front [2,3,4,5,6,] tail
Queue: size = 6, capacity = 10
front [2,3,4,5,6,7,] tail
Queue: size = 7, capacity = 10
front [2,3,4,5,6,7,8,] tail
Queue: size = 6, capacity = 10
front [3,4,5,6,7,8,] tail
Queue: size = 7, capacity = 10
front [3,4,5,6,7,8,9,] tail

循环队列的复杂度分析

循环队列和数组队列的比较

我们用十万次入队和出队操作的时间进行比较

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
package cn.shuzu;

import java.util.Random;

public class Main01 {

	//测试使用q运行opcount个enqueue和dequeue操作所需要的时间，单位：秒
	private static double testQueue(Queue<Integer> q,int opCount) {
		
		long startTime = System.nanoTime();
		
		Random random = new Random();
		for (int i = 0; i < opCount; i++) {
			q.enqueue(random.nextInt(Integer.MAX_VALUE));
		}
		for (int i = 0; i < opCount; i++) {
			q.dequeue();
		}
		
		long endTime = System.nanoTime();
		
		return (endTime - startTime) / 1000000000.0;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int opCount = 100000;
		
		ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
		double time1 = testQueue(arrayQueue, opCount);
		System.out.println("ArrayQueue,time : " + time1 + "s");
		
		LoopQueue<Integer> LoopQueue = new LoopQueue<Integer>();
		double time2 = testQueue(arrayQueue, opCount);
		System.out.println("LoopQueue,time : " + time2 + package cn.shuzu;

import java.util.Random;

public class Main01 {

	//测试使用q运行opcount个enqueue和dequeue操作所需要的时间，单位：秒
	private static double testQueue(Queue<Integer> q,int opCount) {
		
		long startTime = System.nanoTime();
		
		Random random = new Random();
		for (int i = 0; i < opCount; i++) {
			q.enqueue(random.nextInt(Integer.MAX_VALUE));
		}
		for (int i = 0; i < opCount; i++) {
			q.dequeue();
		}
		
		long endTime = System.nanoTime();
		
		return (endTime - startTime) / 1000000000.0;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int opCount = 100000;
		
		ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
		double time1 = testQueue(arrayQueue, opCount);
		System.out.println("ArrayQueue,time : " + time1 + "s");
		
		LoopQueue<Integer> LoopQueue = new LoopQueue<Integer>();
		double time2 = testQueue(arrayQueue, opCount);
		System.out.println("LoopQueue,time : " + time2 + "s");
		
	}
}

十万次入队出队的时间比较