当前位置： 首页 > article >正文

初级数据结构——栈与队列的互相实现

article 2025/2/20 6:04:15

目录

  • 前言
  • 一、用栈实现队列
    • 操作：
    • c++代码模版
    • 经典例题
  • 二、用队列实现栈
    • 操作：
    • c++代码模版
    • 经典例题
  • 三、总结
  • 四、结语

前言

通过我之前的作品已经初步理解了栈和队列的数据结构，这期我们来学习如何实现这两个数据结构的互相转换。在计算机科学中，栈（Stack）和队列（Queue）是两种常见的数据结构，它们具有不同的操作特性和应用场景。栈遵循后进先出（LIFO, Last In First Out）的原则，而队列遵循先进先出（FIFO, First In First Out）的原则。尽管它们有不同的特性，但我们可以利用其中一种数据结构来实现另一种数据结构。

在这里插入图片描述

一、用栈实现队列

操作：

要使用栈来实现队列，我们需要两个栈：一个用于处理入队操作（stack_in），另一个用于处理出队操作（stack_out）。

入队（Enqueue）：
直接将元素压入 stack_in。

出队（Dequeue）：
如果 stack_out 为空，则将 stack_in 中的所有元素逐个弹出并压入 stack_out（这样原来 stack_in 中的栈底元素就移动到了 stack_out 的栈顶）。然后从 stack_out 弹出栈顶元素。

检查队列是否为空（IsEmpty）：
当 stack_in 和 stack_out 都为空时，队列为空。

查看队列的头部元素（Peek）：
类似于出队操作，但如果 stack_out 为空，则将 stack_in 中的所有元素移动到 stack_out，然后返回 stack_out 的栈顶元素（但不弹出）。

c++代码模版

#include<iostream>
#include<exception>
using namespace std;

template<typename T>//定制栈里面的元素，就像vector一样
class Stack {
private:
	int size;//既为栈元素个数又为栈顶位置
	int capacity;
	T* data;
	void resize();
public:
	Stack() :data(new T[capacity]), size(0), capacity(10) {}//构造函数，申请类型为T容量为capacity的内存空间，相当于数组
	~Stack();
	void push(T x);
	T top() const;
	T pop();
	int getSize() const;
	bool empty() const;
};

template<typename T>
void Stack<T>::resize() {//顺序栈扩容
	int newCapacity = 2 * capacity;
	T* newData = new T[newCapacity];
	for (int i = 0; i < size; i++) {
		newData[i] = data[i];
	}
	delete[]data;
	data = newData;
	capacity = newCapacity;
}

template<typename T>
Stack<T>::~Stack() {
	delete[]data;
}

template<typename T>
void Stack<T>::push(T x) {
	if (size == capacity) {
		resize();
	}
	data[size++] = x;
}

template<typename T>
T Stack<T>::top() const {
	if (!size) {
		throw std::underflow_error("Stack is empty");//如果栈为空即为非法状态，抛出异常
	}
	return data[size - 1];//注意栈元素序号从零开始
}

template<typename T>
T Stack<T>::pop() {
	if (!size) {
		throw std::underflow_error("Stack is empty");
	}
	return data[--size];
}

template<typename T>
int Stack<T>::getSize() const {
	return size;
}

template<typename T>
bool Stack<T>::empty() const {
	return size == 0;
}


class MyQueue {
private:
	Stack<int> s1;//s1作为辅助栈
	Stack<int> s2;
public:
	MyQueue(){}
	void push(int x) {
		s1.push(x);//队列插入元素，就是把元素插入s1中
	}
	int pop() {
		if (s2.empty()) {//队列出队操作，就是将s1中谈栈入栈到s2中，队首就是s2的栈顶
			while (!s1.empty()) {
				s2.push(s1.pop());
			}
		}
		return s2.pop();
	}
	int peek() {//去队首函数
		if (s2.empty()) {
			while (!s1.empty()) {
				s2.push(s1.pop());
			}
		}
		return s2.top();
	}
	bool empty() {//队列判空函数
		return s1.empty() && s2.empty();
	}
};


int main() {
	MyQueue m;
	for (int i = 0; i < 5; i++) {
		m.push(i);
	}
	cout << m.peek() << endl;

	return 0;
}

经典例题

面试题 03.04. 化栈为队
（蓝色字体可以点进去看原题）

代码题解

template<typename T>//定制栈里面的元素，就像vector一样
class Stack {
private:
	int size;//既为栈元素个数又为栈顶位置
	int capacity;
	T* data;
	void resize();
public:
	Stack() :data(new T[capacity]), size(0), capacity(10) {}//构造函数，申请类型为T容量为capacity的内存空间，相当于数组
	~Stack();
	void push(T x);
	T top() const;
	T pop();
	int getSize() const;
	bool empty() const;
};

template<typename T>
void Stack<T>::resize() {//顺序栈扩容
	int newCapacity = 2 * capacity;
	T* newData = new T[newCapacity];
	for (int i = 0; i < size; i++) {
		newData[i] = data[i];
	}
	delete[]data;
	data = newData;
	capacity = newCapacity;
}

template<typename T>
Stack<T>::~Stack() {
	delete[]data;
}

template<typename T>
void Stack<T>::push(T x) {
	if (size == capacity) {
		resize();
	}
	data[size++] = x;
}

template<typename T>
T Stack<T>::top() const {
	if (!size) {
		throw std::underflow_error("Stack is empty");//如果栈为空即为非法状态，抛出异常
	}
	return data[size - 1];//注意栈元素序号从零开始
}

template<typename T>
T Stack<T>::pop() {
	if (!size) {
		throw std::underflow_error("Stack is empty");
	}
	return data[--size];
}

template<typename T>
int Stack<T>::getSize() const {
	return size;
}

template<typename T>
bool Stack<T>::empty() const {
	return size == 0;
}


class MyQueue {
private:
	Stack<int> s1;//s1作为辅助栈
	Stack<int> s2;
public:
	MyQueue(){}
	void push(int x) {
		s1.push(x);//队列插入元素，就是把元素插入s1中
	}
	int pop() {
		if (s2.empty()) {//队列出队操作，就是将s1中谈栈入栈到s2中，队首就是s2的栈顶
			while (!s1.empty()) {
				s2.push(s1.pop());
			}
		}
		return s2.pop();
	}
	int peek() {//去队首函数
		if (s2.empty()) {
			while (!s1.empty()) {
				s2.push(s1.pop());
			}
		}
		return s2.top();
	}
	bool empty() {//队列判空函数
		return s1.empty() && s2.empty();
	}
};

二、用队列实现栈

要使用队列来实现栈，我们可以使用一个队列（queue）和两个辅助变量：size 用于跟踪队列中的元素数量，main_queue 和 temp_queue 用于操作。

操作：

入栈（Push）：
将新元素添加到 temp_queue。
将 main_queue 中的所有元素依次出队并重新入队到 temp_queue（这样原来 main_queue 中的最后元素就到了 temp_queue 的前面）。交换 main_queue 和 temp_queue 的引用。

出栈（Pop）：
从 main_queue 出队元素（因为 main_queue 的第一个元素就是栈顶元素）。

检查栈是否为空（IsEmpty）：
当 main_queue 为空时，栈为空。

查看栈顶元素（Peek）：
返回 main_queue 的第一个元素（但不出队）。

c++代码模版

#include<iostream>
#include<exception>
using namespace std;

template<typename T>
class Queue {
private:
	int front;
	int rear;
	int capacity;
	T* data;
	void resize();
public:
	Queue() :data(new T[capacity]), front(0), rear(0), capacity(10) {}
	~Queue();
	void Enqueue(T x);
	T Dequeue();
	T getFront();
	int size();
	bool empty();
};

template<typename T>
void Queue<T>::resize() {
	int newCapacity = capacity * 2;
	T* newData = new T[newCapacity];
	for (int i = front; i < rear; i++) {
		newData[i] = data[i];
	}
	delete[] data;
	data = newData;
	capacity = newCapacity;
}

template<typename T>
Queue<T>::~Queue() {
	delete[]data;
}

template<typename T>
void Queue<T>::Enqueue(T x) {
	if (rear == capacity) resize();
	data[rear++] = x;
}

template<typename T>
T Queue<T>::Dequeue() {
	if (front == rear) {
		throw std::underflow_error("Queue is empty!");
	}
	return data[front++];
}

template<typename T>
T Queue<T>::getFront() {
	if (front == rear) {
		throw std::underflow_error("Queue is empty!");
	}
	return data[front];
}

template<typename T>
int Queue<T>::size() {
	return rear - front;
}

template<typename T>
bool Queue<T>::empty() {
	return size() == 0;
}

class MyStack {
private:
	Queue<int>q1;//辅助队列
	Queue<int>q2;
public:
	void push(int x) {
		q1.Enqueue(x);
	}
	int pop() {
		while (q1.size() > 1) {
			q2.Enqueue(q1.Dequeue());
		}
		int ret = q1.Dequeue();
		while (!q2.empty()) {
			q1.Enqueue(q2.Dequeue());
		}
		return ret;
	}
	int top() {
		while (q1.size() > 1) {//把q1除队尾以为元素存入q2,剩下的元素就是栈顶
			q2.Enqueue(q1.Dequeue());
		}
		int ret = q1.Dequeue();//去除栈顶以后记得将该值放进q2
		q2.Enqueue(ret);
		while (!q2.empty()) {
			q1.Enqueue(q2.Dequeue());
		}
		return ret;
	}
	bool empty() {
		return q1.empty();
	}
};

int main() {
	MyStack s;
	for (int i = 0; i < 5; i++) {
		s.push(i);
	}
	cout << s.top() << endl;
	int x = s.pop();
	cout << x << endl;
	cout << s.empty() << endl;
	return 0;
}

经典例题

225. 用队列实现栈

代码题解

template<typename T>
class Queue {
private:
	int front;
	int rear;
	int capacity;
	T* data;
	void resize();
public:
	Queue() :data(new T[capacity]), front(0), rear(0), capacity(10) {}
	~Queue();
	void Enqueue(T x);
	T Dequeue();
	T getFront();
	int size();
	bool empty();
};

template<typename T>
void Queue<T>::resize() {
	int newCapacity = capacity * 2;
	T* newData = new T[newCapacity];
	for (int i = front; i < rear; i++) {
		newData[i] = data[i];
	}
	delete[] data;
	data = newData;
	capacity = newCapacity;
}

template<typename T>
Queue<T>::~Queue() {
	delete[]data;
}

template<typename T>
void Queue<T>::Enqueue(T x) {
	if (rear == capacity) resize();
	data[rear++] = x;
}

template<typename T>
T Queue<T>::Dequeue() {
	if (front == rear) {
		throw std::underflow_error("Queue is empty!");
	}
	return data[front++];
}

template<typename T>
T Queue<T>::getFront() {
	if (front == rear) {
		throw std::underflow_error("Queue is empty!");
	}
	return data[front];
}

template<typename T>
int Queue<T>::size() {
	return rear - front;
}

template<typename T>
bool Queue<T>::empty() {
	return size() == 0;
}

class MyStack {
private:
	Queue<int>q1;//辅助队列
	Queue<int>q2;
public:
	void push(int x) {
		q1.Enqueue(x);
	}
	int pop() {
		while (q1.size() > 1) {
			q2.Enqueue(q1.Dequeue());
		}
		int ret = q1.Dequeue();
		while (!q2.empty()) {
			q1.Enqueue(q2.Dequeue());
		}
		return ret;
	}
	int top() {
		while (q1.size() > 1) {//把q1除队尾以为元素存入q2,剩下的元素就是栈顶
			q2.Enqueue(q1.Dequeue());
		}
		int ret = q1.Dequeue();//去除栈顶以后记得将该值放进q2
		q2.Enqueue(ret);
		while (!q2.empty()) {
			q1.Enqueue(q2.Dequeue());
		}
		return ret;
	}
	bool empty() {
		return q1.empty();
	}
};

三、总结

通过以上方法，我们可以使用栈来实现队列，或使用队列来实现栈。这些实现虽然效率不如直接使用相应的数据结构（因为涉及额外的操作），但它们展示了数据结构之间的转换和灵活性。

四、结语

通过本次学习相信大家对栈和队列这两个数据结构有更深刻理解了，希望大家多刷题巩固知识点，那么下期我们一起学习初级数据结构——串。

在这里插入图片描述
想看更多内容可以关注我，看我作品，关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家

在这里插入图片描述


http://www.kler.cn/a/406506.html

相关文章：

  • 【倍数问题——同余系】
  • PDF电子发票信息转excel信息汇总
  • Elasticsearch 分词器
  • “人工智能+高职”：VR虚拟仿真实训室的发展前景
  • 安装多个nodejs版本（nvm）
  • 2024年11月最新版Adobe PhotoShop(26.0)中文版下载
  • 高性能网络SIG月度动态： 推进SMC支持基于eBPF透明替换和内存水位限制等多项功能支持
  • 在线pdf转word免费工具
  • AI科技赋能，探索人力资源管理软件的高效应用
  • C++11异步操作——std::future
  • 即时通讯app入侵了 怎么办？
  • 浦语提示词工程实践(LangGPT版，服务器上部署internlm2-chat-1_8b，踩坑很多才完成的详细教程，)
  • IAR与鸿轩科技共同推进汽车未来
  • 实验07---7-03 n个数存入数组，输出下标奇数的元素
  • 代理IP：苹果Siri与ChatGPT Plus融合的关键助力
  • Android上运行Opencv（TODO）
  • 机器学习周志华学习笔记-第3章＜线性模型＞
  • 【阅读记录-章节3】Build a Large Language Model (From Scratch)
  • 掌上单片机实验室 – RT-Thread + ROS2 初探（25）
  • 【FTHR-G0001开发板测评】简介、程序测试