# 堆栈的实现

2015/05/19 19:33

/** * 堆栈是一个线性表，其插入和删除操作都在同一端进行 * 其中一端成为栈顶，另一端成为栈底 * * 堆栈是一种先进后出或者是后进先出的数据结构 * 可以使用公式化描述实现堆栈，也可以使用链表实现堆栈 * */
#include "Exception.h"
#include <iostream>

using namespace std;

/** * 适用公式化描述实现LinearStack */
template<class T>
class LinearStack{
public:
LinearStack(int MaxLinearStackSize = 10);
~LinearStack(){delete [] stack;}
T Top() const;  //获取栈顶元素
LinearStack<T>& Delete(T& x);   //从栈中删除一个元素
int Size() const;   //获取堆栈的大小
void print(); //输出堆栈中的数据

private:
int top;  //栈顶
int MaxTop; //栈的最大容量
T *stack;
};

template <class T>
LinearStack<T>::LinearStack(int MaxLinearStackSize){
MaxTop = MaxLinearStackSize - 1;
top = -1;
stack = new T[MaxLinearStackSize];
}

template<class T>
T LinearStack<T>::Top() const{
if(isEmpty()) throw OutOfBounds();

else return stack[top];
}

template<class T>
if(isFull()) throw OutOfBounds();

top ++;
stack[top] = x;

return *this;
}

template<class T>
LinearStack<T>& LinearStack<T>::Delete(T& x){
if(isEmpty()) throw OutOfBounds();

x = stack[top--];

return *this;
}

template<class T>
int LinearStack<T>::Size() const{

int size = top+1;

return size;
}

template<class T>
int size = this->Size();

int left = MaxTop + 1 - size;

throw OutOfBounds();

for(int i = 0;i < addedSize;i++){
}

return *this;
}

template<class T>
void LinearStack<T>::print(){
int size = this->Size();

for(int i = size-1;i >= 0;i--){
cout << stack[i] << " ";
}

cout << endl;
}

/* * LinkedStack.cpp * * Created on: 2015年5月7日 * Author: 洪波 */

#include "Exception.h"
#include <iostream>

using namespace std;

template<class T>

template<class T>
class Node{

private:
T data;
};

template<class T>
public:
bool IsFull() const;
T Top() const;
void print();

private:
Node<T> *top;  //指向栈顶节点
};

template<class T>
Node<T> *next;
while(top){
delete top;

top = next;
}
}

template<class T>
try{
Node<T> *p = new Node<T>();
delete p;
return false;
}catch(NoMem &nm){
return true;
}
}

template<class T>

}

template<class T>

Node<T> *node = new Node<T>();
node->data = x;

top = node;

return *this;
}

template<class T>
if(IsEmpty()) throw OutOfBounds();

Node<T> *p = top;
x = top->data;

delete p;

return *this;
}

template<class T>
Node<T> *p = top;

while(p){
cout << p->data << " ";
}

cout << endl;
}


/* * Test.cpp * * Created on: 2015年5月7日 * Author: 洪波 */
#include "LinearStack.cpp"

int main(){

/********************************************** * 测试 LinearStack * **********************************************/
// LinearStack<int> ls(10);
//
//
//
// ls.print();
//
// int array[3] = {30,40,50};
//
//
// ls.print();

/*====================================================*/

/********************************************** * 测试 LinkedStack * **********************************************/

int n;
cout << n << endl;
return 0;
}


0
1 收藏

0 评论
1 收藏
0