栈(Stack)和队列(queue)及其应用(C++)

矫情吗；* 2022-05-18 08:49 196阅读 0赞

栈

栈操作实例：

![70][]

栈可试作序列的特例，将栈作为向量的派生类

#include "../Vector/Vector.h"   //以向量为基类，派生出栈模板类
    template <typename T> class Stack: public Vector<T> {   //将向量的首/末端作为栈底/顶
    public:                         //size(), empty()以及其它开放接口，均可直接沿用
        void push( T const& e ) { insert( size(), e ); }    //入栈
        T pop() { return remove( size()-1 ); }              //出栈
        T& top() { return (*this)[size()-1]; }              //取顶
    };

栈的应用

试探回溯法

1.八皇后问题

皇后类

struct Queen {  //皇后类
        int x, y;   //坐标
        Queen (int xx = 0, int yy = 0 ) : x(xx), y(yy) {};
        bool operator==( Queen const& q ) const {   //重载判等操作符，检验不同皇后之间可能存在的冲突
            return (x==q.x)         //行冲突
                || (y==q.y)         //列冲突
                || (x+y == q.x+q.y) //对角线冲突
                || (x-y == q.x-q.y);
        }
        bool operator!=( Queen const& q) const { return !(*this == q); }    //重载不等操作符
    };

将存在冲突的皇后判作相等

每行仅能放置一个皇后，先见各皇后分配至每一行。逐个尝试着她们放置到无冲突的某列，若当前皇后在任何列都冲突，则回溯到上一个皇后。

N皇后算法:

void placeQueen ( int N ) {             //N皇后算法:采用试探/回溯的策略,借助栈记录查找结果
        Stack<Queen> solu;          //存放解的栈
        Queen q(0,0);               //原点位置开始
        do {                        //反复试探，回溯
            if ( N <= solu.size() || N <= q.y ) {   //若已出界，则回溯一行，并继续试探下一列
                q = solu.pop(); q.y++; 
            } else {    //试探下一行
                while( ( q.y < N ) && (0 <= solu.find(q) ) )       //通过与已有皇后对比,尝试找到可摆放下一皇后的列
                    { q.y++; nCheck++; }
                if ( q.y < N ) {    //存在可摆放的列
                    solu.push(q);   //摆上当前皇后
                    if ( N <= solu.size() ) nSolu++;     //若部分解已称为全局解，则通过全局变量nSolu计数
                    q.x++; q.y==0;                      //转入下一行，从第0列开始，试探下一皇后
                }
            }
        } while( ( 0 < q.x ) || ( q.y < N) );           //所有分支均已或穷举或剪枝之后，算法结束
    }

2.迷宫寻径问题

迷宫格点类:

typedef enum { AVAILABLE, ROUTE, BACKTRACKED, WALL } Status;        //迷宫单元状态
    //           原始可用的， 当前路径上的， 所有方向尝试失败后回溯的， 不可使用的
    
    typedef enum { UNKNOWN, EAST, SOUTH, WEST, NORTH, NO_WAY } ESWN;    //单元的相对邻接方向
    
    inline ESWN nextESWN (ESWN eswn) { return ESWN( eswn + 1); }        //依次转至下一邻接方向
    
    struct Cell {   //迷宫格点
        int x, y; Status status;
        ESWN incoming, outgoing;    //进入，走出方向
    };
    
    #define LABY_MAX 24             //最大迷宫尺寸
    Cell laby[LABY_MAX][LABY_MAX];  //迷宫

邻格查询:

inline Cell* neighbor (Cell* cell)  {   //查询当前位置的相对格点
        switch ( cell->outgoing ) {
            case EAST : return cell + LABY_MAX ;    //向东
            case SOUTH: return cell + 1        ;    //向南
            case WEST : return cell - LABY_MAX ;    //向西
            case NORTH: return cell - 1        ;    //向北
            default   : exit(-1);  
        }
    }

邻格转入:

inline Cell* advance (Cell* cell)  {       //从当前位置转入相邻格点
        Cell* next;
        switch ( cell->outgoing )   {
            case EAST : next = cell + LABY_MAX; next->incoming = WEST;  break;  //向东
            case SOUTH: next = cell +1;         next->incoming = NORTH; break;  //向南
            case WEST : next = cell - LABY_MAX; next->incoming = EAST;  break;  //向西
            case NORTH: next = cell -1;         next->incoming = SOUTH; break;  //向北
            default : exit(-1);
        }
        return next;
     }

迷宫寻径算法实现

//在格单元ｓ至ｔ之间规划一条道路
    bool labyrinth ( Cell Laby[LABY_MAX][LABY_MAX], Cell* s, Cell* t) {
        if ( (AVAILABLE != s->status ) || (AVAILABLE != t->status ) ) return false;     //退化情况
        
        Stack<Cell*> path;     //用栈记录通路
        s->incoming = UNKNOWN;  s->status = ROUTE;  path.push(s);   //起点
        do {    //从起点出发不断试探回溯，直到抵达终点，或者穷尽可能    
            Cell* c = path.top();   
            if ( c == t) return true;       
            while (NO_WAY > (c->outgoing = nextESWN(c->outgoing) ) )        //逐一检查所有方向
                if (AVAILABLE == neighbor(c)->status) break;              //找到尚未试探的方向
            if (NO_WAY <= c->outgoing )     //若所有方向都已尝试
            { c->status = BACKTRACKED; c = path.pop(); }    //向后回溯一步
            else //否则，向前试探一步
                { path.push(c = advance(c) );   c->outgoing = UNKNOWN;  c->status = ROUTE; }
        }while( !path.empty() );
        return false;
    }

\------------------------------------------------------------------------------------------------------------------------------------------------------

队列

队列操作实例：

![70 1][]

队列按线性的逻辑次序排列，约定新对象只能从一端插入其中，这一端称作队尾；只能总另一端取出已有的元素，这一端称作队头；

元素的插入和删除是修改队列结构的主要两种方式，分别称作入队（enqueue）和出队（dequeue）

队列可视作是序列的特例，故只要将队列作为列表的派生类。

Queue模板类

#include "../List/List.h"   //以List为基类
    template <typename T> class Queue: public List<T> { //队列模板类
    public:
        void enqueue (T const& e) { insertAsLast(e); }  //入队：尾部插入
        T dequeue() { return remove( first() ); }       //出队：首部删除
        T& front()  { return first()->data; }           //队首
    };

队列应用

1.循环分配器

RoundRobin {    //循环分配器
        Queue Q(clients);       //参与资源分配的所有客户组成队列Ｑ
        while (!ServiceClosed()) {  //在服务关闭之前，反复地
            e = Q.dequeue();    //队首的客户出队
            serve(e);           //并接受服务
            Q.enqueue(e);       //重新入队
        }
    }

[70]: /images/20220518/5c5ff85de389439d91eb39e618c14331.png
[70 1]: /images/20220518/0254ffd9ac0945129623f7c93f4648dd.png