栈与队列

发表于 更新于 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 7 分钟

栈

栈是限定仅在表尾进行插入和删除操作的线性表。

栈的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
ADT Stack {
Data
    元素具有相同的类型，相邻元素具有前驱后继关系。

Operation
    InitStack (&S)  (构造空栈 )
    操作结果：构造一个空栈S。
    DestroyStack(&S)   (销毁栈结构)
    初始条件：栈S已存在。
    操作结果：栈S被销毁。
    ClearStack (&S)  (栈清空)
    初始条件：栈S已存在。
    操作结果：栈S清为空栈。
    StackEmpty (S)   (判空)
    初始条件：栈S已存在。
    操作结果：若栈S为空栈，则返回true, 否则false。
    StackLength (S) (求栈长)
    初始条件：栈S已存在。
    操作结果：返回S的元素个数，即栈的长度。
    StackTraverse (S) (遍历栈)
    初始条件：栈S已存在且非空。
    操作结果：从栈底到栈顶依次对S的每个数据元素访问。
    GetTop (S, &e)   (求栈顶元素)
    初始条件：栈S已存在且非空。
    操作结果：用e返回S的栈顶元素。
    Push (&S, e) (入栈)
    初始条件：栈S已存在。
    操作结果：插入元素e为新的栈顶元素。
    Pop (&S, &e)  (出栈)
    初始条件：栈S已存在且非空。
    操作结果：删除S的栈顶元素，并用e返回其值。
}ADT Stack

栈的顺序存储结构

1
2
3
4
5
6
7
8
#define MAXSIZE 50      /*存储空间初始分配量*/

typedef int SElemType;  /*SElemType类型根据实际情况而定*/
typedef  struct
{
    SElemType* data;    /*存储空间基地址*/
    int top;            /*栈顶指针*/
} SqStack;

进栈操作

1
2
3
4
5
6
7
8
9
10
void Push(SqStack& S, SElemType e)
{
    if (S.top == MAXSIZE - 1)    /*栈满*/
        cout << "栈满" << endl;
    else
    {
        S.top++;            /*栈顶指针加一*/
        S.data[S.top] = e;  /*新元素赋值给栈顶空间*/
    }
}

出栈操作

1
2
3
4
5
6
7
8
9
10
void Pop(SqStack& S, SElemType& e)
{
    if (S.top == -1)           /*栈空*/
        cout << "栈空" << endl;
    else
    {
        e = S.data[S.top];  /*将要删除元素赋值给e*/
        S.top--;            /*栈顶指针减一*/
    }
}

两栈共享空间

略。。。

栈的链式存储结构

1
2
3
4
5
6
7
8
9
10
typedef struct StackNode
{
    SElemType data;
    struct StackNode* next;
}StackNode, * LinkStackPtr;
typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

进栈操作

1
2
3
4
5
6
7
8
void Push(LinkStack& S, SElemType e)
{
    LinkStackPtr s = new StackNode;
    s->data = e;        /*给新结点值e*/
    s->next = S.top;    /*当前栈顶赋给新结点后继*/
    S.top = s;          /*新结点s赋给栈顶指针*/
    S.count++;
}

出栈出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Pop(LinkStack& S, SElemType& e)
{
    LinkStackPtr p;
    if (IsEmpty(S))
        cout << "栈空" << endl;   /*栈空*/
    else
    {
        e = S.top->data;         /*将要删除元素赋值给e*/
        p = S.top;               /*将栈顶结点赋值给p*/
        S.top = S.top->next;     /*使栈顶指针下移一位*/
        delete p;                /*释放结点p*/
        S.count--;
    }
}

栈的作用

栈的引入简化了程序设计问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。

现在许多的高级语言，如java，C#等都有对栈结构的封装，可以不用关注它的实现细节，就可以直接使用Stack的push和pop方法，非常方便。

栈的应用-递归

我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。

斐波那契数列

F(n)=F(n-1)+F(n-2)，(F(1)=F(2)=1)

1
2
3
4
5
6
int Fbi(int i)
{
    if(i==1||i==2)
        return 1;
    return Fbi(i-1)+Fbi(i-2);
}

等...

栈的应用-四则运算表达式求值

可参考

队列

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
ADT Queue {
Data
    元素具有相同的类型，相邻元素具有前驱后继关系。

Operation
    InitQueue (&Q)  (构造空队列 )
    操作结果：构造一个空队列Q。
    DestroyQueue (&Q)   (销毁队列结构)
    初始条件：队列Q已存在。
    操作结果：队列Q被销毁。
    ClearQueue  (&Q)  (队列清空)
    初始条件：队列Q已存在。
    操作结果：队列Q清为空队列。
    QueueEmpty (Q)   (判空)
    初始条件：队列Q已存在。
    操作结果：若队列Q为空，则返回true, 否则false。
    QueueLength (Q) (求队列长)
    初始条件：队列Q已存在。
    操作结果：返回Q的元素个数，即队列的长度。
    QueueTraverse (Q) (遍历队列)
    初始条件：队列Q已存在且非空。
    操作结果：从队头到队尾，依次对Q的每个数据元素  访问。
    GetHead (Q, &e)   (求队头元素)
    初始条件：队列Q已存在且非空。
    操作结果：用e返回Q的队头元素。
    EnQueue (&Q, e) (入队)
    初始条件：队列Q已存在。
    操作结果：插入元素e为新的队列元素。
    DeQueue (&Q, &e)  (出队)
    初始条件：队列Q已存在且非空。
    操作结果：删除Q的队头元素，并用e返回其值。
}ADT Queue

循环队列

我们把队列的这种头尾相连的顺序存储结构称为循环队列。（可解决顺序存储空间不足）

定义

1
2
3
4
5
6
7
8
9
#define MAXSIZE 50
typedef int QElemType;
//循环队列
typedef struct
{
    QElemType* data;
    int front;      /*头指针*/
    int rear;       /*尾指针*/
}SqQueue;

初始化

1
2
3
4
5
void InitQueue(SqQueue& Q)
{
    Q.front = 0;
    Q.rear = 0;
}

队列长度

1
2
3
4
int GetLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

入队操作

1
2
3
4
5
6
7
8
9
10
void EnQueue(SqQueue& Q, QElemType e)
{
    if ((Q.rear + 1) % MAXSIZE == Q.front)  /*队满*/
        cout << "队列满" << endl;
    else
    {
        Q.data[Q.rear] = e;                 /*元素e赋值给队尾*/
        Q.rear = (Q.rear + 1) % MAXSIZE;    /*rear指针后移一位*/
    }
}

出队操作

1
2
3
4
5
6
7
8
9
10
void DeQueue(SqQueue& Q, QElemType& e)
{
    if (Q.front == Q.rear)                  /*队空*/
        cout << "队列空" << endl;
    else
    {
        e = Q.data[Q.front];                /*队头元素赋值给e*/
        Q.front = (Q.front + 1) % MAXSIZE;  /*front指针后移一位*/
    }
}

队列的链式存储结构

1
2
3
4
5
6
7
8
9
10
11
typedef int QElemType;

typedef struct QNode
{
    QElemType data;
    struct QNode* next;
}QNode, * QueuePtr;
typedef struct
{
    QueuePtr front, rear;
}LinkQueue;

入队操作

1
2
3
4
5
6
7
8
9
10
11
12
13
void EnQueue(LinkQueue& Q, QElemType e)
{
    QueuePtr s = new QNode;
    if (!s)                             /*存储分配失败*/
        cout << "存储分配失败" << endl;
    else
    {
        s->data = e;
        s->next = NULL;
        Q.rear->next = s;   /*新结点s赋值给队尾后继*/
        Q.rear = s;         /*s设为队尾结点*/
    }
}

出队操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void DeQueue(LinkQueue& Q, QElemType& e)
{
    QueuePtr p;
    if (Q.front == Q.rear)          /*队列空*/
        cout << "队列空" << endl;
    else
    {
        p = Q.front->next;          /*欲删除结点暂存给p*/
        e = p->data;                /*欲删除对头结点赋值给e*/
        Q.front->next = p->next;    /*原对头结点后继p->next赋值给头结点后继*/
        if (Q.rear == p)            /*若队头是队尾，则删除后将rear指向头结点*/
            Q.rear = Q.front;
        delete p;
    }
}

栈与队列对比

比较项目 栈 队列
逻辑结构 和线性表一样, 数据元素之间存在一对一的关系 和线性表一样, 数据元素之间存在一对一的关系
顺序存储 存储空间预先分配，可能会导致空间闲置或栈满溢出现象；数据元素个数不能自由扩充 （常设计成循环队列形式）；存储空间预先分配，可能会导致空间闲置或队满溢出现象；数据元素个数不能自由扩充
链式存储 动态分配，不会出现闲置或栈满溢出现象;数据元素个数可以自由扩充 动态分配，不会出现闲置或栈满溢出现象;数据元素个数可以自由扩充
运算规则 插人和删除在表的一端(栈顶)完成，后进先出 插入运算在表的一端(队尾)进行，删除运算在表的另一端(队头),先进先出