WEB开发网
开发学院软件开发C++ 数据结构学习(C++)之栈和队列 阅读

数据结构学习(C++)之栈和队列

 2008-03-08 21:32:12 来源:WEB开发网   
核心提示:栈和队列是操作受限的线性表,似乎每本讲数据结构的数都是这么说的,数据结构学习(C++)之栈和队列,有些书按照这个思路给出了定义和实现;但是很遗憾,本文没有这样做,在不太繁忙的银行,4~5个柜台是合适的——现在的银行大部分都是这样的,所以,有些书中的做法是重复建设
  栈和队列是操作受限的线性表,似乎每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现;但是很遗憾,本文没有这样做,所以,有些书中的做法是重复建设,这或许可以用不是一个人写的这样的理由来开脱。


  顺序表示的栈和队列,必须预先分配空间,并且空间大小受限,使用起来限制比较多。而且,由于限定存取位置,顺序表示的随机存取的优点就没有了,所以,链式结构应该是首选。

  栈的定义和实现
#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   测试程序
#ifndef StackTest_H
#define StackTest_H
#include "Stack.h"

void StackTest_int()
{
 cout << endl << "整型栈测试" << endl;
 cout << endl << "构造一个空栈" << endl;
 Stack<int> a;
 cout << "将1~20入栈,然后再出栈" << endl;
 for (int i = 1; i <= 20; i++) a.Push(i);
  while (!a.IsEmpty()) cout << a.Pop() << ' ';
  cout << endl;
}
#endif

#ifndef QueueTest_H
#define QueueTest_H
#include "Queue.h"

void QueueTest_int()
{
 cout << endl << "整型队列测试" << endl;
 cout << endl << "构造一个空队列" << endl;
 Queue<int> a;
 cout << "将1~20入队,然后再出队" << endl;
 for (int i = 1; i <= 20; i++) a.EnQueue(i);
 while (!a.IsEmpty()) cout << a.DeQueue() << ' ';
 cout << endl;
}
#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 << '\t' << customerNum + 1 << '(' << customer.GetFront() << ',' << t << ')';
    #endif
    CustomerDeparture();
    tellers[i].totalCustomerCount++;
    tellers[i].totalServiceTime += t;
    tellers[i].finishServiceTime += t;
   }

   #ifdef PRINTPROCESS
   else cout << "\t ";
   #endif
  }
  #ifdef PRINTPROCESS
   cout << endl;
  #endif
 }
 PrintResult();
}

void PtintSimuPara()
{
 cout << endl << "模拟参数" << endl;
 cout << "柜台数量: " << tellerNum << "\t营业时间:" << 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\tServiceNum\tServiceTime\tAverageTime" << endl;
 for (int i = 1; i <= tellerNum; i++)
 {
  cout << "TELLER " << i;
  cout << '\t' << tellers[i].totalCustomerCount << " "; tSN += tellers[i].totalCustomerCount;
  cout << '\t' << tellers[i].totalServiceTime << " "; tST += (long)tellers[i].totalServiceTime;

  cout << '\t';
  if (tellers[i].totalCustomerCount)
   cout << (float)tellers[i].totalServiceTime/(float)tellers[i].totalCustomerCount;
  else cout << 0;
   cout << " " << endl;
 }
 cout << "TOTAL \t" << tSN << " \t" << tST << " \t";
 if (tSN) cout << (float)tST/(float)tSN; else cout << 0;
 cout << " " << endl;
 cout << "Customer Number:\t" << customerNum << "\tno Service:\t" << customerNum - tSN << endl;

 cout << "Customer WaitTime:\t" << customerTime << "\tAvgWaitTime:\t";
 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个柜台是合适的——现在的银行大部分都是这样的。

 
更多文章 更多内容请看数据结构 数据结构教程 数据结构相关文章专题,或

Tags:数据结构 学习 队列

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接