C++栈的顺序存储和链式存储的实现数据结构和算法

【C++栈的顺序存储和链式存储的实现】栈是最常见的数据结构，其特点是后进先出（Last In First Out)也是链表的特殊形式，所以和链表一样，有两种存储方式，第一是顺序存储的栈，方便快速读写数据，但是栈的长度必须先固定；第二种是链式存储的栈，可以不用定义栈的长度，可以大量插入数据，如果不是物理内存使用完的话，可以存储大量的数据。
首先，顺序存储的栈的实现，代码如下：

#pragma once #define MAXSIZE 10 template class OrderStack {public: OrderStack(); ~OrderStack(); bool GetTop(EleType& e); bool Push(const EleType& e); bool Pop(EleType& e); void Show()const; private: EleType data[MAXSIZE]; int top; bool Empty()const; bool Full()const; int StackLength()const; };

#include "OrderStack.h" #include using namespace std; template bool OrderStack::Pop(EleType& e) { if (Empty()) { cout << "The stack is empty!\n"; return false; } e = data[top]; --top; return true; }template bool OrderStack::Push(const EleType& e) { if (Full()) { return false; } ++top; data[top] = e; return true; }template bool OrderStack::GetTop(EleType& e) { if (Empty()) { return false; } e = data[top]; return true; }template OrderStack::~OrderStack() {}template OrderStack::OrderStack() :top(-1) {}template int OrderStack::StackLength() const { return top + 1; }template bool OrderStack::Full() const { return (top == MAXSIZE - 1); }template bool OrderStack::Empty() const { return (top == -1); }template void OrderStack::Show() const { if (Empty()) { cout << "The stack is Empty!\n"; return; } cout << "The stack length is: " << StackLength() << endl; cout << "The stack is: "; for (int i = top; i >= 0; --i) { cout << data[i] << " "; } cout << endl; }

第二，栈的链式存储，代码如下：

#pragma once template class ChainStack { public: ChainStack(); ~ChainStack(); bool GetTop(EleType& e); bool Push(const EleType& e); bool Pop(EleType& e); void Show()const; private: bool Empty()const; //bool Full()const; int StackLength()const; struct Node { EleType data; Node* next; Node(){ next = nullptr; } }; Node* top; int length; };

#include "ChainStack.h" #include using namespace std; template int ChainStack::StackLength() const { return length; }// template // bool ChainStack::Full() const // { // // }template bool ChainStack::Empty() const { return (length == 0); }template void ChainStack::Show() const { if (Empty()) { cout << "The stack is empty!\n"; return; } cout << "The stack length is " << length << endl; cout << "The stack is "; Node* temp=top; for (int i = 1; i <= length; ++i) { cout << temp->data << " "; temp = temp->next; } cout << endl; }template bool ChainStack::Pop(EleType& e) { if (Empty()) { cout << "The stack is empty!\n"; return false; } e = top->data; Node* temp = top; top = top->next; --length; delete temp; return true; }template bool ChainStack::Push(const EleType& e) { Node* temp = new Node; temp->data = https://www.it610.com/article/e; if (Empty()) { top = temp; } else { temp->next = top; top = temp; } ++length; return true; }template bool ChainStack::GetTop(EleType& e) { if (Empty()) { cout << "The stack is empty!\n"; return false; } e = top->data; return true; }template ChainStack::~ChainStack() { Node* temp = top; while (top) { temp = top; top = temp->next; delete temp; }}template ChainStack::ChainStack() :length(0), top(nullptr) {}