重生之数据结构与算法----队列&栈

呼延含玉 · 2025-6-4 22:21:18

简介

上文说到，数据结构只有两种。其它的数据结构都是它的整花活。

栈
栈只能在表的一端（称为栈顶）进行插入和删除操作，遵循 “后进先出”（Last In First Out，LIFO）的原则。就像生活中的一摞盘子，最后放上去的盘子会最先被拿走
队列
它只允许在表的一端进行插入操作（队尾），在另一端进行删除操作（队头），遵循 “先进先出”（First In First Out，FIFO）的原则。类似于生活中排队买票，先排队的人先买到票离开队列。

用链表实现stack

public class MyLinkedStack<T>()
{
public static void Run()
{
var stack = new MyLinkedStack<string>();
stack.Push("aaaa");
stack.Push("bbbb");
stack.Push("cccc");
stack.Push("dddd");
while (stack.Count > 0)
{
Console.WriteLine(stack.Pop());
}
}
private LinkedList<T> _linked = new LinkedList<T>();
/// <summary>
/// 入栈
/// O(1)
/// </summary>
/// <param name="item"></param>
public void Push(T item)
{
_linked.AddFirst(item);
}
/// <summary>
/// 出栈
/// O(1)
/// </summary>
/// <returns></returns>
public T Pop()
{
var first = _linked.First;
_linked.RemoveFirst();
return first.Value;
}
/// <summary>
/// 查看栈顶
/// </summary>
/// O(1)
/// <returns></returns>
public T Peek()
{
return _linked.First.Value;
}
public int Count { get { return _linked.Count; } }
}

复制代码

用链表实现queue

public class MyLinkedQueue<T>
{
public static void Run()
{
var queue = new MyLinkedQueue<string>();
queue.Enqueue("aaa");
queue.Enqueue("bbb");
queue.Enqueue("ccc");
queue.Enqueue("ddd");
while (queue.Count > 0)
{
Console.WriteLine(queue.Dequeue());
}
}
private LinkedList<T> _linked = new LinkedList<T>();
/// <summary>
/// 入列
/// </summary>
/// <param name="item"></param>
public void Enqueue(T item)
{
_linked.AddFirst(item);
}
/// <summary>
/// 出列
/// </summary>
/// <returns></returns>
public T Dequeue()
{
var last= _linked.Last;
_linked.RemoveLast();
return last.Value;
}
/// <summary>
/// 查看队列顶
/// </summary>
/// <returns></returns>
public T Peek()
{
return _linked.First.Value;
}
public int Count { get { return _linked.Count; } }
}

复制代码

用数组实现stack

public class MyArrayStack<T>()
{
public static void Run()
{
var stack = new MyLinkedStack<string>();
stack.Push("aaaa");
stack.Push("bbbb");
stack.Push("cccc");
stack.Push("dddd");
while (stack.Count > 0)
{
Console.WriteLine(stack.Pop());
}
}
private List<T> _list=new List<T>();
/// <summary>
/// 入栈
/// O(1)
/// </summary>
/// <param name="item"></param>
public void Push(T item)
{
_list.Add(item);
}
/// <summary>
/// 出栈
/// O(1)
/// </summary>
/// <returns></returns>
public T Pop()
{
var v = _list[_list.Count - 1];
_list.RemoveAt(_list.Count - 1);
return v;
}
/// <summary>
/// 查看栈顶
/// </summary>
/// O(1)
/// <returns></returns>
public T Peek()
{
return _list[_list.Count - 1];
}
public int Count { get { return _list.Count; } }
}

复制代码

用数组实现queue

由于queue先进先出的特性，list头部增删元素的复杂度是O(N),不符合性能要求，我们可以使用前文介绍的环形数组，来实现list头部增删的O(1)

public class MyArrayQueue<T>
{
public static void Run()
{
var queue = new MyArrayQueue<string>();
queue.Push("aaaa");
queue.Push("bbbb");
queue.Push("cccc");
queue.Push("dddd");
while (queue.Count > 0)
{
Console.WriteLine(queue.Pop());
}
}
private CircularArray<T> _list = new CircularArray<T>();
/// <summary>
/// 入栈
/// O(1)
/// </summary>
/// <param name="item"></param>
public void Push(T item)
{
_list.AddFirst(item);
}
/// <summary>
/// 出栈
/// O(1)
/// </summary>
/// <returns></returns>
public T Pop()
{
var v = _list.GetLast();
_list.RemoveLast();
return v;
}
/// <summary>
/// 查看栈顶
/// </summary>
/// O(1)
/// <returns></returns>
public T Peek()
{
return _list.GetFirst();
}
public int Count { get { return _list.Count; } }
}

复制代码

队列的变种：双端队列

所谓双端队列，主要是比普通队列，多一个出入口,可以从队列的两头进行插入，删除。但也破坏了先进先出的原则。
日常场景使用不多。只有 Python用得多一些，因为Python标准库没有提供内置的栈和队列，一般会用双端队列来模拟标准队列。

public interface IMyQueue<T>
{
/// <summary>
/// 从头入列
/// </summary>
/// <param name="item"></param>
void EnqueueFirst(T item);
/// <summary>
/// 从头出列
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
T DequeueFirst(T item);
/// <summary>
/// 从尾入列
/// </summary>
void EnqueueLast();
/// <summary>
/// 从头出列
/// </summary>
/// <returns></returns>
T DequeueLast();
}

复制代码

实现比较简单，不再重复，参考普通队列思路即可。链表/环形数组均可实现。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

轩辕娅童 · 2025-10-17 13:54:53

很好很强大我过来先占个楼待编辑

段干叶农 · 2025-10-24 00:44:49

感谢分享

赘暨逢 · 2025-11-10 12:23:29

鼓励转贴优秀软件安全工具和文档！

晌集涟 · 2025-12-9 18:08:10

用心讨论，共获提升！

师悠逸 · 2025-12-10 13:52:16

新版吗？好像是停更了吧。

石娅凉 · 2025-12-28 20:37:07

热心回复！

战匈琼 · 2026-1-19 02:48:26

热心回复！

科元料 · 2026-1-19 11:37:17

热心回复！

凳舒 · 2026-1-20 16:12:43

东西不错很实用谢谢分享

晁红叶 · 2026-1-23 04:20:14

很好很强大我过来先占个楼待编辑

刃减胸 · 2026-1-26 05:18:56

东西不错很实用谢谢分享

章海 · 2026-2-5 09:09:08

鼓励转贴优秀软件安全工具和文档！

迫蔺 · 2026-2-8 07:48:55

热心回复！

时思美 · 2026-2-8 11:49:29

用心讨论，共获提升！

卢莹洁 · 2026-2-9 08:26:32

喜欢鼓捣这些软件，现在用得少，谢谢分享！

钿稳铆 · 2026-2-9 21:54:32

谢谢楼主提供！

琦谓 · 2026-2-10 11:06:24

感谢分享

乱蚣 · 2026-2-11 04:30:16

yyds。多谢分享

卓卞恻 · 2026-2-11 16:27:42

热心回复！

账号		自动登录	找回密码
密码			立即注册

重生之数据结构与算法----队列&栈

相关帖子

回复

浏览过的版块

签约作者

重生之数据结构与算法----队列&栈

相关帖子

相关推荐

回复

浏览过的版块

签约作者