#pragma once
#include "MyLink.h"
template<typename T>
class MyStack {
MyLink<T> lk;
MyStack& operator=(const MyStack&);
MyStack(const MyStack&);
public:
MyStack(){}
size_t StackGetSize() { return lk.GetSize(); }
bool StackPushBack(const T& e) { return lk.AppendElement(e); }
bool StackPopBack() { return lk.DeleteTail(); }
T StackGetTop() { return lk.GetTail(); }
bool StackEmpty() { return GetSize() == 0; }
void StackPrint() { lk.PrintLinkList(); }
};
//===========================
#pragma once
#include "MyLink.h"
template<typename T>
class MyQueue {
MyLink<T> lk;
MyQueue& operator=(const MyQueue&);
MyQueue(const MyQueue&);
public:
MyQueue() {}
size_t QueueGetSize() { return lk.GetSize(); }
bool QueuePushBack(const T& e) { return lk.AppendElement(e); }
bool QueuePopFront() { return lk.DeleteHead(); }
T QueueGetHead() { return lk.GetHead(); }
T QueueGetTail() { return lk.GetTail(); }
bool QueueEmpty() { return GetSize() == 0; }
void QueuePrint() { lk.PrintLinkList(); }
};
//==================================
#pragma once
#include <memory>
#include <iostream>
template <typename T>
class MyLink {
struct LinkNode {
T val;
std::shared_ptr<LinkNode> next;
};
size_t linkSize_;
std::shared_ptr<LinkNode> begin_;
std::shared_ptr<LinkNode> end_;
MyLink& operator=(const MyLink&);
MyLink(const MyLink&);
public:
MyLink():begin_(nullptr),end_(nullptr), linkSize_(0){}
size_t GetSize() { return linkSize_; }
T GetHead() { return begin_->val; }
T GetTail() { return end_->val; }
bool AppendElement(const T& e) {
bool ret = false;
std::shared_ptr<LinkNode> node(new LinkNode);
if (node == nullptr)
return ret;
node->val = e;
node->next = nullptr;
if (nullptr == end_ || nullptr == begin_) {
begin_ = end_ = node;
linkSize_++;
ret = true;
return ret;
}
end_->next = node;
end_ = node;
linkSize_++;
ret = true;
return ret;
}
bool DeleteTail() {
bool ret = false;
// 无元素 或者 仅有一个元素情况
if (begin_ == end_) {
if (end_ != nullptr) {
linkSize_--;
}
begin_ = end_ = nullptr;
ret = true;
return ret;
}
std::shared_ptr<LinkNode> p = begin_;
while (p->next != nullptr) {
if (p->next == end_) {
end_ = p;
p->next = nullptr;
linkSize_--;
ret = true;
return ret;
}
p = p->next;
}
return ret;
}
bool DeleteHead() {
bool ret = false;
// 无元素 或者 仅有一个元素情况
if (begin_ == end_) {
if (begin_ != nullptr) {
linkSize_--;
}
begin_ = end_ = nullptr;
ret = true;
return ret;
}
begin_ = begin_->next;
linkSize_--;
ret = true;
return ret;
}
void PrintLinkList() {
std::shared_ptr<LinkNode> p = begin_;
std::cout << "print linklist: " << std::endl;
while (p != nullptr) {
std::cout << p->val << " ";
p = p->next;
}
std::cout << std::endl;
std::cout << "link size is " << linkSize_ << std::endl;
std::cout << std::endl<< std::endl;
}
};