数据结构与算法~栈与队列

博主： Xherlock
发布时间：2021 年 10 月 12 日
518 次浏览
暂无评论
4968字数
分类：数据结构与算法

# 栈

|          | <span style="display:inline-block;width:100px">栈</span>     | <span style="display:inline-block;width:100px">队列</span>           |
| ---------- | :------------------------------------------------------------- | ---------------------------------------------------------------------- |
| 定义     | 只能在表的一端（栈顶）进行插入和删除运算的线性表             | 只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表 |
| 逻辑结构 | 与线性表相同，仍为一对一关系                                 | 与线性表相同，仍为一对一关系                                         |
| 存储结构 | 用顺序栈或链栈存储均可，顺序栈更常见                         | 用顺序队列或链队存储均可                                             |
| 运算规则 | 只能在栈顶运算，且访问结点时依照**后进先出**/先进后出的原则  | **先进先出**                                                         |
| 实现方式 | 关键是编写入栈和出栈函数，具体实现一顺序栈或链栈的不同而不同 | 关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同         |
| 基本操作 | 入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空               |                                                                      |

**与一般线性表的区别**

栈、队列是一种特殊（操作受限）的线性表，区别仅在于运算规则不同（线性表是**随机**、**顺序存取**）

## 顺序栈

### 定义

~~~C
#define MAXSIZE 100
typedef struct
{
    SElemType *base;	// 栈底指针
    SElemType *top;		// 栈顶指针
    int stacksize;		// 栈可用的最大容量
}SqStack;
~~~

解释：

base指针初始化完成后始终指向栈底的位置，为NULL则表明栈结构不存在

top指针初值指向栈底，每插入新的栈顶元素是，指针top增1，删除时减1；栈非空时，top指针始终指向栈顶元素的上一个位置

### 初始化

1. 为顺序栈动态分配一个最大容量为MAXZISE的数组空间，使base指向这段空间的基地址，即栈底
2. 栈顶指针top初始化为base，表示栈为空
3. stacksize置为栈的最大容量MAXSIZE

~~~C
Status InitStack(SqStack &S)
{
    S.base = new SElemType[MAXSIZE];
    if(!S.base)				// 为顺序栈动态分配一个最大容量为MAXZISE的数组空间
        return OVERFLOW;	// 存储分配失败
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}
~~~

### 判断是否为空

~~~C
int StackEmpty(SqStack &S)
{
    if(S.top==S.base)
        return 1;	// 为空时返回1
    else
        return 0;	// 不空时返回0
}
~~~

### 求栈长

~~~C
int StackLength(SqStack &S)
{
    return S.top-S.base;
}
~~~

### 清空

~~~C
Status ClearStack(SqStack &S)
{
    if(S.base)
        S.top=S.base;
    return OK;
}
~~~

### 销毁

~~~C
Status DestoryStack(SqStack &S)
{
    if(S.base)
    {
        free(S.base);
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
    return OK;
}
~~~

### 入栈

1. 判断栈是否满，若满返回ERROR
2. 将新元素压入栈顶，栈顶指针加1

~~~C
Status Push(SqStack &S, SElemType e)
{
    if(S.top-S.base==S.stacksize)
        return ERROR;
    *s.top++=e;		// 这里是先赋值再指向下一位
    return OK;
}
~~~

### 出栈

1. 判断栈是否空，若空返回ERROR
2. 栈顶指针减1，栈顶元素出栈

~~~C
Status Pop(SqStack &S, SElemType &e)
{
    if(S.top==S.base)
        return ERROR;
    e = *--S.top;		// 这里是先指向上一位再赋值
    return Ok;
}
~~~

### 取栈顶元素

~~~C
Status GetTop(Sqstack S, SElemType &e)
{
    if(S.top==S.base)
        return Error;
    e = *(S.top-1);		// 这里不能使用S.top--,否则会使top指针指向的位置发生改变
    return OK;
}
~~~

## 链栈

运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点

### 定义

~~~C
typedf struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;
~~~

### 初始化

~~~C
void InitStack(LinkStack &S)
{
    S = NULL;
}
~~~

### 判断是否为空

~~~C
Status StackEmpty(LinkStack S)
{
    if(S == NULL)
        return TRUE;
    else
        return FALSE;
}
~~~

### 进栈

~~~C
Status Push(LinkStack &S, SElemType e)
{
    p = new StackNode;
    if(!p)
        exit(OVERFLOW);
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}
~~~

### 出栈

~~~C
Status Pop(LinkStack &S, SElemType &e)
{
    if(S == NULL)
        return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    delete p;
    return OK;
}
~~~

### 取栈顶元素

~~~C
SElemType GetTop(LinkStack S)
{
    if(S == NULL)
        exit(1);
    else
        return S->data;
}
~~~

## 栈与递归

常用到递归

* 递归定义的数学函数：阶乘函数、2阶Fibonaci数列
* 具有递归特性的数据结构：树、广义表
* 可递归求解的问题：迷宫问题、Hanoi塔问题

# 队列

## 循环队列

### 定义

~~~c
#define MAXQSIZE 100
typedef struct
{
    QElemType *base;	// 存储空间的基地址
    int front;	// 头指针
    int rear;	// 尾指针
}SqQueue;
~~~

### 分析

队空：front==rear

入队：base[rear++]=x

出队：x=base[front++]

但是会存在**假溢出**的情况：头指针前为空，而尾指针已到达最大空间的地址

解决方案就是将队列改为循环队列，即base[0]接在base[MAXQSIZE-1]之后，若rear+1=MAXQSIZE则令rear=0

此时

队空：front==rear

入队：base[rear]=x;	rear=(rear+1)%MAXQSIZE;

出队：x=base[front];	front=(front+1)%MAXQSIZE;

队满：(rear+1)%MAXQSIZE=front;

### 初始化

~~~C
Status InitQueue(SqQueue &Q)
{
    Q.base = new QElemType[MAXQSIZE];
    if(!Q.base)
        exit(overflow);
    Q.front = Q.rear = 0;
    return OK;
}
~~~

### 求队列长度

~~~C
int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
~~~

### 入队

~~~C
Status EnQueue(SqQueue &Q, QElmeType e)
{
    if((Q.rear + 1) % MAXQSIZE == Q.front)
        return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}
~~~

### 出队

~~~C
Status DeQueue(SqQueue &Q, QElemType &e)
{
    if(Q.front == Q.rear)
        return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}
~~~

## 链队列

略

最后修改：2021 年 10 月 25 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

操作系统实验Lab04
浏览次数: 762
数据结构与算法思维导图
浏览次数: 574
并发控制和备份恢复
浏览次数: 448
中断与异常
浏览次数: 854
机器学习3
浏览次数: 381

数据结构与算法~栈与队列

Xherlock • 2021 年 10 月 12 日

# 栈

**与一般线性表的区别**

栈、队列是一种特殊（操作受限）的线性表，区别仅在于运算规则不同（线性表是**随机**、**顺序存取**）

## 顺序栈

### 定义

~~~C
#define MAXSIZE 100
typedef struct
{
    SElemType *base;	// 栈底指针
    SElemType *top;		// 栈顶指针
    int stacksize;		// 栈可用的最大容量
}SqStack;
~~~

解释：

base指针初始化完成后始终指向栈底的位置，为NULL则表明栈结构不存在

top指针初值指向栈底，每插入新的栈顶元素是，指针top增1，删除时减1；栈非空时，top指针始终指向栈顶元素的上一个位置

### 初始化

### 判断是否为空

~~~C
int StackEmpty(SqStack &S)
{
    if(S.top==S.base)
        return 1;	// 为空时返回1
    else
        return 0;	// 不空时返回0
}
~~~

### 求栈长

~~~C
int StackLength(SqStack &S)
{
    return S.top-S.base;
}
~~~

### 清空

~~~C
Status ClearStack(SqStack &S)
{
    if(S.base)
        S.top=S.base;
    return OK;
}
~~~

### 销毁

~~~C
Status DestoryStack(SqStack &S)
{
    if(S.base)
    {
        free(S.base);
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
    return OK;
}
~~~

### 入栈

1. 判断栈是否满，若满返回ERROR
2. 将新元素压入栈顶，栈顶指针加1

~~~C
Status Push(SqStack &S, SElemType e)
{
    if(S.top-S.base==S.stacksize)
        return ERROR;
    *s.top++=e;		// 这里是先赋值再指向下一位
    return OK;
}
~~~

### 出栈

1. 判断栈是否空，若空返回ERROR
2. 栈顶指针减1，栈顶元素出栈

~~~C
Status Pop(SqStack &S, SElemType &e)
{
    if(S.top==S.base)
        return ERROR;
    e = *--S.top;		// 这里是先指向上一位再赋值
    return Ok;
}
~~~

### 取栈顶元素

## 链栈

运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点

### 定义

~~~C
typedf struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;
~~~

### 初始化

~~~C
void InitStack(LinkStack &S)
{
    S = NULL;
}
~~~

### 判断是否为空

~~~C
Status StackEmpty(LinkStack S)
{
    if(S == NULL)
        return TRUE;
    else
        return FALSE;
}
~~~

### 进栈

~~~C
Status Push(LinkStack &S, SElemType e)
{
    p = new StackNode;
    if(!p)
        exit(OVERFLOW);
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}
~~~

### 出栈

~~~C
Status Pop(LinkStack &S, SElemType &e)
{
    if(S == NULL)
        return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    delete p;
    return OK;
}
~~~

### 取栈顶元素

~~~C
SElemType GetTop(LinkStack S)
{
    if(S == NULL)
        exit(1);
    else
        return S->data;
}
~~~

## 栈与递归

常用到递归

* 递归定义的数学函数：阶乘函数、2阶Fibonaci数列
* 具有递归特性的数据结构：树、广义表
* 可递归求解的问题：迷宫问题、Hanoi塔问题

# 队列

## 循环队列

### 定义

~~~c
#define MAXQSIZE 100
typedef struct
{
    QElemType *base;	// 存储空间的基地址
    int front;	// 头指针
    int rear;	// 尾指针
}SqQueue;
~~~

### 分析

队空：front==rear

入队：base[rear++]=x

出队：x=base[front++]

但是会存在**假溢出**的情况：头指针前为空，而尾指针已到达最大空间的地址

解决方案就是将队列改为循环队列，即base[0]接在base[MAXQSIZE-1]之后，若rear+1=MAXQSIZE则令rear=0

此时

队空：front==rear

入队：base[rear]=x;	rear=(rear+1)%MAXQSIZE;

出队：x=base[front];	front=(front+1)%MAXQSIZE;

队满：(rear+1)%MAXQSIZE=front;

### 初始化

~~~C
Status InitQueue(SqQueue &Q)
{
    Q.base = new QElemType[MAXQSIZE];
    if(!Q.base)
        exit(overflow);
    Q.front = Q.rear = 0;
    return OK;
}
~~~

### 求队列长度

~~~C
int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
~~~

### 入队

~~~C
Status EnQueue(SqQueue &Q, QElmeType e)
{
    if((Q.rear + 1) % MAXQSIZE == Q.front)
        return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}
~~~

### 出队

~~~C
Status DeQueue(SqQueue &Q, QElemType &e)
{
    if(Q.front == Q.rear)
        return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}
~~~

## 链队列

略

发表评论 取消回复

数据结构与算法~栈与队列

发表评论取消回复