數(shù)據(jù)結構學習記錄連載8（堆棧提高要求續(xù)）

說明：提高要求的鏈式堆棧實現(xiàn)與測試

1.StackNode.h：鏈式堆棧的結點類

/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發(fā)組
* All rights reserved.
*
* 文件名稱：StackNode.h
* 摘 要： 堆鏈式棧類的定義與實現(xiàn)
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/
template <class T> class LinkStack; //前向聲明

template <class T>
class StackNode
{
 friend class LinkStack<T>;
private:
 StackNode<T> *next;
public:
 T data;

 StackNode(const T& item, StackNode<T> *ptrNext = NULL)
 {
  data = item;
  next = ptrNext;
 }

 ~StackNode(){}
};

2.LinkStack.h：定義鏈式堆棧類和實現(xiàn)接口

/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發(fā)組
* All rights reserved.
*
* 文件名稱：LinkStack.h
* 摘 要： 堆鏈式棧類的定義與實現(xiàn)
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include "StackNode.h"
template <class T>
class LinkStack
{
private:
 StackNode<T> *top;
 int size;
public:
 LinkStack(void);
 ~LinkStack(void);

 int StackSize(void) const;  //堆棧數(shù)據(jù)個數(shù)
 int StackEmpty(void) const;  //堆棧是否為空（返回1）
 void Push(const T& item);  //入棧
 T Pop(void);     //出棧
 T Peek(void);     //返回棧頂數(shù)據(jù)
 void ClearStack(void);   //清空堆棧
};

template <class T>
LinkStack<T>::LinkStack(void)
{
 top = NULL;
 size = 0;
}

template <class T>
LinkStack<T>::~LinkStack(void)
{
 ClearStack();
 top = NULL;
}

template <class T>
int LinkStack<T>::StackSize(void) const
{
 return size;
}

template <class T>
int LinkStack<T>::StackEmpty(void) const
{
 return size == 0 ? 1 : 0;
}

/*
* 函數(shù)名稱: Push
* 輸　入: item
* item: 壓入堆棧的數(shù)據(jù)
* 輸　出:
* 功能描述: 將item入棧
* 作　者: 吳友強
* 日　期: 2009年10月17日
* 修　改:
* 日　期:
*/
template <class T>
void LinkStack<T>::Push(const T& item)
{
 StackNode<T> *newNode = new StackNode<T>(item, top);
 top = newNode;
 size++;
}

template <class T>
T LinkStack<T>::Pop(void)
{
 if (size == 0)
 {
  cout << "堆棧以空無元素可刪除" << endl;
  exit(0);
 }

 StackNode<T> *p = top->next;
 T data = top->data;
 delete top;
 size--;
 top = p;
 return data;
}

template <class T>
T LinkStack<T>::Peek(void)
{
 return top->data;
}

template <class T>
void LinkStack<T>::ClearStack(void)
{
 StackNode<T> *p, *q;

 p = top;
 while (p != NULL)
 {
  q = p;
  p = p->next;
  delete q;
 }
 size = 0;
}

3.LinkStackTest.cpp：測試程序，計算后綴表達式（加減乘除）

/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發(fā)組
* All rights reserved.
*
* 文件名稱：LinkStackTest.cpp
* 摘 要： 測試鏈式堆棧的功能,計算后綴表達式（加減乘除）
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月17日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include <iostream.h>
#include <stdlib.h>
#include <ctype.h>

#include "LinkStack.h"

/*
* 函數(shù)名稱: Insert
* 輸　入: s
*   s: 用作存儲的數(shù)據(jù)結構
* 輸　出:
* 功能描述: 借助堆棧s計算后綴表達式的值后屏幕輸出
* 作　者: 吳友強
* 日　期: 2009年10月17日
* 修　改:
* 日　期:
*/
template <class T>
void PostExp(LinkStack<T> &s)
{
 char ch;
 T x, x1, x2;

 cout << "輸入后綴表達式，結尾加符號#" << endl;

 while (cin >> ch, ch != '#')  //輸入字符直到輸入為'#'
 {
  if (isdigit(ch))    //ch為操作數(shù)
  {
   cin.putback(ch);   //回退一位
   cin >> x;     //輸入數(shù)值給變量x
   s.Push(x);     //數(shù)值入棧
  }
  else       //ch為操作符
  {
   x2 = s.Pop();    //退棧得操作數(shù)
   x1 = s.Pop();    //退棧得被操作數(shù)
   switch (ch)
   {
   case '+':
    {
     x1 += x2;
     break;
    }
   case '-':
    {
     x1 -= x2;
     break;
    }
   case '*':
    {
     x1 *= x2;
     break;
    }
   case '/':
    {
     x1 /= x2;
     break;
    }
   default:
    break;
   }
   s.Push(x1);     //操作結果入棧
  }
 }
 cout << "后綴表達式計算結果為：" << s.Pop() << endl;
}

int main()
{
 LinkStack<int> s;
 PostExp(s);

 return 0;
}