数据结构-栈和队列

栈和队列–操作受限的线性表

栈Stack

栈又称堆栈,它是操作受限制的线性表。

其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行插入、查找、删除操作。表中进行插入、删除操作的一端称为栈顶(top),栈顶保存的元素称为栈顶元素。相对的,表的另一端称为栈底

当栈中没有数据元素时称为空栈;向一个栈插入元素又称为进栈或者入栈;从一个栈中删除元素又称为出栈或者退栈;由于栈的插入和删除操作仅在栈顶进行,后进栈的元素必定先出栈,所以又把栈称为后进先出表(Last In First Out)。

针对栈的专业词汇:push 、pop、peek

1
2
3
4
5
6
7
public interface Stack<E>{
public int size();
public boolean isEmpty(); //判断堆栈是否为空
public void push(E e); //数据元素e入栈
public Object pop(); //栈顶元素出栈
public Object 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
public class MyStack<E> implements Stack<E> {
private int size;
private Node top;
private static class Node<E>{
E data;
Node<E> prev;
Node<E> next;
public Node(E data) {
this.data = data;
}
public Node(E data, Node<E> prev, Node<E> next) {
this.data = data;
this.prev = prev;
this.next = next;
}
}
public MyStack() {
top = null;
size = 0;
}

@Override
public boolean isEmpty() {
return size==0;
}

@Override
public void push(E e) {
if(top==null){
top = new Node<E>(e);
}
else{
top.next = new Node<E>(e,top,null);
top = top.next;
}
size++;
}
@Override
public E pop() {
if(top==null){
return null;
}
else{
E e = (E)top.data;
top = top.prev;
size--;
return e;
}
}
@Override
public E peek() {
if(top==null){
return null;
}
else{
return (E)top.data;
}
}

@Override
public int size() {
return size;
}
}

队列queue

队列(queue)简称队,它同堆栈一样,也是一种运算受限的线性表。

其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾(rear),删除数据元素的一端称为队首(front)

向队尾插入元素称为入队,新元素入队后成为新的队尾元素。从队列中删除元素称为出队,元素出队后,其后续元素称为新的队首元素。由于队列的插入和删除操作分别在队尾和队首进行,每个元素必然按照进入的次序离队,所以称队列为先进先出表(First In First Out)。

Queue使用要使用offer()来加入元素,使用poll()来获取并移出元素。如果要使用前端而不移出该元素,使用element()或者peek()方法。

队列的存储结构:由于数组的局限性,先进先出会导致大量空间丢失,我们使用循环数组作为存储结构。

下面我们人工实现主要功能:

1
2
3
4
5
6
7
public interface Queue<E> {
public int size();
public boolean isEmpty();
public void offer(E e);
public E poll();
public 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
public class MyQueue<E> implements Queue<E> {
//双向链表即可
private int size;
private QNode first;
private QNode last;
private static class QNode<E>{
E data;
QNode prev;
QNode next;
private QNode(E data, QNode prev, QNode next) {
super();
this.data = data;
this.prev = prev;
this.next = next;
}
}
private MyQueue() {
size = 0;
first = null;
last = null;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size==0;
}
public void offer(E e) {
if(first==null){
first = new QNode(e,null,null);
last = first;
}
else{
last.next = new QNode(e,last,null);
last = last.next;
}
size++;
}

public E poll() {
if(first==null){
return null;
}
else{
E tmp = (E)first.data;
size--;
first = first.next;
if(first!=null) first.prev = null;
return tmp;
}
}

public E peek() {
if(first==null){
return null;
}
else{
return (E)first.data;
}
}
}

双端队列

双端队列:即两端都可以输入与输出,双端队列既可以用来队列操作,也可以用来实现栈操作

输出受限的双端队列:一个端点允许删除和插入,另一端只允许插入。

输入受限的双端队列:一个端点只允许删除,另一端允许删除和插入。

Java中,Deque是一个线性collection,支持在两端插入和删除元素,其中dequedouble ended queue的缩写。此接口定义了双端队列两端访问元素的方法,支持从两端插入、移除和检查元素。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(null或者false,具体取决于操作)。插入操作的后一种形式是专门为使用有容量限制的deque实现设计的,具体如下表。

操作 抛出异常 返回特殊值
插入 addFirst(e) offerFirst(e)
插入 addLast(e) offerLast(e)
删除 removeFirst(e) pollFirst(e)
删除 removeLast(e) pollLast(e)
检查 getFirst(e) peekFirst(e)
检查 getLast(e) peekLast(e)

Java中的栈和队列

Stack类:栈类 过时 我们平时已经不再经常使用该类了,改用下面的Deque。

1
public class Stack<E> extends Vector<E>{}

Queue接口:队列接口 不是实现类。我们经常使用LinkedList这个实现类,当然,还有其他的实现类,其自行查看对应的API。

Queue方法 等效Deque方法
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()

Deque接口:双端队列,栈操作时建议使用,这个也是接口。我们常用的实现类也是LinkedList(),其余实现类自行查看API。

堆栈方法 等效Deque方法
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()

下面是查看源码后发现的内部构造:

1
2
3
4
5
6
7
8
//Queue的父接口是Collection
public interface Queue<E> extends Collection<E> {
...
}
//Deque的父接口是Queue
public interface Deque<E> extends Queue<E> {
...
}

Queue使用时尽量避免Collectionadd()remove()方法,而是要使用offer()来加入元素,使用poll()来获取并移出元素。它们的优点是可以通过返回值判断成功与否,add()remove()方法在失败的时候会抛出异常。如果要使用前端而不移出该元素,使用element()或者peek()方法。

代码实现:通过查看API我们可以发现,Java中实现栈和队列操作都可以通过使用LinkedList类实现,底层使用的是链表。当然,我们也可以使用ArrayDeque来实现Deque接口,ArrayDeque底层是大小可变数组。

栈的实现案例–将10进制转换成2进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

/**
* 栈的初步应用:将10进制转换成2进制
* @author x1aolin
*/
public class MyStack {
public static void main(String[] args) {
Deque<Integer> stack = new LinkedList<>();
Scanner sc = new Scanner(System.in);
System.out.print("Please input a number: ");
int num = sc.nextInt();
while(num!=0){
stack.push(num%2);
num /= 2;
}
System.out.print("The result is ");
while(!stack.isEmpty())
System.out.print(stack.pop());
}
}
您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------