06.栈的概念及实现、队列的概念及实现、两个有趣的问题

约 2493 字大约 8 分钟

栈数据结构队列算法

2022-06-25

三十四、栈的概念及实现（上）

1、栈的定义

栈是一种特殊的线性表
栈仅能在线性表的一端进行操作
栈顶(Top)：允许操作的一端
栈底(Bottom)：不允许操作的一端

2、栈的特性

后进先出( Last In First Out )

3、栈的操作

创建栈 Stack()
销毁栈 ~Stack()
清空栈 clear()
进栈 push()
出栈 pop()
获取栈顶元素 top()
获取栈的大小 size()

4、栈的实现

5、栈的顺序实现

6、StaticStack 设计要点

类模板
使用原生数组作为栈的存储空间
使用模板参数决定栈的最大容量

7、编程实验：基于顺序存储结构的栈

StaticStack.h

#ifndef STATICSTACK_H
#define STATICSTACK_H
 
#include "Stack.h"
#include "Exception.h"
 
namespace DTLib
{
 
template < typename T, int N >
class StaticStack : public Stack<T>
{
protected:
    T m_space[N];       
    int m_top;
    int m_size;
public:
    StaticStack()    // O(1)
    {
        m_top = -1;
        m_size = 0;
    }
 
    int capacity() const  // O(1)
    {
        return N;
    }
 
    void push(const T& e)  // O(1)
    {
        if( m_size < N )
        {
            m_space[m_top + 1] = e;     // 为了异常安全，先复制后改动标识，因为是类型T可能存在异常
            m_top++;
            m_size++;
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No space in current stack ...");
        }
    }
 
    void pop()   // O(1)
    {
        if( m_size > 0 )
        {
            m_top--;
            m_size--;
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");
        }
    }
 
    T top() const   // O(1)
    {
        if( m_size > 0 )
        {
            return m_space[m_top];
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");
        }
    }
 
    void clear()   // O(1)
    {
        m_top = -1;
        m_size = 0;
    }
 
    int size() const  // O(1)
    {
        return m_size;
    }
};
 
}
 
#endif // STATICSTACK_H

8、小结

栈是一种特殊的线性表
栈只允许在线性表的一端进行操作
StaticStack使用原生数组作为内部存储空间
StaticStack的最大容量由模板参数决定

三十五、栈的概念及实现（下）

当存储的元素为类类型时，StaticStack的对象在创建时，会多次调用元素类型的构造函数，影响效率。
是的，所以我们需要实现链式栈。

创建栈对象时，调用泛指类型的构造函数。

1、链式栈的存储实现

2、链式栈的设计要点

类模板，抽象父类Stack的直接子类
在内部组合使用LinkList类，实现栈的链式存储
只在单链表成员对象的头部进行操作

3、编程实验：基于链式存储结构的栈

LinkStack.h

#ifndef LINKSTACK_H
#define LINKSTACK_H
 
#include "Stack.h"
#include "LinkList.h"
 
namespace DTLib
{
 
template < typename T >
class LinkStack : public Stack<T>
{
protected:
    LinkList<T> m_list; // 组合使用单链表类
public:
    void push(const T& e)  // O(1)
    {
        m_list.insert(0, e);
    }
 
    void pop()   // O(1)
    {
        if( m_list.length() > 0 )
        {
            m_list.remove(0);
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");
        }
    }
 
    T top() const  // O(1)
    {
        if( m_list.length() > 0 )
        {
            return m_list.get(0);
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");
        }
    }
 
    void clear()  // O(n)
    {
        m_list.clear();
    }
 
    int size() const  // O(1)
    {
        return m_list.length();
    }
};
 
}
 
#endif // LINKSTACK_H

4、栈的应用实践

符号匹配问题
在C语言中有一些成对匹配出现的符号
括号：(), [], { }, <>
引号：' ' , " "

5、问题：如何实现编译器中的符号成对检测？

6、算法思路

从第一个字符开始扫描
当遇见普通字符时忽略
当遇见左符号时压入栈中
当遇见右符号时弹出栈顶符号，并进行匹配
结束
成功：所有字符扫描完毕，且栈为空
失败：匹配失败或所有字符扫描完毕但栈非空

7、编程实验：符号匹配问题

main.cpp

8、小结

链式栈的实现组合使用了单链表对象
在单链表的头部进行操作能够实现高效的入栈和出栈操作
栈 “后进先出” 的特性适用于检测成对出现的符号
栈非常适合于需要 “就近匹配” 的场合

9、开放性问题

使用单链表对象实现链式栈时，为什么选择在单链表的头部进行操作？如果选择在尾部进行操作是否也能实现栈的功能？

三十六、队列的概念及实现（上）

1、队列的本质

队列是一种特殊的线性表
队列仅能在线性表的两端进行操作
队头( Front )：取出数据元素的一端
队尾( Rear )：插入数据元素的一端

2、队列的特性

先进先出( First In First Out )

3、队列的操作

创建队列 Queue()
销毁队列 ~Queue()
清空队列 clear()
进队列 add( )
出队列 remove()
获取队头元素 front()
获取队列的长度 length()

4、队列的实现

5、队列的顺序实现

6、StaticQueue设计要点

类模板
使用原生数组作为队列的存储空间
使用模板参数决定队列的最大容量

7、StaticQueue 实现要点（循环计数法）

关键操作

队列的状态

8、编程实验：基于顺序存储结构的队列

StaticQueue.h

#ifndef STATICQUEUE_H
#define STATICQUEUE_H
 
#include "Queue.h"
#include "Exception.h"
 
namespace DTLib
{
 
template < typename T, int N >
class StaticQueue : public Queue<T>
{
protected:
    T m_space[N];
    int m_front;
    int m_rear;
    int m_length;
public:
    StaticQueue()
    {
        m_front = 0;
        m_rear = 0;
        m_length = 0;
    }
 
    int capacity() const   // O(1)
    {
        return N;
    }
 
    void add(const T& e)    // O(1)
    {
        if( m_length < N )
        {
            m_space[m_rear] = e;// 为了异常安全，先复制后改动标识，因为是类型T可能存在异常
            m_rear = (m_rear + 1) % N;
            m_length++;
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No space in current queue ...");
        }
    }
 
    void remove()    // O(1)
    {
        if( m_length > 0 )
        {
            m_front = (m_front + 1) % N;
            m_length--;
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element in current queue ...");
        }
    }
 
    T front() const   //  O(1)
    {
        if( m_length > 0 )
        {
            return m_space[m_front];
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element in current queue ...");
        }
    }
 
    void clear()   // O(1)
    {
        m_front = 0;
        m_rear = 0;
        m_length = 0;
    }
 
    int length() const   // O(1)
    {
        return m_length;
    }
};
 
}
 
#endif // STATICQUEUE_H

9、小结

队列是一种特殊的线性表，具有先进先出的特性
队列只允许在线性表的两端进行操作，一端进，一端出
StaticQueue使用原生数组作为内部存储空间
StaticQueue的最大容量由模板参数决定
StaticQueue采用循环计数法提高队列操作的效率

三十七、队列的概念及实现（下）

当数据元素为类类型，StaticQueue 的对象在创建时，会多次调用元素类型的构造函数，影响效率。
是的，所以我们需要实现链式队列。

1、队列的链式存储实现

2、链式队列的设计要点

类模板，抽象父类Queue的直接子类
在内部使用链式结构实现元素的存储
只在链表的头部和尾部进行操作

3、链式队列的设计要点

4、编程实验：基于LinkList的队列

LinkQueue.h

5、问题

使用LinkList类实现链式队列是否合适，是否有更好的方案？

时间复杂度较高

6、队列链式存储实现的优化

7、链式队列的设计优化

8、编程实验：基于Linux内核链表的队列

LinkQueue.h

#ifndef LINKQUEUE_H
#define LINKQUEUE_H
 
#include "Queue.h"
#include "LinuxList.h"
#include "Exception.h"
 
namespace DTLib
{
 
template < typename T >
class LinkQueue : public Queue<T>
{
protected:
    struct Node : public Object                                     // 结点类型
    {
        list_head head;                                             // Linux内核链表结点的结构体成员
        T value;                                                    // 数据域
    };
 
    list_head m_header;// 头结点
    int m_length;//当前队列长度
public:
    LinkQueue()   // O(1)
    {
        m_length = 0;
 
        INIT_LIST_HEAD(&m_header); // Linux链表头结点初始化
    }
 
    void add(const T& e)     // O(1)
    {
        Node* node = new Node();
 
        if( node != NULL )
        {
            node->value = e;
 
            list_add_tail(&node->head, &m_header);   // O(1)插入到链表的尾部
 
            m_length++;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No memory to add new element ...");
        }
    }
 
    void remove()      // O(1)
    {
        if( m_length > 0 )
        {
            list_head* toDel = m_header.next;
 
            list_del(toDel);
 
            m_length--;
 
            delete list_entry(toDel, Node, head);
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element in current queue ...");
        }
    }
 
    T front() const    // O(1)
    {
        if( m_length > 0 )
        {
            return list_entry(m_header.next, Node, head)->value;
        }
        else
        {
            THROW_EXCEPTION(InvalidOperationException, "No element in current queue ...");
        }
    }
 
    void clear()    // O(n)
    {
        while( m_length > 0 )
        {
            remove();
        }
    }
 
    int length() const    // O(1)
    {
        return m_length;
    }
 
 
    ~LinkQueue()   // O(n)
    {
        clear();
    }
};
 
}
 
#endif // LINKQUEUE_H