焦作做网站优化,wordpress redirect.php,网站域名被重定向,flash 源码网站文章目录 1、 栈与队列简介栈#xff08;Stack#xff09;队列#xff08;Queue#xff09; 2、使用链表实现栈C语言实现C#语言实现C语言实现 3、使用链表实现队列C语言实现C#语言实现C语言实现 4、链表实现栈和队列的性能分析时间复杂度空间复杂度性能特点与其他实现的比较… 文章目录 1、 栈与队列简介栈Stack队列Queue 2、使用链表实现栈C语言实现C#语言实现C语言实现 3、使用链表实现队列C语言实现C#语言实现C语言实现 4、链表实现栈和队列的性能分析时间复杂度空间复杂度性能特点与其他实现的比较 总结 在软件开发中数据结构是不可或缺的一部分。本文将详细介绍如何使用链表来实现栈和队列这两种基本的数据结构并提供C、C#和C三种语言的示例代码。
1、 栈与队列简介
栈Stack
栈是一种后进先出Last In First Out, LIFO的数据结构。栈的基本操作包括
push将元素压入栈顶。pop移除栈顶元素。peek查看栈顶元素。
队列Queue
队列是一种先进先出First In First Out, FIFO的数据结构。队列的基本操作包括
enqueue在队列尾部添加元素。dequeue移除队列头部元素。peek查看队列头部元素。
2、使用链表实现栈
链表是一种灵活的数据结构非常适合实现栈。
C语言实现
#include stdio.h
#include stdlib.htypedef struct Node {int data;struct Node* next;
} Node;typedef struct Stack {Node* top;
} Stack;void initStack(Stack* stack) {stack-top NULL;
}void push(Stack* stack, int data) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data data;newNode-next stack-top;stack-top newNode;
}int pop(Stack* stack) {if (stack-top NULL) {printf(栈为空\n);return -1;}Node* temp stack-top;int data temp-data;stack-top stack-top-next;free(temp);return data;
}int peek(Stack* stack) {if (stack-top NULL) {printf(栈为空\n);return -1;}return stack-top-data;
}void destroyStack(Stack* stack) {while (stack-top ! NULL) {Node* temp stack-top;stack-top stack-top-next;free(temp);}
}int main() {Stack stack;initStack(stack);push(stack, 1);push(stack, 2);push(stack, 3);printf(栈顶元素%d\n, peek(stack));printf(出栈元素%d\n, pop(stack));printf(出栈元素%d\n, pop(stack));destroyStack(stack);return 0;
}C#语言实现
using System;public class Node {public int Data { get; set; }public Node Next { get; set; }
}public class Stack {private Node top;public void Push(int data) {Node newNode new Node { Data data, Next top };top newNode;}public int Pop() {if (top null) {throw new InvalidOperationException(栈为空);}int data top.Data;top top.Next;return data;}public int Peek() {if (top null) {throw new InvalidOperationException(栈为空);}return top.Data;}
}class Program {static void Main() {Stack stack new Stack();stack.Push(1);stack.Push(2);stack.Push(3);Console.WriteLine(栈顶元素 stack.Peek());Console.WriteLine(出栈元素 stack.Pop());Console.WriteLine(出栈元素 stack.Pop());}
}C语言实现
#include iostreamstruct Node {int data;Node* next;
};class Stack {
public:Stack() : top(nullptr) {}~Stack() {while (top ! nullptr) {Node* temp top;top top-next;delete temp;}}void push(int data) {Node* newNode new Node{data, top};top newNode;}int pop() {if (top nullptr) {throw std::runtime_error(栈为空);}Node* temp top;int data temp-data;top top-next;delete temp;return data;}int peek() const {if (top nullptr) {throw std::runtime_error(栈为空);}return top-data;}private:Node* top;
};int main() {Stack stack;stack.push(1);stack.push(2);stack.push(3);std::cout 栈顶元素 stack.peek() std::endl;std::cout 出栈元素 stack.pop() std::endl;std::cout 出栈元素 stack.pop() std::endl;return 0;
}3、使用链表实现队列
队列是另一种常见的数据结构同样可以通过链表来实现。
C语言实现
#include stdio.h
#include stdlib.htypedef struct Node {int data;struct Node* next;
} Node;typedef struct Queue {Node* front;Node* rear;
} Queue;void initQueue(Queue* queue) {queue-front queue-rear NULL;
}void enqueue(Queue* queue, int data) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data data;newNode-next NULL;if (queue-rear NULL) {queue-front queue-rear newNode;} else {queue-rear-next newNode;queue-rear newNode;}
}int dequeue(Queue* queue) {if (queue-front NULL) {printf(队列为空\n);return -1;}Node* temp queue-front;int data temp-data;queue-front queue-front-next;if (queue-front NULL) {queue-rear NULL;}free(temp);return data;
}int peekQueue(Queue* queue) {if (queue-front NULL) {printf(队列为空\n);return -1;}return queue-front-data;
}void destroyQueue(Queue* queue) {while (queue-front ! NULL) {Node* temp queue-front;queue-front queue-front-next;free(temp);}queue-rear NULL;
}int main() {Queue queue;initQueue(queue);enqueue(queue, 1);enqueue(queue, 2);enqueue(queue, 3);printf(队首元素%d\n, peekQueue(queue));printf(出队元素%d\n, dequeue(queue));printf(出队元素%d\n, dequeue(queue));destroyQueue(queue);return 0;
}C#语言实现
using System;public class Node {public int Data { get; set; }public Node Next { get; set; }
}public class Queue {private Node front;private Node rear;public void Enqueue(int data) {Node newNode new Node { Data data };if (rear null) {front rear newNode;} else {rear.Next newNode;rear newNode;}}public int Dequeue() {if (front null) {throw new InvalidOperationException(队列为空);}int data front.Data;front front.Next;if (front null) {rear null;}return data;}public int Peek() {if (front null) {throw new InvalidOperationException(队列为空);}return front.Data;}
}class Program {static void Main() {Queue queue new Queue();queue.Enqueue(1);queue.Enqueue(2);queue.Enqueue(3);Console.WriteLine(队首元素 queue.Peek());Console.WriteLine(出队元素 queue.Dequeue());Console.WriteLine(出队元素 queue.Dequeue());}
}C语言实现
#include iostreamstruct Node {int data;Node* next;
};class Queue {
public:Queue() : front(nullptr), rear(nullptr) {}~Queue() {while (front ! nullptr) {Node* temp front;front front-next;delete temp;}}void enqueue(int data) {Node* newNode new Node{data, nullptr};if (rear nullptr) {front rear newNode;} else {rear-next newNode;rear newNode;}}int dequeue() {if (front nullptr) {throw std::runtime_error(队列为空);}Node* temp front;int data temp-data;front front-next;if (front nullptr) {rear nullptr;}delete temp;return data;}int peek() const {if (front nullptr) {throw std::runtime_error(队列为空);}return front-data;}private:Node* front;Node* rear;
};int main() {Queue queue;queue.enqueue(1);queue.enqueue(2);queue.enqueue(3);std::cout 队首元素 queue.peek() std::endl;std::cout 出队元素 queue.dequeue() std::endl;std::cout 出队元素 queue.dequeue() std::endl;return 0;
}4、链表实现栈和队列的性能分析
时间复杂度
栈Stack
push入栈操作O(1)
在链表实现的栈中每次入栈操作只需要在链表头部插入一个新节点这是一个常数时间操作。
pop出栈操作O(1)
出栈操作涉及移除链表头部的节点这同样是一个常数时间操作。
peek查看栈顶元素操作O(1)
查看栈顶元素只需要返回链表头部的节点值不需要遍历链表。
队列Queue
enqueue入队操作O(1)
在链表实现的队列中每次入队操作通常在链表尾部插入一个新节点这也是一个常数时间操作。
dequeue出队操作O(1)
出队操作涉及移除链表头部的节点在链表实现的队列中通常需要保持一个指向链表尾部的指针以便于在尾部进行插入操作。为了使出队操作达到O(1)我们可以使用双端链表或两个指针分别指向头部和尾部这样出队时只需要更新头部指针。
peek查看队首元素操作O(1)
与栈类似查看队首元素只需要返回链表头部的节点值。
空间复杂度
栈和队列O(n)
链表实现栈和队列的空间复杂度是线性的其中n是栈或队列中元素的数量。每个元素都需要一个节点来存储。
性能特点
动态大小链表实现的栈和队列可以根据需要动态地增长和收缩不需要预先分配固定大小的存储空间。无内存碎片与数组实现相比链表实现不会产生内存碎片因为它们通过指针连接不需要连续的内存空间。插入和删除效率链表的插入和删除操作不需要移动其他元素只需改变指针因此效率较高。内存开销链表实现需要额外的内存来存储节点间的指针这可能比数组实现需要更多的内存。
与其他实现的比较
与数组实现的栈和队列比较
数组实现的栈和队列在内存使用上可能更高效因为它们不需要额外的指针字段。数组实现的栈和队列可能需要预先分配固定大小的空间这可能导致空间浪费或需要动态扩容而链表实现则可以更加灵活地处理大小变化。
与平衡二叉搜索树如AVL树、红黑树实现的栈和队列比较
使用平衡二叉搜索树实现的栈和队列在理论上可以达到O(log n)的时间复杂度但是这在实际中很少见因为这种实现过于复杂且在实践中不太必要。
总的来说链表实现的栈和队列在大多数情况下提供了良好的性能尤其是在元素数量变化较大或者内存使用需要优化时。然而具体选择哪种实现方式还需要根据实际应用场景和性能需求来决定。
总结
本文通过C、C#和C三种不同的编程语言详细介绍了如何使用链表来实现栈和队列这两种基本的数据结构。每种实现都包括了初始化、添加元素、移除元素、查看顶部元素和销毁数据结构的完整操作。
链表由于其灵活性和动态性是实现栈和队列的理想选择。通过本文的示例我们可以看到虽然不同的语言在语法和细节上有所不同但核心概念和实现逻辑是相似的。
在实际应用中理解这些数据结构的实现对于编写高效和可靠的应用程序至关重要。无论是进行算法设计、数据处理还是系统开发掌握栈和队列的实现都是每个程序员的基本技能。
