数据结构03：栈、队列和数组队习题01[C++]-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构03：栈、队列和数组队习题01[C++]。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构03：栈、队列和数组队习题01[C++],# 数据结构,数据结构,c++,开发语言

考研笔记整理~🥝🥝

之前的博文链接在此：数据结构03：栈、队列和数组_-CSDN博客~🥝🥝

本篇作为链表的代码补充，供小伙伴们参考~🥝🥝

第1版：王道书的课后习题~🧩🧩

编辑：梅头脑🌸

参考用书：王道考研《2025年数据结构考研复习指导》

🧵01 不牺牲存储单元的单链表

🧵02 队列元素逆置

🧵03 利用两个栈模拟队列

🧵04 链栈

🔚结语

🧵01 不牺牲存储单元的单链表

🧩题目

若希望循环队列中的元素都能得到利用，则需设置一个标志域 tag，并以 tag 的值为 0或1来区分队头指针 front 和队尾指针 rear 相同时的队列状态是“空”还是“满”试编写与此结构相应的入队和出队算法。

📇解题思路

虽然入栈和出栈的指针判断均为 front == rear，但是考虑到仅入栈会导致栈满，出栈是导致栈空，因为，入栈与出栈的条件如下：

tag == 1（上一次为入队操作） && front == rear 时，表示栈满；
tag == 0（上一次为出队操作） && front == rear 时，表示栈空；

⌨️解题代码

#include <iostream>
using namespace std;

const int MaxSize = 5;
typedef struct {
	int data[MaxSize];
	int front, rear;
	int tag;
}SeQueue;

class Queue {
private:
	SeQueue* q;
public:
	Queue();
	~Queue();
	bool IsEmpty();
	bool IsFull();
	bool EnQueue(int x);
	bool DeQueue(int& x);
};

Queue::Queue() {
	q = new SeQueue;
	q->front = q->rear = 0;
	q->tag = 0;
}
Queue::~Queue() {
	delete q;
}
bool Queue::IsEmpty() {
	if (q->front == q->rear && q->tag == 0) { cout << "队列为空"; return true; }
	else { cout << "队列不空"; return false; }
}
bool Queue::IsFull() {
	if (q->front == q->rear && q->tag == 1) { cout << "队列已满"; return true; }
	else { cout << "队列未满"; return false; }
}
bool Queue::EnQueue(int x) {
	if (IsFull() == true) { cout << " 入队失败" << endl; return false; }
	q->data[q->rear] = x;
	q->rear = (q->rear + 1) % MaxSize;
	q->tag = 1;
	cout << " 元素" << x << "入队成功" << endl; return true;
}
bool Queue::DeQueue(int& x) {
	if (IsEmpty() == true) { cout << " 出队失败" << endl; return false; }
	x = q->data[q->front];
	q->front = (q->front + 1) % MaxSize;
	q->tag = 0;
	cout << " 元素" << x << "出队成功" << endl; return true;
}

int main()
{
	Queue q;
	int x;
	q.EnQueue(1);
	q.EnQueue(2);
	q.EnQueue(3);
	q.EnQueue(4);
	q.EnQueue(5);
	q.EnQueue(6); // 队列已满, 入队失败
	q.DeQueue(x); cout << "出队元素：" << x << endl;
	q.DeQueue(x); cout << "出队元素：" << x << endl;
	q.DeQueue(x); cout << "出队元素：" << x << endl;
	q.DeQueue(x); cout << "出队元素：" << x << endl;
	q.DeQueue(x); cout << "出队元素：" << x << endl;
	q.DeQueue(x); // 队列为空, 出队失败

	return 0;
}

数据结构03：栈、队列和数组队习题01[C++],# 数据结构,数据结构,c++,开发语言

🧵02 队列元素逆置

🧩题目

只是一个队列，S是一个空栈，实现将队列中的元素逆置的算法。

📇解题思路

先把队的东西导入栈，再次出栈入队时即可实现逆序存储~

⌨️解题代码

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

bool Reverse(queue<int>& q) {
	stack<int> s;
 
	// 队列q中的元素全部入栈s
	while (!q.empty()) {
		s.push(q.front());
		q.pop();
	}
 
	// 栈s中的元素全部入队列q
	while (!s.empty()) {
		q.push(s.top());
		s.pop();
	}
	return true;
}

int main() {
	queue<int> q;

	q.push(1);
	q.push(2);
	q.push(3);

	bool result = Reverse(q);

	while (!q.empty()) {
		cout << q.front() << " ";
		q.pop();
	}
	return 0;
}

数据结构03：栈、队列和数组队习题01[C++],# 数据结构,数据结构,c++,开发语言

🧵03 利用两个栈模拟队列

🧩题目

利用两个栈 S1 和 S2 来模拟一个队列，已知栈的4个运算定义如下:
Push(S,x);                //元素x入栈 s
Pop(S,x);   //s出栈并将出栈的值赋给x
StackEmpty(S);        //判断栈是否为空
StackOverflow(S);    //判断栈是否满
如何利用栈的运算来实现该队列的3个运算(形参由读者根据要求自己设计)?
Engueue; //将元素x入队
Dequeue; //出队，并将出队元素存储在x中
QueueEmpty; //判断队列是否为空

📇解题思路

入栈的时候直接进S1，但是出栈时就不能直接从S1出栈了：栈顶元素出栈，不满足队列要求；

然而，S1的元素导入S2就可以实现一个负负得正的效果，因此，出栈的时候，先把S1的元素搬入S2，然后直接从S2中出栈~

⌨️解题代码

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

const int MaxSize = 5;

class Queue {
private:
	stack<int> s1;
	stack<int> s2;
	int size;
public:
	Queue();
	~Queue();
	bool Enqueue(int x);
	bool Dequeue(int& x);
	bool QueueEmpty();
};

Queue::Queue() {
	size = 0;
}
Queue::~Queue() {
}
bool Queue::Enqueue(int x) {
	if (size == MaxSize) {
		cout << "队列已满" << endl;
		return false;
	}
	s1.push(x);
	size++;
	cout << "元素" << x << "入队成功" << endl;
	return true;
}
bool Queue::Dequeue(int& x) {
	if (size == 0) {
		cout << "队列为空" << endl;
		return false;
	}
	// 如果s2为空, 则将s1中的元素全部转移到s2中；否则s2不为空, 元素直接出队
	if (s2.empty()) {
		while (!s1.empty()) {
			s2.push(s1.top());
			s1.pop();
		}
	}
	x = s2.top();
	s2.pop();
	size--;
	cout << "元素" << x << "出队成功" << endl;
	return true;
}
bool Queue::QueueEmpty() {
	if (size == 0) {
		cout << "队列为空" << endl;
		return true;
	}
	else {
		cout << "队列不空" << endl;
		return false;
	}
}

int main() {
	Queue q;
	int x;
	q.Enqueue(1); // 栈S1：1，栈S2：空
	q.Enqueue(2); // 栈S1：1 2，栈S2：空
	q.Enqueue(3); // 栈S1：1 2 3，栈S2：空
	q.Dequeue(x); // 栈S1：空，栈S2： 3 2
	q.Enqueue(4); // 栈S1：4，栈S2：3 2
	q.Enqueue(5); // 栈S1：4 5，栈S2：3 2
	q.Enqueue(6); // 栈S1：4 5 6，栈S2：3 2
	q.Dequeue(x); // 栈S1：4 5 6，栈S2：3 
	q.Enqueue(7); // 栈S1：4 5 6 7，栈S2：3
	q.Enqueue(8); // 队列已满, 入队失败
	q.Dequeue(x); // 栈S1：4 5 6 7，栈S2：空
	q.Dequeue(x); // 栈S1：空，栈S2：7 6 5 4
	q.Dequeue(x); // 栈S1：空，栈S2：7 6 5
	q.Dequeue(x); // 栈S1：空，栈S2：7 6
	q.Dequeue(x); // 栈S1：空，栈S2：7
	q.Dequeue(x); // 队列为空, 出队失败
	return 0;
}

数据结构03：栈、队列和数组队习题01[C++],# 数据结构,数据结构,c++,开发语言

🧵04 链栈

🧩题目

【2019 统考真题】请设计一个队列，要求满足:①初始时队列为空;②入队时，允许增加队列占用空间;③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减;④入队操作和出队操作的时间复杂度始终保持为0(1)。请回答:

        1)该队列是应选择链式存储结构，还是应选择顺序存储结构?
        2)画出队列的初始状态，并给出判断队空和队满的条件。
        3)画出第一个元素入队后的队列状态。
        4)给出入队操作和出队操作的基本过程。

📇算法思路

链栈可以灵活增加队列占用空间，满足题目要求；而如果使用动态循环数组，平时查询和删除的时间复杂度是O(1)，但是扩容的时间复杂度是O(n)，这一点就不用考虑了~
如果元素出队不想占用空间，那front指针直接从head后移就可以了，移动到front == rear，就是移动到末尾了~
emm...不过以下的代码，还是实现了删除的功能（感觉一直占用空间不删除怪怪的...）

⌨️算法代码（单链表版本）

#include <iostream>
using namespace std;

typedef struct LinkNode {
	int data;
	LinkNode* next;
	LinkNode() : data(0), next(nullptr) {}
	LinkNode(int x) : data(x), next(nullptr) {}
}LinkNode;

class LinkQueue {
private:
	LinkNode* head;
	LinkNode* front;
	LinkNode* rear;
public:
	LinkQueue();
	~LinkQueue();
	bool IsEmpty();
	bool EnQueue(int x);
	bool DeQueue(int& x);
};

LinkQueue::LinkQueue() {
	head = new LinkNode;
	front = rear = head;
}
LinkQueue::~LinkQueue() {
	delete head;
}
bool LinkQueue::IsEmpty() {
	if (front->next == nullptr) { cout << "队列为空 "; return true; }
	else { cout << "队列不空 "; return false; }
}
bool LinkQueue::EnQueue(int x) {
	LinkNode* p = new LinkNode(x);
	if (p == nullptr) { cout << "出队失败" << endl; return false; }
	rear->next = p;
	rear = p;
	cout << "元素" << x << "入队成功" << endl; return true;
}
bool LinkQueue::DeQueue(int& x) {
	if (IsEmpty() == true) { cout << "入队失败" << endl; return false; }
	LinkNode* p = front->next;
	x = p->data;
	front->next = p->next;
  delete p;
	cout << "元素" << x << "出队成功" << endl; return true;
}

int main()
{
	LinkQueue q;
	int x;
	q.EnQueue(1); // 队q：1
	q.EnQueue(2); // 队q：1 2
	q.EnQueue(3); // 队q：1 2 3
	q.DeQueue(x); // 队q：2 3
	q.EnQueue(4); // 队q：2 3 4
	q.EnQueue(5); // 队q：2 3 4 5
	q.EnQueue(6); // 队q：2 3 4 5 6
	q.DeQueue(x); // 队q：3 4 5 6
	q.EnQueue(7); // 队q：3 4 5 6 7
	q.EnQueue(8); // 队q：3 4 5 6 7 8
	q.DeQueue(x); // 队q：4 5 6 7 8
	q.DeQueue(x); // 队q：5 6 7 8
	q.DeQueue(x); // 队q：6 7 8
	q.DeQueue(x); // 队q：7 8
	q.DeQueue(x); // 队q：8
	q.DeQueue(x); // 队q: 空
	q.DeQueue(x); // 队列为空, 出队失败

	return 0;
}

数据结构03：栈、队列和数组队习题01[C++],# 数据结构,数据结构,c++,开发语言

⌨️算法代码（循环单链表版本）

#include <iostream>
using namespace std;

typedef struct LinkNode {
	int data;
	LinkNode* next;
	LinkNode() : data(0), next(nullptr) {}
	LinkNode(int x) : data(x), next(nullptr) {}
}LinkNode;

class LinkQueue {
private:
	LinkNode* head;
	LinkNode* front;
	LinkNode* rear;
public:
	LinkQueue();
	~LinkQueue();
	bool IsEmpty();
	bool EnQueue(int x);
	bool DeQueue(int& x);
};

LinkQueue::LinkQueue() {
	head = new LinkNode;
	front = rear = head;
}
LinkQueue::~LinkQueue() {
	delete head;
}
bool LinkQueue::IsEmpty() {
	if (head->next == head) { cout << "队列为空 "; return true; }
	else { cout << "队列不空 "; return false; }
}
bool LinkQueue::EnQueue(int x) {
	LinkNode* p = new LinkNode(x);
	if (p == nullptr) { cout << "入队失败" << endl; return false; } // 分配结点失败(内存已满
	rear->next = p;
	rear = p;
	rear->next = front;
	cout << "元素" << x << "入队成功" << endl; return true;
}
bool LinkQueue::DeQueue(int& x) {
	if (IsEmpty() == true) { cout << "出队失败" << endl; return false; }
	LinkNode* p = front->next;
	x = p->data;
	front->next = p->next;
	delete p;
	cout << "元素" << x << "出队成功" << endl; return true;
}

int main()
{
	LinkQueue q;
	int x;
	q.EnQueue(1); // 队q：1
	q.EnQueue(2); // 队q：1 2
	q.EnQueue(3); // 队q：1 2 3
	q.DeQueue(x); // 队q：2 3
	q.EnQueue(4); // 队q：2 3 4
	q.EnQueue(5); // 队q：2 3 4 5
	q.EnQueue(6); // 队q：2 3 4 5 6
	q.DeQueue(x); // 队q：3 4 5 6
	q.EnQueue(7); // 队q：3 4 5 6 7
	q.EnQueue(8); // 队q：3 4 5 6 7 8
	q.DeQueue(x); // 队q：4 5 6 7 8
	q.DeQueue(x); // 队q：5 6 7 8
	q.DeQueue(x); // 队q：6 7 8
	q.DeQueue(x); // 队q：7 8
	q.DeQueue(x); // 队q：8
	q.DeQueue(x); // 队q: 空
	q.DeQueue(x); // 队列为空, 出队失败

	return 0;
}

数据结构03：栈、队列和数组队习题01[C++],# 数据结构,数据结构,c++,开发语言