Question

高分悬赏！！！[C++]利用链表构造一个堆栈类Stack

利用链表构造一个堆栈类Stack，
定义在链表上的最小操作为
插入(push)—在链表前面增加一个项
获取(pop)—获取链表第一个项，并将之删除
清除(clear)—在链表中删除所有的项

Answer 1

如果允许用标准库的话，或者你的链表能够提供如push_front()，pop_front()，或者push_back(),pop_back()中的任意一对和clear()函数，事情就好办了：
简单的标准库版本：（只有四个函数，top（））
#include <iostream>
#include <list>
using namespace std;

template <typename Type>
class Stack {
public:
void push(Type elem)
{
slist.push_back(elem);
}
void pop()
{
slist.pop_back();
}
void clear()
{
slist.clear();
}
Type top()
{
return slist.back();
}
private:
list<Type> slist;
};

int main ()
{
Stack<int> st;
st.push(2);
st.push(3);
st.pop();
cout << st.top() << endl;
}
自己编写的版本：（较为完善，empty(),size()，top()等都有）
#include <iostream>
using namespace std;

template <class Type>
class Stack {
private:
struct Node;
public:
Stack():theSize(0), head(0) { }
~Stack();
size_t size() const;
bool empty() const;
void clear();
Type& top();
const Type& top() const;
void push(const Type& x);
void pop();
private:
Node* head;
size_t theSize;
};

template <class Type>
struct Stack<Type>::Node
{
Node(const Type& i = Type(), Node* n = NULL)
:item(i), next(n) { }
Type item;
Node* next;
};

template <class Type>
Stack<Type>::~Stack()
{
while (head) {
Node*temp = head;
head = head->next;
delete temp;
}
}

template <class Type>
size_t Stack<Type>::size() const
{
return theSize;
}

template <class Type>
bool Stack<Type>::empty() const
{
return theSize==0;
}

template <class Type>
void Stack<Type>::clear()
{
while (head) {
Node* temp;
temp = head;
head = head->next;
delete temp;
}
theSize = 0;
}

template <class Type>
Type& Stack<Type>::top()
{
return head->item;
}

template <class Type>
const Type& Stack<Type>::top() const
{
return head->item;
}

template <class Type>
void Stack<Type>::push(const Type& x)
{
Node* temp = head;
head = new Node;
head->next = temp;
head->item = x;
++theSize;
}

template <class Type>
void Stack<Type>::pop()
{
Node* temp = head;
head = head->next;
delete temp;
--theSize;
}

int main ()
{
Stack<int> st;
st.push(2);
st.push(3);
st.push(4);
st.push(3);
st.pop();
cout << st.top() << endl;
cout << st.size() << endl;
if (st.empty())
cout << "empty" << endl;
else
cout << "not empty" << endl;
st.clear();
if (st.empty())
cout << "empty" << endl;
}
第二个，是我将以前的自己编的list头文件改编过来的，其中的push(),pop()分别取的是list中的pust_front(),pop_front()两个函数。用模板可能一些老编译器（包括VC6.0）编译不能通过，我的是在VC2008上运行的，当然你也可以再C++builder2009上运行，还有，如果你需要份文件运行，不要将Stack模板类的的定义和其成员的实现放在不同的文件里，因为很多很多编译器不支持export关键字，所以我也没用，当然主函数可以放在别的文件里。

Answer 2

/************用链表实现栈类Stack****************/
#include <iostream>
#include <cstdio>
using namespace std;
class Stack
{
public:
Stack() { top = NULL; }
~Stack()
{
while (top != NULL)
{
Node *p=top;
top = top->next;
delete p;
}
}
bool push(int i);
bool pop(int& i);
void clear();
private:
struct Node
{
int content;
Node *next;
} *top;
};
bool Stack::push(int i)
{
Node *p=new Node;
if (p == NULL)
{
cout << "Stack is overflow.\n";
return false;
}
else
{
p->content = i;
p->next = top;
top = p;
return true;
}
}
bool Stack::pop(int& i)
{
if (top == NULL)
{
cout << "Stack is empty.\n";
return false;
}
else
{
Node *p=top;
top = top->next;
i = p->content;
delete p;
return true;
}
}

void Stack::clear()
{
Node *p=top;
top = top->next;
delete p;
}
int main()//main()
{
Stack st; //自动地去调用st.Stack()对st进行初始化。
int x;
st.push(12); //把12放进栈st。
st.push(13);
st.clear();
st.push(1);
if(st.pop(x) == true) //把栈顶元素退栈并存入变量x。
{
cout << x << endl;
}
system("pause");
return 0;
}

Answer 3

#include <iostream>
using namespace std;

template<typename Type> class LinkStack;

template<typename Type>
class StackNode
{
private:
friend class LinkStack<Type>;
StackNode(const Type &d, StackNode<Type> *n = NULL):data(d), next(n) {}

Type data;
StackNode<Type> *next;
};

template<typename Type>
class LinkStack
{
public:
LinkStack():top(NULL) {}
~LinkStack()
{
Clear();
}

void Push(const Type &item);
bool Pop(Type &item);
void Clear();
void Print();

bool IsEmpty() const
{
return (top == NULL);
}

private:
StackNode<Type> *top;
};

template<typename Type>
void LinkStack<Type>::Push(const Type &item)
{
top = new StackNode<Type>(item, top);
}

template<typename Type>
bool LinkStack<Type>::Pop(Type &item)
{
if (IsEmpty())
{
cout << "Stack is Empty!" << endl;
return false;
}

StackNode<Type> *del = top;
top = top->next;
item = del->data;
delete del;
return true;
}

template<typename Type>
void LinkStack<Type>::Clear()
{
StackNode<Type> *next, *cursor = top;

while (cursor != NULL)
{
next = cursor->next;
delete cursor;
cursor = next;
}

top = NULL;
}

template<typename Type>
void LinkStack<Type>::Print()
{
StackNode<Type> *cursor = top;

while (cursor != NULL)
{
cout << cursor->data;
cursor = cursor->next;
}
}

int main()
{
LinkStack<int> stack;
int a[10] = {1,3,5,7,4,2,8,0,6,9};
int item;

for (int i = 0; i < 10; ++i)
{
stack.Push(a[i]);
}

stack.Print();
cout << endl;
stack.Pop(item);
cout << item << endl;
stack.Print();
cout << endl;
stack.Pop(item);
cout << item << endl;
stack.Print();
cout << endl;
stack.Clear();
stack.Print();
return 0;
}