栈与队列的介绍,以及与数组实现的对比见:Data Structures in C++:栈和队列的数组实现

链式栈

链式栈通过单链表来实现:每次入栈一个元素,就向链表中添加一个节点;出栈一个元素,就释放一个节点,不存在溢出问题。因为栈具有“先进后出”的特点,栈顶指针top一直指向栈顶元素,而链表的头指针一直指向哑结点,因此在头部进行push和pop时,可以避免遍历操作。

  • 创建空链表,只包含哑结点,并设栈顶指针指示栈顶结点,即first->next;
  • 入栈操作push :新增结点node,重新链接栈顶 node->next = first->next; first->next= node;
  • 出栈操作pop:暂存结点,重新链接栈顶 first->next = first->next->next;,删除结点
  • 空栈:first->next == nullptr

链式栈的定义:

template <typename T>
class LinkedStack
{
public:
    LinkedStack();
    ~LinkedStack();
    T top();
    void push(T);
    void pop();
    bool empty();

private:
    Node<T>* first;     // top node 即 first->next
};

链式栈的实现:

template<typename T>
inline LinkedStack<T>::LinkedStack()
{
    Node<T>* node = new Node<T>;
    node->next = nullptr;
    first = node;
}

template<typename T>
inline LinkedStack<T>::~LinkedStack()
{
}

template<typename T>
inline T LinkedStack<T>::top()
{
    if (empty()) throw std::string("Stack is empty!");
    return first->next->data;
}

template<typename T>
inline void LinkedStack<T>::push(T _data)
{
    Node<T>* node = new Node<T>;
    node->data = _data;
    node->next = first->next;
    first->next = node;
}

template<typename T>
inline void LinkedStack<T>::pop()
{
    Node<T>* node = first->next;
    first->next = first->next->next;
    delete node;
}

template<typename T>
inline bool LinkedStack<T>::empty()
{
    return first->next == nullptr;
}

测试代码:

#include "LinkedStack.h"
#include <iostream>

using namespace std;

int main()
{
    LinkedStack<int> mystack;
    cout << "入栈:" << endl;
    mystack.push(0); cout << mystack.top() << endl;
    mystack.push(1); cout << mystack.top() << endl;
    mystack.push(2); cout << mystack.top() << endl;
    mystack.push(3); cout << mystack.top() << endl;
    try
    {
	    cout << "\n出栈:" << endl;
	    mystack.pop(); cout << "after pop, top = " << mystack.top() << endl;
	    mystack.pop(); cout << "after pop, top = " << mystack.top() << endl;
	    mystack.pop(); cout << "after pop, top = " << mystack.top() << endl;
	    mystack.pop(); cout << "after pop, top = " << mystack.top() << endl;
    }
    catch (string e)
    {
        cout << "\nERROR: " << e << endl;
    }

    return 0;
}


链式队列

  • 创建空链表,只包含哑结点,并设 队首指针 front 指示队首结点前的哑结点;设 队尾指针 rear 指示队尾结点。
  • 入队操作push :新增结点node;重新链接队尾 node->next = nullptr; rear->next= node; 更新队尾指针rear = node;
  • 出队操作pop:暂存队首结点;重新链接队首 front->next = front->next->next; 删除结点;注意 尾结点出队 时的特殊情况:if (front->next == nullptr) rear = front;
  • 队列为空:front == rear

链式队列的声明:

template <typename T>
class LinkedQueue
{
public:
    LinkedQueue();
    ~LinkedQueue();
    void push(T);
    void pop();
    bool empty() const;
    T get_front() const;
    T get_rear() const;

private:
    Node<T>* front;
    Node<T>* rear;
};

链式队列的实现:

template<typename T>
inline LinkedQueue<T>::LinkedQueue()
{
    Node<T>* node = new Node<T>;
    node->next = nullptr;
    front = rear = node;
}

template<typename T>
inline LinkedQueue<T>::~LinkedQueue()
{
}

template<typename T>
inline void LinkedQueue<T>::push(T _data)
{
    Node<T>* node = new Node<T>;
    node->data = _data;
    node->next = nullptr;
    rear->next = node;
    rear = node;
}

template<typename T>
inline void LinkedQueue<T>::pop()
{
    if (empty()) throw std::string("Queue is empty!");
    Node<T>* node = front->next;
    front->next = node->next;
    delete node;
    if (front->next == nullptr) rear = front;
}

template<typename T>
inline bool LinkedQueue<T>::empty() const
{
    return front == rear;
}

template<typename T>
inline T LinkedQueue<T>::get_front() const
{
    if (empty()) throw std::string("Queue is empty!");
    return front->next->data;
}

template<typename T>
inline T LinkedQueue<T>::get_rear() const
{
    if (empty()) throw std::string("Queue is empty!");
    return rear->data;
}