OJ刷题记录：队列的存储结构与操作

英雄爱吃土豆片

发布于 2020-10-29 11:07:12

4080

发布于 2020-10-29 11:07:12

文章被收录于专栏：英雄爱吃土豆片英雄爱吃土豆片

队列的顺序存储结构与操作题目编号:460

题目要求： 请定义一个顺序队列，可以对队列进行“入队”、“出队”、“清空队列”、“获取队首元素”等操作。键盘输入一些命令，可以执行上述操作。本题中，队列的元素为字母，队列的最大元素个数为100。输入描述

输入各个命令，它们对应的格式如下：

入队：E a，a代表入队的元素，这里E和元素之间用空格分隔。

清空队列：C

获取队头元素：当输入的命令为D时，输出出队的元素值；

当输入的命令是G时，输出当前队首元素值；

如果没有元素可出队或可取,

输出描述

当输入的命令为D时，输出出队的元素值；

当输入的命令是G时，输出当前队首元素值；

如果没有元素可出队或可取,请输出None；

输入样例

E a G C E b D D Q

输出样例

a b None

解题思路： 每一次操作时需要对移动的数组下标（head_ 或者 rear_）进行取模，以实现数组的首尾循环，防止假溢出。

通关代码：

#include <iostream>

#define MaxSize 100

using namespace std;

class Queue {
	public:
		Queue();
		
	public:
		void Push(char ch);
		char Pop();
		void Clear();
		char getHead();
		
	private:
		char arr_[MaxSize];
		int head_;
		int rear_;
};

Queue::Queue() {
	head_ = 0;
	rear_ = 0;
}

void Queue::Push(char ch) {
	if ((rear_ + 1) % MaxSize == head_) throw "上溢";
	
	arr_[rear_] = ch;
	rear_ = (rear_ + 1) % MaxSize;
}

char Queue::Pop() {
	if (rear_ == head_) throw "None";
	
	char ch = arr_[head_]; 
	
	head_ = (head_ + 1) % MaxSize;
	
	return ch;
}

void Queue::Clear() {
	head_ = 0;
	rear_ = 0;
}

char Queue::getHead() {
	if (rear_ == head_) throw "None";
	
	return arr_[head_];
}

int main() {
	Queue q;	
	char val, key;

	while (cin >> key) {
		if (key == 'Q') break;
		
		try {
			switch (key) {
				case 'E':
					cin >> val;
					q.Push(val);
					break;

				case 'C':
					q.Clear();
					break;

				case 'G':
					cout << q.getHead() << endl;
					break;

				case 'D':
					cout << q.Pop() << endl;
					break;
			}
		} catch (const char* str) {
			cout << str << endl;
		}
	}
	
	return 0;
}

队列的链式存储结构与操作题目编号:115

题目要求： 同上。

解题思路： 水。

通关代码：

#include <iostream>

using namespace std;

struct Node {
	char _val;
	Node* _next;
	Node(int val):_val(val), _next(NULL) {}
};

class Queue {
	public:
		Queue();
		~Queue();

	public:
		void Push(char ch);
		char Pop();
		void Clear();
		char getHead();

	private:
		Node* head_;
		Node* rear_;
};

Queue::Queue() {
	head_ = new Node(-1);
	rear_ = head_;
}

Queue::~Queue() {
	Node* afterHead = NULL;

	for (Node* p = head_; p != NULL; p = afterHead) {
		afterHead = p->_next;
		delete p;
	}
}

void Queue::Push(char ch) {
	Node* node = new Node(ch);

	rear_->_next = node;
	rear_ = node;
}

char Queue::Pop() {
	if (head_->_next == NULL) throw "None";
	
	Node* popedNode = head_->_next;

	char res = popedNode->_val;
	head_->_next = popedNode->_next;

	delete popedNode;

	return res;
}

void Queue::Clear() {
	Node* afterHead = NULL;

	for (Node* p = head_->_next; p != NULL; p = afterHead) {
		afterHead = p->_next;
		delete p;
	}
	
	head_->_next = NULL;
	rear_ = head_;
}

char Queue::getHead() {
	if (head_->_next == NULL) throw "None";
	
	return head_->_next->_val;
}

int main() {
	Queue q;
	char val, key;

	while (cin >> key) {
		if (key == 'Q') break;

		try {
			switch (key) {
				case 'E':
					cin >> val;
					q.Push(val);
					break;

				case 'C':
					q.Clear();
					break;

				case 'G':
					cout << q.getHead() << endl;
					break;

				case 'D':
					cout << q.Pop() << endl;
					break;
			}
		} catch (const char* str) {
			cout << str << endl;
		}
	}

	return 0;
}

毕。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-09-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度