數據結構學習(C++)之棧和隊列

棧和隊列是操作受限的線性表，好像每本講數據結構的數都是這麼說的。有些書按照這個思路給出了定義和實現；但是很遺憾，本文沒有這樣做，所以，有些書中的做法是重復建設，這或許可以用不是一個人寫的這樣的理由來開脫。

順序表示的棧和隊列，必須預先分配空間，並且空間大小受限，使用起來限制比較多。而且，由於限定存取位置，順序表示的隨機存取的優點就沒有了，所以，鏈式結構應該是首選。

棧的定義和實現

#ifndef Stack_H
#define Stack_H
#include "List.h"
template <class Type> class Stack : List<Type>//棧類定義
{
　public:
　　void Push(Type value)
　　{
　　　Insert(value);
　　}
　Type Pop()
　{
　　Type p = *GetNext();
　　RemoveAfter();
　　return p;
　}
　Type GetTop()
　{
　　return *GetNext();
　}
　List<Type> ::MakeEmpty;
　List<Type> ::IsEmpty;
};
#endif

隊列的定義和實現

#ifndef Queue_H
#define Queue_H
#include "List.h"
template <class Type> class Queue : List<Type>//隊列定義
{
　public:
　　void EnQueue(const Type &value)
　　{
　　　LastInsert(value);
　　}
　Type DeQueue()
　{
　　Type p = *GetNext();
　　RemoveAfter();
　　IsEmpty();
　　return p;
　}
　Type GetFront()
　{
　　return *GetNext();
　}
　List<Type> ::MakeEmpty;
　List<Type> ::IsEmpty;
};
#endif

測試程序

沒什麼好說的，你可以清楚的看到，在單鏈表的基礎上，棧和隊列的實現是如此的簡單。

棧應用

棧的應用很廣泛，棧的最大的用途是解決回溯問題，這也包含了消解遞歸；而當你用棧解決回溯問題成了習慣的時候，你就很少想到用遞歸了，比如迷宮求解。另外，人的習慣也是先入為主的，比如樹的遍歷，從學的那天開始，就是遞歸算法，雖然書上也教了用棧實現的方法，但應用的時候，你首先想到的還是遞歸；當然了，如果語言本身不支持遞歸（如BASIC），那棧就是唯一的選擇了——好像現在的高級語言都是支持遞歸的。

如下是表達式類的定義和實現，表達式可以是中綴表示也可以是後綴表示，用頭節點數據域裡的type區分，這裡有一點說明的是，由於單鏈表的賦值函數，我原來寫的時候沒有復制頭節點的內容，所以，要是在兩個表達式之間賦值，頭節點裡存的信息就丟了。你可以改寫單鏈表的賦值函數來解決這個隱患，或者你根本不不在兩個表達式之間賦值也行。

#ifndef Expression_H
#define Expression_H
#include "List.h"
#include "Stack.h"
#define INFIX 0
#define POSTFIX 1
#define OPND 4
#define OPTR 8
template <class Type> class ExpNode
{
　public:
　　int type;
　　union { Type opnd; char optr;};
　　ExpNode() : type(INFIX), optr('=') {}
　　ExpNode(Type opnd) : type(OPND), opnd(opnd) {}
　　ExpNode(char optr) : type(OPTR), optr(optr) {}
};
template <class Type> class Expression : List<ExpNode<Type> >
{
　public:
　　void Input()
　　{
　　　MakeEmpty(); Get()->type =INFIX;
　　　cout << endl << "輸入表達式，以＝結束輸入" << endl;
　　　Type opnd; char optr = ' ';
　　　while (optr != '=')
　　　{
　　　　cin >> opnd;
　　　　if (opnd != 0)
　　　　{
　　　　　ExpNode<Type> newopnd(opnd);
　　　　　LastInsert(newopnd);
　　　　}
　　　　cin >> optr;
　　　　ExpNode<Type> newoptr(optr);
　　　　LastInsert(newoptr);
　　　}
　　}
　　void Print()
　　{
　　　First();
　　　cout << endl;
　　　for (ExpNode<Type> *p = Next(); p != NULL; p = Next() )
　　　{
　　　　switch (p->type)
　　　　{
　　　　　case OPND:
　　　　　　cout << p->opnd; break;
　　　　　case OPTR:
　　　　　　cout << p->optr; break;
　　　　　default: break;
　　　　}
　　　　cout << ' ';
　　　}
　　　cout << endl;
　　}
　　Expression & Postfix() //將中綴表達式轉變為後綴表達式
　　{
　　　First();
　　　if (Get()->type == POSTFIX) return *this;
　　　Stack<char> s; s.Push('=');
　　　Expression temp;
　　　ExpNode<Type> *p = Next();
　　　while (p != NULL)
　　　{
　　　　switch (p->type)
　　　　{
　　　　　case OPND:
　　　　　　　temp.LastInsert(*p); p = Next(); break;
　　　　　case OPTR:
　　　　　　　while (isp(s.GetTop()) > icp(p->optr) )
　　　　　　　{
　　　　　　　　ExpNode<Type> newoptr(s.Pop());
　　　　　　　　temp.LastInsert(newoptr);
　　　　　　　}
　　　　　　　if (isp(s.GetTop()) == icp(p->optr) )
　　　　　　　{
　　　　　　　　s.Pop(); p =Next(); break;
　　　　　　　}
　　　　　　　s.Push(p->optr); p = Next(); break;
　　　　　default: break;
　　　　}
　　　}
　　　*this = temp;
　　　pGetFirst()->data.type = POSTFIX;
　　　return *this;
　　}
　　Type Calculate()
　　{
　　　Expression temp = *this;
　　　if (pGetFirst()->data.type != POSTFIX) temp.Postfix();
　　　Stack<Type> s; Type left, right;
　　　for (ExpNode<Type> *p = temp.Next(); p != NULL; p = temp.Next())
　　　{
　　　　switch (p->type)
　　　　{
　　　　　case OPND:
　　　　　　s.Push(p->opnd); break;
　　　　　case OPTR:
　　　　　　right = s.Pop(); left = s.Pop();
　　　　　　switch (p->optr)
　　　　　　{
　　　　　case '+': s.Push(left + right); break;
　　　　　case '-': s.Push(left - right); break;
　　　　　case '*': s.Push(left * right); break;
　　　　　case '/': if (right != 0) s.Push(left/right); else return 0; break;
　　　　　　// case '%': if (right != 0) s.Push(left%right); else return 0; break;
　　　　　　// case '^': s.Push(Power(left, right)); break;
　　　　　default: break;
　　　　}
　　　　default: break;
　　　}
　　}
　　return s.Pop();
}
private:
　int isp(char optr)
　{
　　switch (optr)
　　{
　　　case '=': return 0;
　　　case '(': return 1;
　　　case '^': return 7;
　　　case '*': return 5;
　　　case '/': return 5;
　　　case '%': return 5;
　　　case '+': return 3;
　　　case '-': return 3;
　　　case ')': return 8;
　　　default: return 0;
　　}
　}
　int icp(char optr)
　{
　　switch (optr)
　　{
　　　case '=': return 0;
　　　case '(': return 8;
　　　case '^': return 6;
　　　case '*': return 4;
　　　case '/': return 4;
　　　case '%': return 4;
　　　case '+': return 2;
　　　case '-': return 2;
　　　case ')': return 1;
　　　default: return 0;
　　}
　}
};
#endif

幾點說明

1、表達式用單鏈表儲存，你可以看到這個鏈表中既有操作數又有操作符，如果你看過我的《如何在一個鏈表中鏈入不同類型的對象》，這裡的方法也是對那篇文章的補充。

2、輸入表達式時，會將原來的內容清空，並且必須按照中綴表示輸入。如果你細看一下中綴表達式，你就會發現，除了括號，表達式的結構是“操作數”、“操作符”、“操作數”、……“操作符（＝）”，為了統一這個規律，同時也為了使輸入函數簡單一點，規定括號必須這樣輸入“0（”、“）0”；這樣一來，“0”就不能作為操作數出現在表達式中了。因為我沒有在輸入函數中增加容錯的語句，所以一旦輸錯了，那程序就“死”了。

3、表達式求值的過程是，先變成後綴表示，然後用後綴表示求值。因為原書講解的是這兩個算法，並且用這兩個算法就能完成中綴表達式的求值，所以我就沒寫中綴表達式的直接求值算法。具體算法說明參見原書，我就不廢話了。

4、Calculate()注釋掉的兩行，“％”是因為只對整型表達式合法，“^”的Power()函數沒有完成。

5、isp()，icp()的返回值，原書說的不細，我來多說兩句。‘＝’（表達式開始和結束標志）的棧內棧外優先級都是最低。‘（’棧外最高，棧內次最低。‘）’棧外次最低，不進棧。‘^’棧內次最高，棧外比棧內低。‘×÷％’棧內比‘^’棧外低，棧外比棧內低。‘＋－’棧內比‘×’棧外低，棧外比棧內低。這樣，綜合起來，就有9個優先級，於是就得出了書上的那個表。

隊列應用

我看的兩本教科書（《數據結構（C語言版）》還有這本黃皮書）都是以這個講解隊列應用的，而且都是銀行營業模擬（太沒新意了）。細比較，這兩本書模擬的銀行營業的方式還是不同的。1997版的《數據結構（C語言版）》的銀行還是老式的營業模式（畢竟是1997年的事了），現在的很多地方還是這種營業模式——幾個窗口同時排隊。這種方式其實不太合理，經常會出現先來的還沒有後來的先辦理業務（常常前面一個人磨磨蹭蹭，別的隊越來越短，讓你恨不得把前面那人干掉）。1999版的這本黃皮書的銀行改成了一種掛牌的營業方式，每個來到的顧客發一個號碼，如果哪個櫃台空閒了，就叫號碼最靠前的顧客來辦理業務；如果同時幾個櫃台空閒，就按照一種法則來決定這幾個櫃台叫號的順序（最簡單的是按櫃台號碼順序）。這樣，就能保證顧客按照先來後到的順序接受服務——因為大家排在一個隊裡。這樣的營業模式我在北京的西直門工商銀行見過，應該說這是比較合理的一種營業模式。不過，在本文中最重要的是，這樣的營業模式比較好模擬（一個隊列總比N個隊列好操作）。

原書的這部分太難看了，我看的暈暈的，我也不知道按照原書的方法能不能做出來，因為我沒看懂（旁白：靠，你小子這樣還來現眼）。我按照實際情況模擬，實現如下：

　　#ifndef Simulation_H
#define Simulation_H
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
　　class Teller
{
　public:
　　int totalCustomerCount;
　　int totalServiceTime;
　　int finishServiceTime;
　　Teller() :totalCustomerCount(0), totalServiceTime(0),
　　finishServiceTime(0) {}
};
//#define PRINTPROCESS
class Simulation
{
　public:
　　Simulation()
　　{
　　　cout << endl << "輸入模擬參數" << endl;
　　　cout << "櫃台數量："; cin >> tellerNum;
　　　cout << "營業時間："; cin >> simuTime;
　　　cout << "兩個顧客來到的最小間隔時間："; cin >> arrivalLow;
　　　cout << "兩個顧客來到的最大間隔時間："; cin >> arrivalHigh;
　　　cout << "櫃台服務最短時間："; cin >> serviceLow;
　　　cout << "櫃台服務最長時間："; cin >> serviceHigh;
　　　arrivalRange = arrivalHigh - arrivalLow + 1;
　　　serviceRange = serviceHigh - serviceLow + 1;
　　　srand((unsigned)time(NULL));
　　}
　　Simulation(int tellerNum, int simuTime, int arrivalLow, int arrivalHigh, int serviceLow, int serviceHigh)
: tellerNum(tellerNum), simuTime(simuTime), arrivalLow(arrivalLow), arrivalHigh(arrivalHigh),
　　serviceLow(serviceLow), serviceHigh(serviceHigh),
　　arrivalRange(arrivalHigh - arrivalLow + 1), serviceRange(serviceHigh - serviceLow + 1)
　　{ srand((unsigned)time(NULL)); }
void Initialize()
{
　curTime = nextTime = 0;
　customerNum = customerTime = 0;
　for (int i = 1; i <= tellerNum; i++)
　{
　　tellers[i].totalCustomerCount = 0;
　　tellers[i].totalServiceTime = 0;
　　tellers[i].finishServiceTime = 0;
　}
　customer.MakeEmpty();
}
void Run()
{
　Initialize();
　NextArrived();
　#ifdef PRINTPROCESS
　　cout << endl;
　　cout << "tellerID";
　　for (int k = 1; k <= tellerNum; k++) cout << "\tTELLER " << k;
　　cout << endl;
　#endif
　for (curTime = 0; curTime <= simuTime; curTime++)
　{
　　if (curTime >= nextTime)
　　{
　　　CustomerArrived();
　　　NextArrived();
　　}
　　#ifdef PRINTPROCESS
　　　cout << "Time: " << curTime << " ";
　　#endif
　　for (int i = 1; i <= tellerNum; i++)
　　{
　　　if (tellers[i].finishServiceTime < curTime) tellers[i].finishServiceTime = curTime;
　　　if (tellers[i].finishServiceTime == curTime && !customer.IsEmpty())
　　　{
　　　　int t = NextService();
　　　　#ifdef PRINTPROCESS
　　　　　cout << '　　' << customerNum + 1 << '(' << customer.GetFront() << ',' << t << ')';
　　　　#endif
　　　　CustomerDeparture();
　　　　tellers[i].totalCustomerCount++;
　　　　tellers[i].totalServiceTime += t;
　　　　tellers[i].finishServiceTime += t;
　　　}
　　　#ifdef PRINTPROCESS
　　　else cout << "　　 ";
　　　#endif
　　}
　　#ifdef PRINTPROCESS
　　　cout << endl;
　　#endif
　}
　PrintResult();
}
void PtintSimuPara()
{
　cout << endl << "模擬參數" << endl;
　cout << "櫃台數量： " << tellerNum << "　　營業時間：" << simuTime << endl;
　cout << "兩個顧客來到的最小間隔時間：" << arrivalLow << endl;
　cout << "兩個顧客來到的最大間隔時間：" << arrivalHigh << endl;;
　cout << "櫃台服務最短時間：" << serviceLow << endl;
　cout << "櫃台服務最長時間：" << serviceHigh << endl;
}
void PrintResult()
{
　int tSN = 0;
　long tST = 0;
　cout << endl;
　cout << "－－－－－－－－－－－－－模擬結果－－－－－－－－－－－－－－－－－－－";
　cout << endl << "tellerID　　ServiceNum　　ServiceTime　　AverageTime" << endl;
　for (int i = 1; i <= tellerNum; i++)
　{
　　cout << "TELLER " << i;
　　cout << '　　' << tellers[i].totalCustomerCount << " "; tSN += tellers[i].totalCustomerCount;
　　cout << '　　' << tellers[i].totalServiceTime << " "; tST += (long)tellers[i].totalServiceTime;
　　cout << '　　';
　　if (tellers[i].totalCustomerCount)
　　　cout << (float)tellers[i].totalServiceTime/(float)tellers[i].totalCustomerCount;
　　else cout << 0;
　　　cout << " " << endl;
　}
　cout << "TOTAL 　　" << tSN << " 　　" << tST << " 　　";
　if (tSN) cout << (float)tST/(float)tSN; else cout << 0;
　cout << " " << endl;
　cout << "Customer Number:　　" << customerNum << "　　no Service:　　" << customerNum - tSN << endl;
　cout << "Customer WaitTime:　　" << customerTime << "　　AvgWaitTime:　　";
　if (tSN) cout << (float)customerTime/(float)tSN; else cout << 0;
　cout << endl;
}
private:
　int tellerNum;
　int simuTime;
　int curTime, nextTime;
　int customerNum;
　long customerTime;
　int arrivalLow, arrivalHigh, arrivalRange;
　int serviceLow, serviceHigh, serviceRange;
　Teller tellers[21];
　Queue<int> customer;
　void NextArrived()
　{
　　nextTime += arrivalLow + rand() % arrivalRange;
　}
　int NextService()
　{
　　return serviceLow + rand() % serviceRange;
　}
void CustomerArrived()
{
　customerNum++;
　customer.EnQueue(nextTime);
}
void CustomerDeparture()
{
　customerTime += (long)curTime - (long)customer.DeQueue();
}
};
#endif

幾點說明

1、Run()的過程是這樣的：curTime是時鐘，從開始營業計時，自然流逝到停止營業。當顧客到的事件發生時（顧客到時間等於當前時間，小於判定是因為個別時候顧客同時到達——輸入arrivalLow＝0的情況，而在同一時間，只給一個顧客發號碼），給這個顧客發號碼（用顧客到時間標示這個顧客，入隊，來到顧客數增1）。當櫃台服務完畢時（櫃台服務完時間等於當前時間），該櫃台服務人數增1，服務時間累加，顧客離開事件發生，下一個顧客到該櫃台。因為櫃台開始都是空閒的，所以實際代碼和這個有點出入。最後，停止營業的時候，停止發號碼，還在接受服務的顧客繼續到服務完，其他還在排隊的就散伙了。

2、模擬結果分別是：各個櫃台的服務人數、服務時間、平均服務時間，總的服務人數、服務時間、平均服務時間，來的顧客總數、沒被服務的數目（來的太晚了）、接受服務顧客總等待時間、平均等待時間。

3、這個算法效率是比較低的，實際上可以不用隊列完成這個模擬（用顧客到時間推動當前時鐘，櫃台直接公告服務完成時間），但這樣就和實際情況有很大差別了——出納員沒等看見人就知道什麼時候完？雖然結果是一樣的，但是理解起來很莫名其妙，尤其是作為教學目的講解的時候。當然了，實際中為了提高模擬效率，本文的這個算法是不值得提倡的。

4、注釋掉的#define PRINTPROCESS，去掉注釋符後，在運行模擬的時候，能打印出每個時刻櫃台的服務情況（第幾個顧客，顧客到達時間，接受服務時間），但只限4個櫃台以下，多了的話屏幕就滿了（格式就亂了）。

這是數據結構中第一個實際應用的例子，而且也有現實意義。你可以看出各個櫃台在不同的業務密度下的工作強度（要麼給哪個櫃台出納員發獎金，要麼輪換櫃台），各種情況下顧客的等待時間（人都是輪到自己就不著急了），還有各種情況下設立幾個櫃台合理（很少的空閒時間，很短的等待時間，幾乎為零的未服務人數）。例如這樣：

for (int i = 1; i < 16; i++)
{
　Simulation a(i,240,1,4,8,15);
　a.Run();
}

你模擬一下就會得出，在不太繁忙的銀行，4～5個櫃台是合適的——現在的銀行大部分都是這樣的。