关于用动态数组实现堆栈的问题
这是《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;
// create_stack函数
int create_stack( size_t size )
{
if( stack_size != 0)
{
printf( "stack already created. ");
abort();
}
stack_size = size;
stack = ( STACK_TYPE *)malloc( stack_size * sizeof( STACK_TYPE ) );
if( stack == NULL)
{
printf( "create stack false,please try again(size <max(size_t)). \n ");
return 0;
}
return 1;
}
// destroy_stack函数
int destroy_stack( void )
{
if( stack_size == 0 )
{
printf( "destroy stack false.\n ");
return 0;
}
stack_size = 0;
free( stack );
stack = NULL;
return 1;
}
// push函数
void push( STACK_TYPE value )
{
if( is_full() ) // 若堆栈已满，条件成立.
{
printf( "stack already full.\n ");
exit(0);
}
top_element += 1;
stack[ top_element ] = value;
}
// pop函数
void pop( void )
{
if( is_empty() ) // 若堆栈已空，条件成立.
{
printf( "stack already empty.\n ");
exit(0);
}
top_element -= 1;
}
// top函数
STACK_TYPE top( void )
{
if( is_empty() ) // 若堆栈已空，条件成立.
{
printf( "stack already empty.\n ");
exit(0);
}
return stack[ top_element ];
}
// is_empty函数
int is_empty( void )
{
if( stack_size == 0 ) // 若堆栈空时.
{
printf( "stack is empty,please create stack firstly.\n ");
exit(0);
}
return top_element == -1;
}
// is_full函数
int is_full( void )
{
if( stack_size == 0 ) // 若堆栈空时.
{
printf( "stack is empty,please create stack firstly.\n ");
exit(0);
}
return top_element == (signed int)(stack_size - 1);
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1470068
[解决办法]
数组和链表是两种不同的数据结构体，不能说喜欢用什么就用什么，根据需要的情况使用，因为数组是在内存空间是连续分布，而链表不需要，所以在搜索的时候的复杂度有所不同。
如果你想用数组实现堆栈的某些功能，那么你需要定义一个比较大的数组，用＋－1的方法来实现PUSH 和 POP。但是这样就浪费了数组最好的功能，就是直接根据INDEX得到需要的数据。
打个比方，吃牛杂串，你非要用个碗和一对筷子而不用竹签。你说那个更浪费？
[解决办法]
楼主可以去看看《STL源码剖析》
[解决办法]
聪明一点的做法是new 原来的大小 + 一个适合的大小
