梅头脑_

梅头脑_

关注
发信
关注(28)粉丝(399)

数据结构03：栈、队列和数组 队习题01[C++]

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

考研笔记整理~🥝🥝

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

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

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

编辑：梅头脑🌸

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

目录

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

🧵02 队列元素逆置

🧵03 利用两个栈模拟队列

🧵04 链栈

🔚结语

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

🧩题目

📇解题思路

虽然 入栈和出栈的指针判断均为 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++]-LMLPHP

🧵02 队列元素逆置

🧩题目

📇解题思路

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

⌨️解题代码

#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++]-LMLPHP

🧵03 利用两个栈模拟队列

🧩题目

📇解题思路

入栈的时候直接进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++]-LMLPHP

🧵04 链栈

🧩题目

📇算法思路

  • 链栈可以灵活增加队列占用空间，满足题目要求；而如果使用动态循环数组，平时查询和删除的时间复杂度是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++]-LMLPHP

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

#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++]-LMLPHP

🔚结语

博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等，博主会顶锅前来修改~😶‍🌫️

我是梅头脑，本片博文若有帮助，欢迎小伙伴动动可爱的小手默默给个赞支持一下，收到点赞的话，博主肝文的动力++~🌟🌟

同系列的博文：🌸数据结构_梅头脑_的博客-CSDN博客

同博主的博文：🌸随笔03 笔记整理-CSDN博客

04-01 19:41
Powered by LMLPHP ©2024 梅头脑_ 0.002089