栈和队列

发表于 分类于

相对于一般序列结构，栈和队列的操作仅限于逻辑上特定的某端，二者元素接受操作的次序不同，简而言之，栈是先进后出，而队列为先进先出。在信息处理领域，栈和队列的身影随处可见，不少程序设计语言即建立在栈结构之上，我们日常生活中对自然资源和社会资源分配、调度银行和医院服务窗口可借助队列实现合理和优化的分配。

栈

栈是存放数据对象的一种特殊容器，其中的数据元素按线性的逻辑次序排列，但是插入操作仅限于栈的某一特定端，只能在栈顶插入和删除。栈中元素接受操作的次序必然遵循所谓的后进先出规律：从栈的整个生命周期来看，更晚出栈的元素应为更早入栈者。

栈和递归

调用栈的基本单位是帧，每次函数调用时都会相应地创建一帧，记录该函数在二进制程序中的返回地址，以及局部变量、传入参数等，并将该帧压入调用栈。在任一时刻，调用栈中的各帧依次对应于那些尚未返回的调用的实例，即当时的活跃函数实例

栈的应用

逆序输出

输出次序和处理过程颠倒，递归深度和输出长度不易预知

进制转换

给定任意10进制非负整数，将其转换为d进制表示形式

迭代模式

1
2
3
4
5
6
7
8
void convert ( Stack<char>& S, __int64 n, int base ) { //十进制数n到base进制的转换（迭代版）
   static char digit[] //0 < n, 1 < base <= 16，新进制下的数位符号，可视base取值范围适当扩充
   = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
   while ( n > 0 ) { //由低到高，逐一计算出新进制下的各数位
      int remainder = ( int ) ( n % base ); S.push ( digit[remainder] ); //余数（当前位）入栈
      n /= base; //n更新为其对base的除商
   }
} //新进制下由高到低的各数位，自顶而下保存于栈S中

递归模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void convert ( Stack<char>& S, __int64 n, int base ) { //十进制正整数n到base进制的转换（递归版）
   static char digit[] //0 < n, 1 < base <= 16，新进制下的数位符号，可视base取值范围适当扩充
   = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
   if ( 0 < n ) { //在尚有余数之前，反复地
      S.push ( digit[n % base] ); //逆向记录当前最低位，再
      convert ( S, n / base, base ); //通过递归得到所有更高位
   }
} //新进制下由高到低的各数位，自顶而下保存于栈S中
int main ( int argc, char* argv[] ) {
      Stack<char> S; //用栈记录转换得到的各数位
      convert ( S, n, base ); //进制转换
      while ( !S.empty() ) printf ( "%c", ( S.pop() ) ); //逆序输出栈内数位，即正确结果
   }
   return 0;
}

递归嵌套

具有自相似性的问题可递归描述，但分支位置和嵌套深度不固定

括号匹配

检查表达式括号是否匹配

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void trim ( const char exp[], int& lo, int& hi ) { //删除exp[lo, hi]不含括号的最长前缀、后缀
   while ( ( lo <= hi ) && ( exp[lo] != '(' ) && ( exp[lo] != ')' ) ) lo++; //查找第一个和
   while ( ( lo <= hi ) && ( exp[hi] != '(' ) && ( exp[hi] != ')' ) ) hi--; //最后一个括号
}

int divide ( const char exp[], int lo, int hi ) { //切分exp[lo, hi]，使exp匹配仅当子表达式匹配
   int mi = lo; int crc = 1; //crc为[lo, mi]范围内左、右括号数目之差
   while ( ( 0 < crc ) && ( ++mi < hi ) ) //逐个检查各字符，直到左、右括号数目相等，或者越界
      {  if ( exp[mi] == ')' )  crc--; if ( exp[mi] == '(' )  crc++;  } //左、右括号分别计数
   return mi; //若mi <= hi，则为合法切分点；否则，意味着局部不可能匹配
}

bool paren ( const char exp[], int lo, int hi ) { //检查表达式exp[lo, hi]是否括号匹配（递归版）
   trim ( exp, lo, hi ); if ( lo > hi ) return true; //清除不含括号的前缀、后缀
   if ( exp[lo] != '(' ) return false; //首字符非左括号，则必不匹配
   if ( exp[hi] != ')' ) return false; //末字符非右括号，则必不匹配
   int mi = divide ( exp, lo, hi ); //确定适当的切分点
   if ( mi > hi ) return false; //切分点不合法，意味着局部以至整体不匹配
   return paren ( exp, lo + 1, mi - 1 ) && paren ( exp, mi + 1, hi ); //分别检查左、右子表达式
}

迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
bool paren ( const char exp[], int lo, int hi ) { //表达式括号匹配检查，可兼顾三种括号
   Stack<char> S; //使用栈记录已发现但尚未匹配的左括号
   for ( int i = lo; i <= hi; i++ ) /* 逐一检查当前字符 */ /*DSA*/{
      switch ( exp[i] ) { //左括号直接进栈；右括号若与栈顶失配，则表达式必不匹配
         case '(': case '[': case '{': S.push ( exp[i] ); break;
         case ')': if ( ( S.empty() ) || ( '(' != S.pop() ) ) return false; break;
         case ']': if ( ( S.empty() ) || ( '[' != S.pop() ) ) return false; break;
         case '}': if ( ( S.empty() ) || ( '{' != S.pop() ) ) return false; break;
         default: break; //非括号字符一律忽略
   }
   return S.empty(); //整个表达式扫描过后，栈中若仍残留（左）括号，则不匹配；否则（栈空）匹配
}

栈混洗

考察栈$A=<a_1,a_2,…,a_n]$,$B$为空栈,A左端为栈顶

只允许将A的顶元素弹出并压入S,或将S的顶元素弹出并压入B

经过上述一系列操作后，A中元素全部转入B中，

$B=[a_{k1},a_{k2},…,a_{kn} >$，B右端为栈顶

同一输入序列，可有多种栈混洗

$[1,2,3,4>,[4,3,2,1>,[3,2,4,1>$

长度为$n$的栈混洗，可能的栈混洗个数
$$
SP(n)=\frac{(2n)!}{n!(n+1)!}
$$
设s在$k$次pop之后首次重新变空，则$k$无非$n$种情况

$SP(n)=\sum_{k=1}^{n}SP(k-1)SP(n-k)=catalan(n)$

设B为A的任意排列，则B为A的一个栈混洗，当且仅当对于任意的1<=i<j<k<=n,不存在{…,k,…,i,…,j…}

先证明仅当，首先，对于输入序列中的任意三个元素，其在输出序列中是否存在一个可行的相对排列次序与其它元素无关。不妨只关注这三个元素${i,j,k}$

无论如何,元素$i,j$必然先于$k$(弹出A并随即压入B中)压入中转栈S,若输出序列${k,i,j}$存在，则意味着这三个元素中，k必然首先从栈S中弹出，并且根据先进后出的规律，此时$i,j$存在于栈S中，且顺序只能为$j,i$，三者的次序必然是${k,j,i}$则$k$率先从栈S弹出，则三者压入输出栈B的次序必然是${k,j,i}$,而不是${k,i,j}$。

再证明当，对于任何不含禁形的输出序列，都可给出对应的栈混洗过程。

对任意1<=i<j<=n,B中都不含模式{…,j+1,…,i,…,j…},则B必定为A的一个栈混洗

将${j+1,i,j}$视作新一类的禁形，称为615禁形，${k,i,j}$称为915禁形。

接下来证明，只要B中含有915禁形，必然也含有615禁形，当然，两者中的$i,j$未必一致

假定对于任何的$k-i<d$,以上命题均成立，接下来考虑$k-i=d$的情况

不妨设$i<j<k-1$,于是元素$k-1$在B中的相对于$i$的位置无非两种可能

  1. k-1位于i的左方(前方) 此时${k-1,i,j}$即915禁形，$k-1-i<d$，所以必然含有615禁形
  2. k-1位于i的右侧 ${k,i,k-1}$即构成一个615禁形

若对任意1<j<k<=n，B中都不含模式{…,k,…,j-1,…,j…},则B未必为A的栈混洗

945特征${k,j-1,j}$不称作禁形，915禁形未必含有945模式。

例如，B={2,4,1,3}

其中{3,1,2},{4,1,2},{4,2,3}，不含有任何945模式，但是却含有915模式{4,2,3},同时也是615模式。

延迟缓冲

在一些应用问题中，输入可分解为多个单元并通过迭代依次扫描处理，但过程中的各步计算往往滞后于扫描的进度，需要待到必要信息已完整到一定程度时才能做出判断。在这类场合，栈结构可以扮演缓冲区的角色。

表达式求值

自左向右扫描表达式，用栈记录已经扫描的部分(含执行计算的结果)

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define N_OPTR 9 //运算符总数
typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator; //运算符集合
//加、减、乘、除、乘方、阶乘、左括号、右括号、起始符与终止符

const char pri[N_OPTR][N_OPTR] = { //运算符优先等级 [栈顶] [当前]
   /*              |-------------------- 当 前 运 算 符 --------------------| */
   /*              +      -      *      /      ^      !      (      )      \0 */
   /* --  + */    '>',   '>',   '<',   '<',   '<',   '<',   '<',   '>',   '>',
   /* |   - */    '>',   '>',   '<',   '<',   '<',   '<',   '<',   '>',   '>',
   /* 栈  * */    '>',   '>',   '>',   '>',   '<',   '<',   '<',   '>',   '>',
   /* 顶  / */    '>',   '>',   '>',   '>',   '<',   '<',   '<',   '>',   '>',
   /* 运  ^ */    '>',   '>',   '>',   '>',   '>',   '<',   '<',   '>',   '>',
   /* 算  ! */    '>',   '>',   '>',   '>',   '>',   '>',   ' ',   '>',   '>',
   /* 符  ( */    '<',   '<',   '<',   '<',   '<',   '<',   '<',   '=',   ' ',
   /* |   ) */    ' ',   ' ',   ' ',   ' ',   ' ',   ' ',   ' ',   ' ',   ' ',
   /* -- \0 */    '<',   '<',   '<',   '<',   '<',   '<',   '<',   ' ',   '='
};
float evaluate ( char* S, char*& RPN ) { //对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN
   Stack<float> opnd; Stack<char> optr; //运算数栈、运算符栈 任何时刻，其中每对相邻元素之间均大小一致
   char* expr = S;
   optr.push ( '\0' ); //尾哨兵'\0'也作为头哨兵首先入栈
   while ( !optr.empty() ) { //在运算符栈非空之前，逐个处理表达式中各字符
      if ( isdigit ( *S ) ) { //若当前字符为操作数，则
         readNumber ( S, opnd ); append ( RPN, opnd.top() ); //读入操作数，并将其接至RPN末尾
      } else //若当前字符为运算符，则
         switch ( orderBetween ( optr.top(), *S ) ) { //视其与栈顶运算符之间优先级高低分别处理
            case '<': //栈顶运算符优先级更低时
               optr.push ( *S ); S++; //计算推迟，当前运算符进栈
               break;
            case '=': //优先级相等（当前运算符为右括号或者尾部哨兵'\0'）时
               optr.pop(); S++; //脱括号并接收下一个字符
               break;
            case '>': { //栈顶运算符优先级更高时，可实施相应的计算，并将结果重新入栈
               char op = optr.pop(); append ( RPN, op ); //栈顶运算符出栈并续接至RPN末尾
               if ( '!' == op ) { //若属于一元运算符
                  float pOpnd = opnd.pop(); //只需取出一个操作数，并
                  opnd.push ( calcu ( op, pOpnd ) ); //实施一元计算，结果入栈
               } else { //对于其它（二元）运算符
                  float pOpnd2 = opnd.pop(), pOpnd1 = opnd.pop(); //取出后、前操作数
                  opnd.push ( calcu ( pOpnd1, op, pOpnd2 ) ); //实施二元计算，结果入栈
               }
               break;
            }
            default : exit ( -1 ); //逢语法错误，不做处理直接退出
         }//switch
   }//while
   return opnd.pop(); //弹出并返回最后的计算结果
}

试改进evaluate()算法，检查表达式的语法是否正确

确认每个操作符与其所对应操作数之间的相对位置符合中缀表达式的语法，在每个操作数入栈时，操作数的规模应该刚好比操作符栈的规模大一。注意，这里的操作符不包括括号和头尾标识符。

逆波兰表达式

逆波兰表达式在由运算符和操作数组成的表达式中，不使用括号即可表达带优先级的运算关系。

RPN转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void append ( char*& rpn, float opnd ) { //将操作数接至RPN末尾
   int n = strlen ( rpn ); //RPN当前长度（以'\0'结尾，长度n + 1）
   char buf[64];
   if ( opnd != ( float ) ( int ) opnd ) sprintf ( buf, "%.2f \0", opnd ); //浮点格式，或
   else                          sprintf ( buf, "%d \0", ( int ) opnd ); //整数格式
   rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + strlen ( buf ) + 1 ) ); //扩展空间
   strcat ( rpn, buf ); //RPN加长
}

void append ( char*& rpn, char optr ) { //将运算符接至RPN末尾
   int n = strlen ( rpn ); //RPN当前长度（以'\0'结尾，长度n + 1）
   rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + 3 ) ); //扩展空间
   sprintf ( rpn + n, "%c ", optr ); rpn[n + 2] = '\0'; //接入指定的运算符
}

RPN表达式无需括号即可确定运算优先级，是否意味着所占空间必少于常规表达式

未必，尽管RPN表达式可省去括号，但是必须在相邻的操作数、操作符之间插入特定的分隔符(通常为空格)。这种分隔符必须事先约定，且不能用以表示操作符和操作数，故称为元字符。引入元字符的数目与操作数和操作符的数目相当，故所占空间未必少于原表达式。

既然evaluate()算法已经可以求值，同时完成RPN转换有何意义

同样长度（指同样多操作数）的 RPN 比中缀表达式算得快。

若每个操作数都是一个具体的数，把中缀表达式转成 RPN 的过程已经足以得到中缀表达式的值，这种情况下转成 RPN 再计算得不偿失。

但是，操作数可能是一个未知数。例如中缀表达式 (a + b) * c 分别代入 n 组具体数字计算表达式值，例如代入 (a=1,b=2,c=3) 、 (a=4,b=5,c=6) 、 (a=10,b=11,c=12) 求值。不转就要算 n 次中缀表达式，转就只要转 1 次 + 算 n 次 RPN 。

逆波兰表达式的优点

  • 当有操作符时就计算，因此，表达式并不是从右至左整体计算而是每次由中心向外计算一部分，这样在复杂运算中就很少导致操作符错误。
  • 堆栈自动记录中间结果，这就是为什么逆波兰计算器能容易对任意复杂的表达式求值。与普通科学计算器不同，它对表达式的复杂性没有限制。
  • 逆波兰表达式中不需要括号，用户只需按照表达式顺序求值，让堆栈自动记录中间结果；同样的，也不需要指定操作符的优先级。
  • 机器状态永远是一个堆栈状态，堆栈里是需要运算的操作数，栈内不会有操作符。

试探回溯法

根据候选解的某些局部特征，即可判断其是否合理，以候选解的子集为单位批量地删除称为剪枝。

试探回溯模式

从0开始，逐渐增加候选解长度，一旦发现注定要失败，则收缩至前以长度，并继续试探。

N皇后问题

在n*n的棋盘上放置n个皇后，使得她们互不攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void placeQueens ( 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 ) ) ) //通过与已有皇后的比对
            /*DSA*///while ((q.y < N) && (solu.find(q))) //（若基于List实现Stack，则find()返回值的语义有所不同）
            { q.y++; nCheck++; } //尝试找到可摆放下一皇后的列
         if ( N > q.y ) { //若存在可摆放的列，则
            solu.push ( q ); //摆上当前皇后，并
            if ( N <= solu.size() ) nSolu++; //若部分解已成为全局解，则通过全局变量nSolu计数
            q.x++; q.y = 0; //转入下一行，从第0列开始，试探下一皇后
         }
      }
   } while ( ( 0 < q.x ) || ( q.y < N ) ); //所有分支均已或穷举或剪枝之后，算法结束
}

迷宫寻径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool labyrinth ( Cell Laby[LABY_MAX][LABY_MAX], Cell* s, Cell* t ) {
   if ( ( AVAILABLE != s->status ) || ( AVAILABLE != t->status ) ) return false; //退化情况
   Stack<Cell*> path; //用栈记录通路（Theseus的线绳）
   s->incoming = UNKNOWN; s->status = ROUTE; path.push ( s ); //起点
   do { //从起点出发不断试探、回溯，直到抵达终点，或者穷尽所有可能
      /*DSA*/displayLaby(); /*path.traverse(printLabyCell); printLabyCell(path.top());*/ getchar();
      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;
}

队列

与栈一样，队列也是存放数据对象的一种容器，其中的数据对象也按线性逻辑次序排列。同样只允许在队列两端进行操作，若插入对象只能从其中某一端，而删除只能从另外一端，将允许取出元素的一头称为队首，另外一端称为队尾。队列中各对象的操作次序遵循先进先出的规律：更早出队的元素应为更早入队者。

队列的应用

循环分配器

一群客户共享同一资源时，按照先来后到的顺序分配资源，例如多个应用程序共享cpu，实验室成员共享打印机

1
2
3
4
5
6
7
8
9
RoundRobin{
     Queue Q(clients);
     while(!ServiceClosed()){
         e=	Q.enqueue();
         serve(e);
         Q.enqueue(e);
     }
}

银行服务模拟

以银行这一典型场景为例，利用队列结构实现队顾客服务的调度和优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void simulate ( int nWin, int servTime ) { //按指定窗口数、服务总时间模拟银行业务
   Queue<Customer>* windows = new Queue<Customer>[nWin]; //为每一窗口创建一个队列
   for ( int now = 0; now < servTime; now++ ) { //在下班之前，每隔一个单位时间
      if ( rand() % ( 1 + nWin ) ) { //新顾客以nWin/(nWin + 1)的概率到达
         Customer c ; c.time = 1 + rand() % 98; //新顾客到达，服务时长随机确定
         c.window = bestWindow ( windows, nWin ); //找出最佳（最短）的服务窗口/*DSA*/ToDo: 更精细的策略
         windows[c.window].enqueue ( c ); //新顾客加入对应的队列
      }
      for ( int i = 0; i < nWin; i++ ) //分别检查
         if ( !windows[i].empty() ) //各非空队列
            if ( -- windows[i].front().time <= 0 ) //队首顾客的服务时长减少一个单位
               windows[i].dequeue(); //服务完毕的顾客出列，由后继顾客接替
   } //for
   delete [] windows; //释放所有队列（此前，~List()会自动清空队列）
}
int bestWindow ( Queue<Customer> windows[], int nWin ) { //为新到顾客确定最佳队列
   int minSize = windows[0].size(), optiWin = 0; //最优队列（窗口）
   for ( int i = 1; i < nWin; i++ ) //在所有窗口中
      if ( minSize > windows[i].size() ) //挑选出
         { minSize = windows[i].size(); optiWin = i; } //队列最短者
   return optiWin; //返回
}