【数据结构】栈和队列

水深无声 2022-12-12 04:53 210阅读 0赞

## 栈 ##

栈是一种重要的线性结构。是我们前面讲过的线性表的一种具体形式  
**栈是限定仅在表尾进行插入和删除操作的线性表**  
由于栈本身就是一个线性表，那么我们讲的线性表的顺序存储和链式存储，对于栈来说，都是适用的。

我们把允许插入和删除的一端称为栈顶top,另一端称为栈底bottom,不含任何元素的栈称为空栈。  
栈又称为后进先出（Last In First Out）的线性表，简称LIFO

栈的插入操作，叫做进栈，也称为压栈，入栈  
栈的删除操作，叫做出栈，也称为弹栈

## 抽象数据结构 ##

ADT 栈(stack)
    Data
        同线性表。元素具有相同的类型，相邻元素具有前驱和后继的关系。
    
    Operation
        InitStack( *s): 初始化操作，建立一个空栈
        ClearStack( *s): 将栈清空
        StackEmpty( s): 若栈存在，返回true，否则返回false
        StackLength( s): 返回栈S的元素个数
    
        GetTop( s, *e): 若是栈存在且非空，用e返回S的栈顶元素
        Push( *s, e):若是栈存在，则插入新的元素e到栈S中并成为栈顶元素
        Pop( *s, *e):若是栈存在且非空，删除栈顶元素，并用e返回其值
        DestroyStack( *s): 若是栈存在，则销毁他
    endADT

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5X3RlZW1v_size_16_color_FFFFFF_t_70_pic_center]

## 存储方式 ##

和线性表一样，都有顺序存储和链式存储。  
优势和缺点一模一样。

实现起来的区别就是：栈没有中间插入和查找，都是从尾端操作。

## 实现 ##

[顺序栈 C++版][C]  
[链栈 C++版][C 1]

## 共享栈操作 ##

对于此消彼长的情况，可以使用共享栈来节约空间。  
![在这里插入图片描述][20201006200755489.png_pic_center]

## 队列 ##

**是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。**  
与栈相反，队列是先进先出(First In First Out:FIFO)的线性表。  
与栈相同：队列也是一种重要的线性结构，实现一个队列同样需要顺序表或者链表来作为基础。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5X3RlZW1v_size_16_color_FFFFFF_t_70_pic_center 1]

## 抽象数据结构 ##

ADT 队列(Queue)
    
    Data
        同线性表。元素具有相同的类型，相邻元素具有前驱和后继的关系。
    
    Operation
        InitQueue( *Q): 初始化操作，建立一个空队列Q
        ClearQueue( *Q): 将队列清空
        QueueEmpty( Q): 若队列为空，返回true，否则返回false
        QueueLength( Q): 返回队列Q的元素个数
    
        GetHead( Q, *e): 若是队列存在且非空，用e返回Q的队头元素
        EnQueue( *Q, e):若是队列存在，则插入新的元素e入队为队尾
        DeQueue( *Q, *e):若是队列存在且非空，进行出队操作，用e接收数据
        DestroyQueue( *Q): 若是队列存在，则销毁他
    endADT

## 实现 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5X3RlZW1v_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/fc91abef55b748c9b2c4773acae36e0d.png
[C]: https://blog.csdn.net/happy_teemo/article/details/52185119
[C 1]: https://blog.csdn.net/happy_teemo/article/details/52185124
[20201006200755489.png_pic_center]: /images/20221123/e0205a7b15c24bd994bcceeb547d09a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5X3RlZW1v_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/3706a0cbf1014ac0a4fe8742a509319f.png