链表 写队列和栈 练习代码

#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;
}

};

链表 写队列和栈 练习代码

原文：http://www.cnblogs.com/itdef/p/6374446.html