队列-栈基本原理
原创约 1068 字
计算机的两种存储方式,顺序存储(数组)和链式存储(链表)都讲完了,之后的所有数据结构都是基于这两种存储方式之上玩花活。
本文讲解队列和栈的基本原理,后面的文章会讲解如何用代码具体实现。
先说概念吧,其实队列和栈都是「操作受限」的数据结构。说它操作受限,主要是和基本的数组和链表相比,它们提供的 API 是不完整的。
比方说我们前面实现的数组和链表,增删查改的 API 都实现过了,你可以对任意一个索引元素进行增删查改,只要索引不越界,就随便你。
但是对于队列和栈,它们的操作是受限的:队列只能在一端插入元素,另一端删除元素;栈只能在某一端插入和删除元素。
形象地说,队列只允许在队尾插入元素,在队头删除元素,栈只允许在栈顶插入元素,从栈顶删除元素:
![](/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/1.jpg)
队列就像排队买票,先来的先买,后来的后买;栈就像一摞盘子,最先放的压在最下面,最后放的留在最上面,拿的时候也是最上面的先被拿走。所以我们常说,队列是一种「先进先出」的数据结构,栈是一种「先进后出」的数据结构,就是这个道理。
当然,这个图中把栈竖着画,队列横着画,只是为了更形象,但实际上它们底层都是数组和链表实现的,后面会讲到。
这两种数据结构的基本 API 如下:
java 🟢
// 队列的基本 API
class MyQueue<E> {
// 向队尾插入元素,时间复杂度 O(1)
void push(E e);
// 从队头删除元素,时间复杂度 O(1)
E pop();
// 查看队头元素,时间复杂度 O(1)
E peek();
// 返回队列中的元素个数,时间复杂度 O(1)
int size();
}
// 栈的基本 API
class MyStack<E> {
// 向栈顶插入元素,时间复杂度 O(1)
void push(E e);
// 从栈顶删除元素,时间复杂度 O(1)
E pop();
// 查看栈顶元素,时间复杂度 O(1)
E peek();
// 返回栈中的元素个数,时间复杂度 O(1)
int size();
}
cpp 🤖
// 队列的基本 API
template <typename E>
class MyQueue {
public:
// 向队尾插入元素,时间复杂度 O(1)
void push(const E& e);
// 从队头删除元素,时间复杂度 O(1)
E pop();
// 查看队头元素,时间复杂度 O(1)
E peek() const;
// 返回队列中的元素个数,时间复杂度 O(1)
int size() const;
};
// 栈的基本 API
template <typename E>
class MyStack {
public:
// 向栈顶插入元素,时间复杂度 O(1)
void push(const E& e);
// 从栈顶删除元素,时间复杂度 O(1)
E pop();
// 查看栈顶元素,时间复杂度 O(1)
E peek() const;
// 返回栈中的元素个数,时间复杂度 O(1)
int size() const;
};
python 🤖
# 队列的基本 API
class MyQueue:
# 向队尾插入元素,时间复杂度 O(1)
def push(self, e):
pass
# 从队头删除元素,时间复杂度 O(1)
def pop(self):
pass
# 查看队头元素,时间复杂度 O(1)
def peek(self):
pass
# 返回队列中的元素个数,时间复杂度 O(1)
def size(self):
pass
# 栈的基本 API
class MyStack:
# 向栈顶插入元素,时间复杂度 O(1)
def push(self, e):
pass
# 从栈顶删除元素,时间复杂度 O(1)
def pop(self):
pass
# 查看栈顶元素,时间复杂度 O(1)
def peek(self):
pass
# 返回栈中的元素个数,时间复杂度 O(1)
def size(self):
pass
go 🤖
// 队列的基本 API
type MyQueue[T any] struct {
}
// 向队尾插入元素,时间复杂度 O(1)
func (q *MyQueue[T]) Push(e T) {}
// 从队头删除元素,时间复杂度 O(1)
func (q *MyQueue[T]) Pop() T {}
// 查看队头元素,时间复杂度 O(1)
func (q *MyQueue[T]) Peek() T {}
// 返回队列中的元素个数,时间复杂度 O(1)
func (q *MyQueue[T]) Size() int {}
// 栈的基本 API
type MyStack[T any] struct {
}
// 向栈顶插入元素,时间复杂度 O(1)
func (s *MyStack[T]) Push(e T) {}
// 从栈顶删除元素,时间复杂度 O(1)
func (s *MyStack[T]) Pop() T {}
// 查看栈顶元素,时间复杂度 O(1)
func (s *MyStack[T]) Peek() T {}
// 返回栈中的元素个数,时间复杂度 O(1)
func (s *MyStack[T]) Size() int {}
javascript 🤖
// 队列的基本 API
class MyQueue {
// 向队尾插入元素,时间复杂度 O(1)
push(e) {}
// 从队头删除元素,时间复杂度 O(1)
pop() {}
// 查看队头元素,时间复杂度 O(1)
peek() {}
// 返回队列中的元素个数,时间复杂度 O(1)
size() {}
}
class MyStack {
// 向栈顶插入元素,时间复杂度 O(1)
push(e) {}
// 从栈顶删除元素,时间复杂度 O(1)
pop() {}
// 查看栈顶元素,时间复杂度 O(1)
peek() {}
// 返回栈中的元素个数,时间复杂度 O(1)
size() {}
}
不同编程语言中,队列和栈提供的方法名称可能不一样,但每个方法的效果肯定是一样的。
有些语言的标准库可能没有直接提供队列和栈,你可以自己用数组或者链表模拟出队列和栈的效果。下一章我就会先带你用链表实现队列和栈。