关于用动态数组实现堆栈的有关问题
关于用动态数组实现堆栈的问题
这是《C++ Primer Plus(第四版)》第12章的课后习题第四题：
有如下的类声明
// stack.h — class declaration for the stack ADT
typedef unsigned long Item;
class Stack
{
private:
enum { MAX = 10} ; // constant specific to class
Item * pitems; // holds stack items
int size; // number of elements in stack
int top; // index for top stack item
public:
Stack(int n = 10); // creates stack with n elements
Stack(const Stack & st);
~Stack();
bool isempty() const;
bool isfull() const;
// push() returns false if stack already is full, true otherwise
bool push(const Item & item); // add item to stack
// pop() returns false if stack already is empty, true otherwise
bool pop(Item & item); // pop top into item
Stack & operator=(const Stack & st);
} ;
正如私有成员表明的，这个类使用动态分配的数组来保存堆栈项，请实现该类的定义并编写一个程序来演示所有方法，包括复制构造函数和赋值操作符。
这是一个简化了的堆栈，我就不解释每个方法的意思了。如果是用数组“Item pitems[MAX]”来实现，就很简单，可是用动态数组怎么做呢？最关键的一个问题是：在push时，怎么增大动态数组，并将它与以前的数组联系起来？用链表能够实现，可是用数组该怎么办？
我能想得的方法就是：在push时，重新new一个新的数组（大小是原来的大小＋1），然后将原来的数组元素和pust的那个元素拷贝进去，再把原来的那个数组delete了。可是这样太笨拙了，我觉得标准答案应该不是这样（可恶的是这本书的练习题没有答案）。
所以，只好请各位高手相助了，谢谢！^_^
BTW：STL里面也有Stack，它是用什么实现的呢？
------解决方案--------------------
差不多是那樣了
------解决方案--------------------
你可以先分配一个比较大的数组，比如说100，栈头和栈尾都指向第一个元素。
push:
if(栈尾-栈头==100）{//空间如何增大可以灵活决定
重新分配更大的空间；
拷贝元素；
}
栈尾上移一位；
在栈尾加入元素;
}
大致就是这样，STL中的栈也差不多这么实现。
------解决方案--------------------
动态数组实现的堆栈
/*_############################################################################
_##
_## 动态数组实现的堆栈
_## Author: xwlee
_## Time: 2006.12.31
_## Chang 'an University
_## Development condition: win2003 Server+VC6.0
_##
_## dynamic_array.cpp 文件
_##########################################################################*/
#include "stack.h "
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
static STACK_TYPE *stack;
static size_t stack_size;
static int top_element = -1;
这是《C++ Primer Plus(第四版)》第12章的课后习题第四题：
有如下的类声明
// stack.h — class declaration for the stack ADT
typedef unsigned long Item;
class Stack
{
private:
enum { MAX = 10} ; // constant specific to class
Item * pitems; // holds stack items
int size; // number of elements in stack
int top; // index for top stack item
public:
Stack(int n = 10); // creates stack with n elements
Stack(const Stack & st);
~Stack();
bool isempty() const;
bool isfull() const;
// push() returns false if stack already is full, true otherwise
bool push(const Item & item); // add item to stack
// pop() returns false if stack already is empty, true otherwise
bool pop(Item & item); // pop top into item
Stack & operator=(const Stack & st);
} ;
正如私有成员表明的，这个类使用动态分配的数组来保存堆栈项，请实现该类的定义并编写一个程序来演示所有方法，包括复制构造函数和赋值操作符。
这是一个简化了的堆栈，我就不解释每个方法的意思了。如果是用数组“Item pitems[MAX]”来实现，就很简单，可是用动态数组怎么做呢？最关键的一个问题是：在push时，怎么增大动态数组，并将它与以前的数组联系起来？用链表能够实现，可是用数组该怎么办？
我能想得的方法就是：在push时，重新new一个新的数组（大小是原来的大小＋1），然后将原来的数组元素和pust的那个元素拷贝进去，再把原来的那个数组delete了。可是这样太笨拙了，我觉得标准答案应该不是这样（可恶的是这本书的练习题没有答案）。
所以，只好请各位高手相助了，谢谢！^_^
BTW：STL里面也有Stack，它是用什么实现的呢？
------解决方案--------------------
差不多是那樣了
------解决方案--------------------
你可以先分配一个比较大的数组，比如说100，栈头和栈尾都指向第一个元素。
push:
if(栈尾-栈头==100）{//空间如何增大可以灵活决定
重新分配更大的空间；
拷贝元素；
}
栈尾上移一位；
在栈尾加入元素;
}
大致就是这样，STL中的栈也差不多这么实现。
------解决方案--------------------
动态数组实现的堆栈
/*_############################################################################
_##
_## 动态数组实现的堆栈
_## Author: xwlee
_## Time: 2006.12.31
_## Chang 'an University
_## Development condition: win2003 Server+VC6.0
_##
_## dynamic_array.cpp 文件
_##########################################################################*/
#include "stack.h "
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
static STACK_TYPE *stack;
static size_t stack_size;
static int top_element = -1;