栈的链式存储结构之C++实现
链式栈是线性表的链接存储表示，采用链式栈来表示一个栈，便于结点的插入与删除。在程序中同时使用多个栈的情况下，用链式表示不仅能提高效率，还可以达到共享存储空间的目的。
#ifndef STACK_H_INCLUDED #define STACK_H_INCLUDED #include <bits/stdc++.h> const int maxSize = 284; template<class T> class Stack { public: Stack() {std::cout << "Defalut Stack Constructing" << std::endl;} ~Stack() {std::cout << "Destructing Stack"<< std::endl;} virtual void Push(const T& x) = 0;; virtual bool Pop(T& x) = 0; virtual bool GetTop(T& x)const = 0; virtual bool IsEmpty()const = 0; virtual bool IsFull()const = 0; virtual int GetSize()const = 0; }; #endif // STACK_H_INCLUDED #ifndef LinkedListEDLIST_H_INCLUDED #define LinkedListEDLIST_H_INCLUDED #include <bits/stdc++.h> using namespace std; template<class T> class LinkNode { public: LinkNode(LinkNode<T>* ptr = NULL) {cout << "Constructing a LinkNode by default way!" << endl; link = ptr;} LinkNode(const T& item, LinkNode<T>* ptr = NULL) {cout << "Constructing a LinkNode by defined way!" << endl; data = item, link = ptr;} ~LinkNode() {cout << "Desctructing a LineNode!" << endl; delete link;} T data; // Data Scope LinkNode<T> *link; // Point Scope, Point to next Node }; // LinkedListList with head node template <class T> class LinkedList : public LinkNode<T> { public: LinkedList() {cout << "Constructing a LinkedListList by default way" << endl; first = new LinkNode<T>;} LinkedList(const T&x); LinkedList(LinkedList<T>& L); // Deep copy constructor function ~LinkedList() {cout << "Destructing a LinkedListNode by default way" << endl; delete first;} void makeEmpty(); // Delete all nodes in the LinkedList int Length() const; // Get the length of the SinlyLinkedList LinkNode<T> *GetHead() const {return first;} // Return first LinkNode<T> *Search(T x); // x can only be a variable while T& x LinkNode<T> *Locate(int i); // Get the i-th node's address bool GetData(int i, T& x); // Get the data in i-th node and let x = data void SetData(int i, T& x); // Make the data in i-th node equals x bool Insert(int i, T& x); // Insert a node in i-th with its' data be x bool Remove(int i, T& x); // Delete the i-th node and make x = node[i]->data bool IsEmpty() const {return first->link == NULL ? true : false;} bool IsFull() const {return false;} void Sort(); // Sort all datas in the LinkedList by non-decreasing way void Input(); // Input all elements void Output(); // Out all elements LinkedList<T>& operator=(LinkedList<T>& L); // Overloading operator = protected: LinkNode<T> *first; // Point to Head node }; #endif // LinkedListEDLIST_H_INCLUDED #ifndef LINKEDSTACK_H_INCLUDED #define LINKEDSTACK_H_INCLUDED #include "stack.h" #include "LinkedList.h" #include <bits/stdc++.h> template<class T> class LinkedStack : public Stack<T>{ public: LinkedStack() : top(NULL) {cout << "Constructing LinkedStack" << endl;} ~LinkedStack() {MakeEmpty();cout << "Destructing LinkedStack" << endl;} void Push(const T& x); bool Pop(T& x); bool GetTop(T& x)const; bool IsEmpty()const {return top == NULL ? true : false;} bool IsFull()const {return GetSize() == maxSize ? true : false;}; int GetSize()const; // Declaration must be exactly same except virtual void MakeEmpty(); //friend ostream& operator<<(ostream& os, LinkedStack<T>& s); private: LinkNode<T> *top; }; template<class T> void LinkedStack<T>::Push(const T& x) { top = new LinkNode<T>(x, top); assert(top != NULL); // Create a new node and quit if top == NULL } template<class T> bool LinkedStack<T>::Pop(T& x) { if(IsEmpty() == true) { cerr << "No more elements to pop" << endl; return false; } LinkNode<T> *ptr = top; top = top->link; x = ptr->data; delete ptr; return true; } template<class T> bool LinkedStack<T>::GetTop(T& x)const { if(IsEmpty() == true) { cerr << "No elements in the stack now" << endl; return false; } x = top->data; return true; } template<class T> int LinkedStack<T>::GetSize()const { int cnt = 0; LinkNode<T> *cur = top; while(cur != NULL) { cnt++; cur = cur->link; } return cnt; } template<class T> void LinkedStack<T>::MakeEmpty() { if(IsEmpty()) return ; LinkNode<T> *cur = top; while(top != NULL) { top = top->link; delete cur; cur = top; } return ; } #endif // LINKEDSTACK_H_INCLUDED #include <iostream> #include "LinkedStack.h" using namespace std; int main() { LinkedStack<int> s; s.Push(284); s.Push(220); cout << s.GetSize() << endl; int topEle; if(s.GetTop(topEle)) { cout << topEle << endl; } s.Pop(topEle); cout << topEle << endl; cout << s.GetSize() << endl; s.Push(7); s.MakeEmpty(); cout << s.GetSize() << endl; return 0; }