数据结构——栈和队列

红太狼 2022-06-17 00:42 393阅读 0赞

# 数据结构——栈和队列 #

## 1、栈 ##

### 栈的概念 ###

栈是一种特殊的线性表，具有和线性表的特点，同时也有特殊性：元素遵循“先进后出”的特点，也就是只能从栈顶插入或删除元素。同样可以用顺序存储和链式存储两种方式实现，分别称为顺序栈和链栈。栈结构可以用来实现表达式求值、括号匹配等。

栈的特点可以看成是一个桶，往桶里面装东西，取东西都是从上面进行的，最先放进去的要最后才能取出来：

![20170411195240432][]

###  栈的基本操作定义： ###

> >  *  InitStack(&S):初始化一个空栈
> >  *  StackEmpty(S):判断栈是否为空，为空返回1否则返回0
> >  *  GetTop(S,&e):返回栈顶元素放到e中
> >  *  PushStack(&S,e):从栈顶插入元素e
> >  *  PopStack(&S,&e):从栈顶弹出元素放入e
> >  *  StackLength(S):返回栈内元素个数
> >  *  ClearStack(&S):清空栈内元素

###  栈的实现： ###

> > [顺序存储][Link 1]和[链式存储][Link 2]

## 2、队列 ##

###  队列的概念 ###

队列也是一种特殊的线性表，它的特殊性在于“先进先出”，如同现实生活中的排队问题：先来的人先服务完先走。不同于栈的地方在于队列一端用来插入新元素，一端用来删除元素，即有队首和队尾：

![20170411200841481][]

###  队列的基本操作： ###

> >  *  InitQueue(&Q):初始化一个空队列
> >  *  QueueEmpty(Q):判断队列是否为空
> >  *  EnterQueue(&Q,x):插入元素到队尾
> >  *  DeleteQueue(&Q,&x):删除队首一个元素并放入x中
> >  *  GetHead(Q,&e):返回队首元素到e
> >  *  ClearQueue(&Q):清空队列

###  队列的实现： ###

> > [顺序循环队列][Link 3]和[链式队列][Link 4]

[20170411195240432]: /images/20220617/84b69f5f640d4a70931cf8eb2803ac2a.png
[Link 1]: http://blog.csdn.net/qq_29721419/article/details/70131787
[Link 2]: http://blog.csdn.net/qq_29721419/article/details/70141726
[20170411200841481]: /images/20220617/b04cab487a2341678c4f9093431da58f.png
[Link 3]: http://blog.csdn.net/qq_29721419/article/details/70147044
[Link 4]: http://blog.csdn.net/qq_29721419/article/details/70146456