数据结构 -栈和队列

3.1 栈和队列的定义和特点

-栈和队列是两种常用的、重要的数据结构。
-栈和队列是限定插入和删除只能在表的端点“”进行的线性表。


队列 的特点（先进先出）

insert(Q,n+1，x)  //插入只能在队尾
Delete(Q,1)       //删除在第一个位置
1
2

3.1.1 栈的定义和特点

1. 限定在表尾，进行插入删除的线性表。
2. 后进先出（list in First Out）的线性表。简称LIFO。
   
   

3.1.2 队列的定义和特点

3. 队列 （先进先出 First IN First OUT）FIFO（排队事件）
   
   

3.2 案例引入

3.2.1 进制转换

1. 例 将 十进制数159 转换为 八进制数

159/8=19~7
19/8=2~3
2/8=0~2
237 就是 159 转换八进制的数

3.2.2 表达式的求值

• 操作数：常数、变量
• 运算符：算术运算符、关系运算符和逻辑符
• 界限符：左右括弧和表达式结束符

3.3栈的表示和操作的实现

3.3.1 栈的抽象数据类型的类型定义

ADT Stack{
数据对象:
D = {ai|ai ∈ ElemSet, i=1,2,...,n,n≥0  }
数据关系:
R1={<ai-1,ai>|ai-1，ai∈D，i=2,...,n}
约定an端为栈顶，a1端为栈底。
基本操作:初始化、进栈、出栈、取栈顶元素等
}ADT Stack
1
2
3
4
5
6
7
8

3.3.2 栈的表示和实现

• 栈本身就是线性表，于是栈也有顺序存储
  和链式存储两种实现方式。

栈的顺序存储 —顺序栈
栈的链式存储 —链栈

栈满报错的处理方法：
1.报错，返回操作系统
2.分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈。

使用数据作为顺序栈存储方式的特点：
 简单、方便、但易溢出（数组大小固定）
 上溢：栈已经满，又要压入元素
 下溢：栈已经空，还要弹出元素

>  注:上溢是一种错误，使问题的处理无法进行;而下溢一般认为是一种结束条件，即问题处理结束。

1
2
3
4
5
6
7

#define MAXSIZE 100
typedef struct{
    SElemType *base;  //栈底指针
    SElemType *top;   //栈顶指针
    int stacksize;    //栈可用最大容量
}SqStack;
1
2
3
4
5
6

- 顺序栈的初始化

Status InitStack(SqStack &S){ //构造一个空栈
S.base = new SEleType[MAXSIZE]//s.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
 (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);//存储分配失败
S.top = S.base; //栈顶指针等于栈底指针
S.stacksize = MAXSIZE;
return OK;
1
2
3
4
5
6
7

==【算法补充】==顺序栈判断栈是否为空

 /*栈为空，返回TRUE；否则返回FAlSE*/
Status StackEmpty(SqStack S)
{
if(S.top == S.base) 
{
return true
}          
else
{
}
return false;             
}
1
2
3
4
5
6
7
8
9
10
11
12

【算法补充】 求顺序栈长度

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

1
2
3
4
5

【算法补充】 清空顺序栈

Status ClearStack(Sqstack &S)
{
    if(S.base)           //如果栈不为空，则证明有 栈
    {
    S.top = S.base       //将栈顶移到栈底
    }
}
1
2
3
4
5
6
7

【算法补充】 销毁顺序栈

Status DestroyStack(Sqstack &S)
{
    if(S.base)           //如果栈不为空，则证明有栈
    {
    delete S.base;       //删除栈底
    S.stacksize = 0;             //将栈的空间设置为0
    S.top = S.base = NULL;       //将栈顶移到栈底
    }
    return ok;
}
1
2
3
4
5
6
7
8
9
10

【顺序栈的入栈 】

入栈将数据存入栈底

（1）判断是否栈满，若满则出错（上溢）
（2）元素e压入栈底
（3）栈顶指针加1

Status Push(SqStack &S,SElemType e)
{
    if(S.top - S.base == S.stacksize)  // 用栈顶 - 栈底 是否为 栈空间大小，确定是否栈满
    { 
        return ERROR;
    }
    *S.top++ = e;                       //*S.top = e;  将e值赋值给指针所指的空间，然后 指针 加加 指向下一个空间 S.top++;
    return OK;
}
// & 取地址操作符
// * 取数据操作符
1
2
3
4
5
6
7
8
9
10
11

【顺序栈的出栈 】

（1）判断是否栈空，若空则出错（下溢）
（2）获取栈顶元素e
（3）栈顶指针减一1

Status Pop(SqStack &S,SElemType e)
{ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回OK；
    if(S.top - S.base == 0)    // 等价于if(StackEmpty(S))   if(S.top == S.base)   判断栈是否空
    {
        return ERROR;
    }
    e = *--S.top ;        //指针－－ ，取出指针当前地址空间的内容。  等价于  --S.top ; e = *S.top ，
}
1
2
3
4
5
6
7
8

3.3.3 链栈的表示和实现

typedef struct StackNode  
{
    SElemType data;         //数据域 存放栈中数据元素 类型为栈中类型
    struct StackNode *next  //指针域  
} StackNode,*LinkStack;     //StackNode 栈的结点类型   *LinkStack 栈的指针类型
LinkStack S;              //指向结点的指针型            
1
2
3
4
5
6

链表的头指针就是栈顶
不需要头结点
基本不存在栈满
空栈相当于头指针指向空
插入和删除仅在栈处 操作

算法

• 链栈的初始化

/*构造一个空栈，栈顶指针置空
void InitStack(LinkStack &S) //构建一个空栈，栈顶指针指针置为空
{                            
S=NULL;
return OK;
}
1
2
3
4
5
6

• 判断链栈是否为空

Status StackEmpty(LinkStack S)
{
    if(S==NULL)                           //判断头指针 S 是否为空
    {
        return TRUE;
    }    
    else
    {
        return FALSE;
    }
}
1
2
3
4
5
6
7
8
9
10
11

• 链栈的入栈

Status Push(LInKStack &S,SElemType e)
{
    p = new StackNode;                 //生成一个新结点
    p -> data = e;                     //将新结点数据域置为e
    p -> next = S;                    //将新结点的指针域置为S
    S = p；;                          //将头结点从S换成P
    return OK;
}
1
2
3
4
5
6
7
8

• 链栈的出栈
  

Stack Pop(LinkStack &S,SElemType &e)
{
    if(S == NULL)
    {
        return False;
    }
    e = S -> data;                    //将data域中数值保存为e
    p = S；;                          //
    S = S->next;                      //将S的Next的值赋给S
    free(p);                          //delete p; 释放删除结点的空间
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 取得链栈的元素

Stack Pop(LinkStack &S,SElemType &e)
{
if(S != NULL)
{
return S -> data;
}
}