链表：
#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include <stdexcept>
using namespace std;
template<typename T>
class Node {
public:
T element;
Node<T> *next;
Node() {
next = NULL;
}
Node(T element) {
this->element = element;
next = NULL;
}
};
//----------------- Iterator -----------------
template<typename T>
class Iterator {
public:
Iterator(Node<T> *p) {
current = p;
}
Iterator &operator++() {
current = current->next;
return *this;
}
Iterator &operator++(int) {
return ++(*this);
}
T operator*() {
return current->element;
}
bool operator==(const Iterator<T> &iterator) {
return current == iterator.current;
}
bool operator!=(const Iterator<T> &iterator) {
return current != iterator.current;
}
private:
Node<T> *current;
};
//----------------- Iterator -----------------
template<typename T>
class LinkedList {
public:
LinkedList();
void addFirst(T element);
void addLast(T element);
T getFirst();
T getLast();
T get(int index);
T removeFirst() throw (runtime_error);
T removeLast() throw (runtime_error);
void add(T element);
void add(int index, T element);
void remove(T element);
T removeAt(int index) throw (runtime_error);
void clear();
int getSize();
bool isEmpty();
//----------------- Iterator -----------------
Iterator<T> begin();
Iterator<T> end();
//----------------- Iterator -----------------
private:
Node<T> *head, *tail;
int size;
};
template<typename T>
LinkedList<T>::LinkedList() {
size = 0;
head = tail = NULL;
}
template<typename T>
void LinkedList<T>::addFirst(T element) {
Node<T> *newNode = new Node<T> (element);
newNode->next = head;
head = newNode;
size++;
if (tail == NULL)
tail = head;
}
template<typename T>
void LinkedList<T>::addLast(T element) {
if (tail == NULL)
tail = head = new Node<T> (element);
else {
tail->next = new Node<T> (element);
tail = tail->next;
}
size++;
}
template<typename T>
T LinkedList<T>::getFirst() {
if (size == 0)
throw runtime_error("Index out of range.");
return head->element;
}
template<typename T>
T LinkedList<T>::getLast() {
if (size == 0)
throw runtime_error("Index out of range.");
return tail->element;
}
template<typename T>
T LinkedList<T>::get(int index) {
if (index < 0 || index > (size - 1))
throw runtime_error("Index out of range.");
else if (index == 0)
return getFirst();
else if (index == (size - 1))
return getLast();
else {
Node<T> *current = head;
for (int i = 0; i < index; i++)
current = current->next;
return current->element;
}
}
template<typename T>
T LinkedList<T>::removeFirst() throw (runtime_error) {
if (size == 0)
throw runtime_error("No elements in the list.");
Node<T> *temp = head;
head = head->next;
if (head == NULL)
tail = NULL;
size--;
T element = temp->element;
delete temp;
return element;
}
template<typename T>
T LinkedList<T>::removeLast() throw (runtime_error) {
if (size == 0)
throw runtime_error("No elements in the list.");
else if (size == 1) {
Node<T> *temp = head;
head = tail = NULL;
size = 0;
T element = temp->element;
delete temp;
return element;
} else {
Node<T> *current = head;
for (int i = 0; i < size - 2; i++)
current = current->next;
Node<T> *temp = tail;
tail = current;
tail->next = NULL;
size--;
T element = temp->element;
delete temp;
return element;
}
}
template<typename T>
void LinkedList<T>::add(T element) {
addLast(element);
}
template<typename T>
void LinkedList<T>::add(int index, T element) {
if (index == 0)
addFirst(element);
else if (index >= size)
addLast(element);
else {
Node<T> *current = head;
for (int i = 1; i < index; i++)
current = current->next;
Node<T> *temp = current->next;
current->next = new Node<T> (element);
(current->next)->next = temp;
size++;
}
}
template<typename T>
void LinkedList<T>::remove(T element) {
}
template<typename T>
T LinkedList<T>::removeAt(int index) throw (runtime_error) {
if (index < 0 || index > (size - 1))
throw runtime_error("Index out of range.");
else if (index == 0)
return removeFirst();
else if (index == (size - 1))
return removeLast();
else {
Node<T> *previous = head;
for (int i = 1; i < index; i++)
previous = previous->next;
Node<T> *current = previous->next;
previous->next = current->next;
size--;
T element = current->element;
delete current;
return element;
}
}
template<typename T>
void LinkedList<T>::clear() {
while (head != NULL) {
Node<T> *temp = head;
delete temp;
head = head->next;
}
tail = NULL;
}
template<typename T>
int LinkedList<T>::getSize() {
return size;
}
template<typename T>
bool LinkedList<T>::isEmpty() {
return head == NULL;
}
//----------------- Iterator -----------------
template<typename T>
Iterator<T> LinkedList<T>::begin() {
return Iterator<T> (head);
}
template<typename T>
Iterator<T> LinkedList<T>::end() {
return Iterator<T> (tail->next);
}
//----------------- Iterator -----------------
#endif /* LINKEDLIST_H_ */
栈：
#ifndef STACKWITHLINKEDLIST_H_
#define STACKWITHLINKEDLIST_H_
#include "LinkedList.h"
template<typename T = int>
class Stack {
public:
Stack();
bool isEmpty();
T peek();
void push(T value);
T pop();
int getSize();
private:
LinkedList<T> list;
};
template<typename T>
Stack<T>::Stack() {
}
template<typename T>
bool Stack<T>::isEmpty() {
return list.isEmpty();
}
template<typename T>
T Stack<T>::peek() {
return list.getLast();
}
template<typename T>
void Stack<T>::push(T value) {
list.addLast(value);
}
template<typename T>
T Stack<T>::pop() {
return list.removeLast();
}
template<typename T>
int Stack<T>::getSize() {
return list.getSize();
}
#endif /* STACKWITHLINKEDLIST_H_ */
队列：
#ifndef QUEUE_H_
#define QUEUE_H_
#include "LinkedList.h"
using namespace std;
template<typename T>
class Queue {
public:
Queue();
void enqueue(T element);
T dequeue() throw (runtime_error);
int getSize();
private:
LinkedList<T> list;
};
template<typename T>
Queue<T>::Queue() {
}
template<typename T>
void Queue<T>::enqueue(T element) {
list.addLast(element);
}
template<typename T>
T Queue<T>::dequeue() throw (runtime_error) {
return list.removeFirst();
}
template<typename T>
int Queue<T>::getSize() {
return list.getSize();
}
#endif /* QUEUE_H_ */
分享到：
相关推荐
链表分为单向链表和双向链表。在单向链表中，节点只能向前遍历；而在双向链表中，节点可以向前也可以向后遍历。C语言中，链表通常通过定义结构体来实现： ```c typedef struct Node { int data; struct Node* ...
在某些场景下，链表栈和链表队列相比数组实现的栈和队列，能更好地处理动态变化的大小需求。 在实际编程中，我们可能需要对这些数据结构进行优化，例如，循环链表可以避免空指针问题，提高效率；链表栈和链表队列...
链表有多种类型，如单向链表、双向链表和循环链表。在单向链表中，每个节点只能向前指向一个节点；双向链表则允许节点同时向前和向后指；循环链表的最后一个节点会指向列表的第一个节点，形成一个环。链表的主要操作...
链表分为单向链表、双向链表和循环链表等类型，本程序可能使用的是单向链表，因为队列和栈通常只需要头尾操作，不需要双向访问。 队列是一种先进先出（FIFO，First In First Out）的数据结构，类似于现实生活中的...
单向链表只能按顺序访问，而双向链表支持前向和后向遍历。链表的优点在于可以灵活地添加和删除元素，但访问速度较慢，因为需要遍历到目标位置。 3. **栈**（Stack）：栈是一种“后进先出”（LIFO）的数据结构。它的...
单向链表只能向前遍历，而双向链表则可以向前或向后遍历。链表的主要操作包括插入、删除和查找。在C语言中，通过指针操作来实现链表的这些操作，这在动态内存分配和数据存储上提供了很大的灵活性。 接下来是队列，...
单向链表常用于实现数据结构如栈和队列，缓存管理，以及当频繁的插入和删除操作远多于查找操作时的情况。 总结，C#中的单向链表通过`LinkedList<T>`类提供了丰富的操作，同时也可以通过自定义节点和链表类理解其...
该队列的主要特点是其内部数据结构采用了一个单向链表，并且实现了 BlockingQueue 接口，提供了线程安全的插入、删除和获取元素的操作。 单向链表是一种简单的数据结构，由一系列节点组成，每个节点包含数据以及...
链表分为单向链表、双向链表和循环链表等类型。在List.cpp文件中，可能包含了链表的创建、插入、删除、遍历等操作的实现。例如，你可以找到关于头插法、尾插法、查找特定节点以及反转链表的C++代码。 栈是一种后进...
链表分为单向链表、双向链表和循环链表等类型。链表的主要操作有插入、删除和遍历。链表在处理动态数据集合时特别有用，因为它们不需要预先确定大小，且插入和删除操作通常比数组快。 然后是队列（Queue），它是...
单向链表在各种数据结构（如栈、队列、哈希表）以及算法（如LRU缓存淘汰策略）中都有应用。例如，链表可以用来实现动态分配内存的内存池，或者作为操作系统中的进程控制块链表。 总结，单向链表是数据结构的基础，...
在Python中，我们可以自定义链表结构来实现单向链表和双向链表。 单向链表（Single Linked List）的特点是每个节点只包含一个指向下一个节点的引用。在单向链表中，遍历只能从头节点开始，按顺序访问每个节点，无法...
数据结构与算法的学习：_稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、_dataStructuresAndAlgorithm
顺序表、链表、栈、队列、树、Hashmap等数据结构；排序、二分法查找、树遍历等常见算法实现...单向链表 双向链表 单向循环链表 栈 队列 FIFO队列 LIFO队列 优先队列（Priority Queue） 双端队列（double-ended queue）
链表分为单向链表、双向链表和循环链表。单向链表只能向前遍历，而双向链表支持前向和后向遍历。链表的主要操作包括插入、删除和遍历。 2. **队列**：队列是一种先进先出（FIFO）的数据结构，类似于现实生活中的...
链表分为单向链表、双向链表和循环链表等类型，它们各有优缺点，如单向链表插入和删除操作相对简便，但访问元素不如数组直接。 栈是一种后进先出（LIFO）的数据结构，常被比喻为一个堆叠的盘子。栈的操作主要包括压...
在实际应用中，单向链表常用于实现各种数据结构，如队列（先进先出，FIFO）、栈（后进先出，LIFO）和关联数组（哈希表）。单向链表还常常作为其他复杂数据结构的基础，例如双向链表、循环链表等。 在“数据结构实验...
在实际编程中，链表还可以用于实现各种高级数据结构，如栈、队列和图等。同时，链表的操作如删除节点、查找节点、反转链表等也是面试和编程竞赛中常见的问题。理解和熟练掌握链表的这些基本操作对于提升编程技能至关...
假定一个单向循环链表来表示队列