栈和队列的理解

妖狐艹你老母 2024-04-01 09:49 87阅读 0赞

**一.栈**

**1.1** **概念**

**栈** ：一种 **特殊的线性表** ，其 **只允许在固定的一端进行插入和删除元素操作** 。 进行数据插入和删除操作的一端称为栈

顶，另一端称为栈底。 **栈中的数据元素遵守后进先出** **LIFO** **（** **Last In First Out** **）的原则。**

**压栈：栈的插入操作叫做进栈** **/** **压栈** **/** **入栈，** **入数据在栈顶** **。**

**出栈：栈的删除操作叫做出栈。** **出数据在栈顶** **。** **栈** **：一种特殊的线性表，其** **只允许在固定的一端进行插入和删除元素操作** **。进行数据插入和删除操作的一端称为栈**

**顶，另一端称为栈底。栈中的数据元素遵守后进先出** **LIFO** **（** **Last In First Out** **）的原则。**

压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， **入数据在栈顶** 。

出栈：栈的删除操作叫做出栈。 **出数据在栈顶** 。

![384c232c9d494ef3ab00fed37ac2f337.png][]

![d5b5e006e307419d97f7e6f96b03c644.png][]

**1.2栈在现实生活中的例子：**

![4c984c7a6efd4f569656f893cde1ddf5.png][]

![c309ceb7c9f9438abacf6a5126288bc1.png][]

public static void main ( String \[\] args ) \{

Stack < Integer > s = new Stack ();

s . push ( 1 );

s . push ( 2 );

s . push ( 3 );

s . push ( 4 );

System . out . println ( s . size ()); // 获取栈中有效元素个数 \---> 4

System . out . println ( s . peek ()); // 获取栈顶元素 \---> 4

s . pop (); // 4 出栈，栈中剩余 1 2 3 ，栈顶元素为 3

System . out . println ( s . pop ()); // 3 出栈，栈中剩余 1 2 栈顶元素为 3

if ( s . empty ())\{

System . out . println ( " 栈空 " );

\} else \{

System . out . println ( s . size ());

**1.3** **栈的模拟实现**

![ac56c85e05a24e8b9eb18e0c4709da89.png][]

从上图中可以看到， **Stack** **继承了** **Vector** **，** **Vector** **和** **ArrayList** **类似，都是动态的顺序表** ，不同的是 **Vector** **是线程安** **全的。**

public class MyStack \{

int \[\] array ;

int size ;

public MyStack ()\{

array = new int \[ 3 \];

public int push ( int e )\{

ensureCapacity ();

array \[ size \++ \] = e ;

return e ;

public int pop ()\{

int e = peek ();

size \-- ;

return e ;

public int peek ()\{

if ( empty ())\{

throw new RuntimeException ( " 栈为空，无法获取栈顶元素 " );

return array \[ size \- 1 \];

public int size ()\{

return size ;

public boolean empty ()\{

return 0 == size ;

private void ensureCapacity ()\{

if ( size == array . length )\{

array = Arrays . copyOf ( array , size \* 2 );

**1.4** **栈的应用场景**

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

2. 一个栈的初始状态为空。现将元素 1 、 2 、 3 、 4 、 5 、 A 、 B 、 C 、 D 、 E 依次入栈，然后再依次出栈，则元素出栈的顺

序是（ ）。

A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA

2. **将递归转化为循环**

比如：逆序打印链表

// 递归方式

void printList ( Node head )\{

if ( null != head )\{

printList ( head . next );

System . out . print ( head . val \+ " " );

// 循环方式

void printList ( Node head )\{

if ( null == head )\{

return ;

Stack < Node > s = new Stack <> ();

// 将链表中的结点保存在栈中

Node cur = head ;

while ( null != cur )\{

s . push ( cur );

cur = cur . next ;

// 将栈中的元素出栈

while ( ! s . empty ())\{

System . out . print ( s . pop (). val \+ " " );

**1.5** **概念区分**

栈、虚拟机栈、栈帧有什么区别呢？

![388304f10dc245809fdf57a4577ea446.png][]

**二.队列**

**2.1** **概念**

**队列** ：只允许 **在一端进行插入数据操作** ， **在另一端进行删除数据操作的特殊线性表** ，队列具有先进先出 FIFO(First

In First Out) 入队列： **进行插入操作的一端称为** **队尾（** **Tail/Rear** **）** **出队列：进行删除操作的一端称为** **队头**

**（** **Head/Front** **）**

![732bf7a1c3ef42db982c65d70084b3f4.png][]

**2.2** **队列的使用**

在 Java 中， **Queue** **是个** **接口** **，** **底层是通过链表实现** 的。

![3560d23990e34c199ac799991cde89f3.png][]

![f353696392ed4777a07a7af129661a44.png][]

public static void main ( String \[\] args ) \{

Queue < Integer > q = new LinkedList <> ();

q . offffer ( 1 );

q . offffer ( 2 );

q . offffer ( 3 );

q . offffer ( 4 );

q . offffer ( 5 ); // 从队尾入队列

System . out . println ( q . size ());

System . out . println ( q . peek ()); // 获取队头元素

q . poll ();

System . out . println ( q . poll ()); // 从队头出队列，并将删除的元素返回

if ( q . isEmpty ())\{

System . out . println ( " 队列空 " );

\} else \{

System . out . println ( q . size ());

**2.3** **队列模拟实现**

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有

两种： **顺序结构 和 链式结构** 。同学们思考下： **队列的实现使用顺序结构还是链式结构好？**

![7d6d271fb0b64119ac7d0bc18af1f55c.png][]

public class Queue \{

// 双向链表节点

public static class ListNode \{

ListNode next ;

ListNode prev ;

int value ;

ListNode ( int value )\{

this . value = value ;

ListNode fifirst ; // 队头

ListNode last ; // 队尾

int size = 0 ;

// 入队列 \--- 向双向链表位置插入新节点

public void offffer ( int e )\{

ListNode newNode = new ListNode ( e );

if ( fifirst == null )\{

fifirst = newNode ;

// last = newNode;

\} else \{

last . next = newNode ;

newNode . prev = last ;

// last = newNode;

last = newNode ;

size \++ ;

// 出队列 \--- 将双向链表第一个节点删除掉

public int poll ()\{

// 1. 队列为空

// 2. 队列中只有一个元素 \---- 链表中只有一个节点 \--- 直接删除

// 3. 队列中有多个元素 \--- 链表中有多个节点 \---- 将第一个节点删除

int value = 0 ;

if ( fifirst == null )\{

return null ;

\} else if ( fifirst == last )\{

last = null ;

fifirst = null ;

\} else \{

value = fifirst . value ;

fifirst = fifirst . next ;

fifirst . prev . next = null ;

fifirst . prev = null ;

\-- size ;

return value ;

// 获取队头元素 \--- 获取链表中第一个节点的值域

public int peek ()\{

if ( fifirst == null )\{

return null ;

return fifirst . value ;

public int size () \{

return size ;

public boolean isEmpty ()\{

return fifirst == null ;

**2.4** **循环队列**

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。

环形队列通常使用数组实现。

![d840acd0ebc54facae5da958b301a184.png][]

**数组下标循环的小技巧**

1. 下标最后再往后 (offffset 小于 array.length): index = (index + offffset) % array.length

![b5ce83eccb2848e0a8ae2137c55f5368.png][]

2. 下标最前再往前 (offffset 小于 array.length): index = (index + array.length - offffset) % array.length

![ef6004c50af94b7e972e6b8f75ec90e5.png][]

**如何区分空与满**

1. 通过添加 size 属性记录

2. 保留一个位置

3. 使用标记

![59df21661a2446fd92e91d18cdee5c3f.png][]

**在这里我们进行简单理解，在OJ题的相关笔记中会对此进行更加详细的介绍**

**3.** **双端队列** **(Deque)**

双端队列（ deque ）是指允许两端都可以进行入队和出队操作的队列， deque 是 “double ended queue” 的简称。

那就说明元素可以从队头出队和入队，也可以在队尾出队和入队。

![646a25d169ce41dfb84a42bdfb1b845f.png][]

Deque 是一个接口，使用时必须创建 LinkedList 的对象。

![576c6910c5364f0fa588412cb822036b.png][]

[384c232c9d494ef3ab00fed37ac2f337.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e38a55e2a5cb42b7aa8df8000f8d9922.png
[d5b5e006e307419d97f7e6f96b03c644.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f1efb9a1059544fe8ccd4ad1a511fca6.png
[4c984c7a6efd4f569656f893cde1ddf5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/37029464d1d8451cb0fd117169353659.png
[c309ceb7c9f9438abacf6a5126288bc1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d168f289d97f475093a02b442adde546.png
[ac56c85e05a24e8b9eb18e0c4709da89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6ccc2a75629a44f6a8df6582eaf53ae9.png
[388304f10dc245809fdf57a4577ea446.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f39e5a8acef24165a9164ba210b5e94c.png
[732bf7a1c3ef42db982c65d70084b3f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/be34f324dcbd491ebaea161d740442e6.png
[3560d23990e34c199ac799991cde89f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e7942af77adb4f2aaa0cf56748fee7e6.png
[f353696392ed4777a07a7af129661a44.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/806abe625171456d806343a9d955b892.png
[7d6d271fb0b64119ac7d0bc18af1f55c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a5390c8a4a9e4a1eb0b0d892e2b03531.png
[d840acd0ebc54facae5da958b301a184.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/dadd030eeb984dad822aa230dbcc81a8.png
[b5ce83eccb2848e0a8ae2137c55f5368.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ed4bec6c89e34739b1dc15df3c6d2229.png
[ef6004c50af94b7e972e6b8f75ec90e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0ae9a1fd091a4d9b99ffe1c27d59c34f.png
[59df21661a2446fd92e91d18cdee5c3f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9d36aa97110449c1995f01a81e91e5d6.png
[646a25d169ce41dfb84a42bdfb1b845f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/37e36baa5fd74afb901ec9272335c1a9.png
[576c6910c5364f0fa588412cb822036b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e373f993e4b24451a63a6b71eb1938f3.png