开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
b_stack.h
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：2k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

b_stack.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  b_stack.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_BSTACK_H
  14. #define LEDA_BSTACK_H
  16. //------------------------------------------------------------------------------
  17. // bounded stacks 
  18. //------------------------------------------------------------------------------
  20. #include <LEDA/basic.h>
  22. /*{Manpage {b_stack} {E} {Bounded Stacks}}*/
  25. template<class E> 
  27. class b_stack
  28. {
  29. /*{Mdefinition
  30. An instance $S$ of the parameterized data type name is a stack
  31. (see section ref{Stacks}) of bounded size.}*/
  33. E* first;  // start of array
  34. E* stop;   // one position behind last element
  35. E* free;   // pointer to first free element
  37. public:
  39. /*{Mcreation S }*/
  42. b_stack(int n)
  43. {
  44. #if !defined(LEDA_CHECKING_OFF)
  45.   if (n<1) error_handler(99,"bounded stack: bad size");
  46. #endif
  47.   free = first = new E[n];
  48.   stop = first + n;
  49.   if (first==0) error_handler(99,"bounded stack: out of memory");
  50.  }
  51. /*{Mcreate creates an instance var of type name that can hold up to $n$ 
  52.             elements.  var is initialized with the empty stack.}*/
  55. virtual ~b_stack() { delete [] first; }
  57. /*{Moperations 2 4}*/
  59. E top() const
  60. {
  61. #if !defined(LEDA_CHECKING_OFF)
  62.   if (free==first) error_handler(99,"bounded stack: empty");
  63. #endif
  64.   return *(free-1);
  65.   }
  67. /*{Mop     returns the top element of var.\
  68.     precond $S$ is not empty.}*/
  70. E pop()
  71. {
  72. #if !defined(LEDA_CHECKING_OFF)
  73.   if (free==first) error_handler(99,"b_stack underflow");
  74. #endif
  75. return *--free;
  76. }
  77. /*{Mop   deletes and returns the top element of var.\
  78.   precond $S$ is not empty.}*/
  80. void push(const E& x)
  81. {
  82. #if !defined(LEDA_CHECKING_OFF)
  83.   if (free==stop) error_handler(99,"bounded stack: overflow");
  84. #endif
  85.   *free++ = x;
  86. }
  87. /*{Mop  adds $x$ as new top element to var.\
  88.  precond $S$.size() $< n$.}*/
  90. void clear() { free = first; }
  91. /*{Mop   makes var the empty stack.}*/
  93. int   size()  const { return free - first; }
  94. /*{Mop    returns the size of var.}*/
  96. bool   empty() const { return (free==first) ? true : false; }
  97. /*{Mop  returns true if var is empty, false otherwise.}*/
  99. };
  101. /*{Mimplementation
  102. Bounded stacks are implemented by CC vectors. All operations take
  103. time $O(1)$. The space requirement is $O(n)$.}*/
  105. #endif