专栏首页英雄爱吃土豆片OJ刷题记录:队列的存储结构与操作

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

队列的顺序存储结构与操作 题目编号: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;
}

毕。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode刷题记录:剑指 Offer 06. 从尾到头打印链表

    题目要求: 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

    英雄爱吃土豆片
  • C/C++编程基础:函数指针

    在讲函数指针之前,我们需要先理解一个概念:编译器是怎么识别并调用函数的。 众所周知,在C/C++程序编译时,内存有四个功能分区: 1)代码区: 存放函数。...

    英雄爱吃土豆片
  • OJ刷题记录:L1-206-学霸递情书(15分)

    题目要求: 李雷和韩梅梅坐前后排。上课想说话怕老师发现,所以改为传小纸条。为了被老师发现他们纸条上说的是啥,他们约定了如下方法传递信息: 将26个英文字母(...

    英雄爱吃土豆片
  • DW2020 | Adobe Dreamweaver 2020中文破解版安装详细教程

    Adobe Dreamweaver,简称“DW”,中文名称 “梦想编织者”,是集网页制作和管理网站于一身的所见即所得网页代码编辑器。利用对 HTML、CSS、J...

    夏末浅笑
  • Leetcode刷题 206. 反转链表 递归迭代两种方法实现

    链接:https://leetcode-cn.com/problems/reverse-linked-list/

    一只胡说八道的猴子
  • Leetcode刷题 206. 反转链表 递归迭代两种方法实现

    **链接**:https://leetcode-cn.com/problems/reverse-linked-list/

    一只胡说八道的猴子
  • 腾讯教育三款产品入选中央电教馆“推荐名单”

    近日,教育部中央电化教育馆公布了2020年“数字校园综合解决方案”名单,腾讯智慧校园、企鹅智笔课堂、智慧教育数据中心三款腾讯教育产品成功入选。《数字校园综合解...

    鹅老师
  • Tensorflow入门教程(四十八)——Seg-GLGAN

    今天将分享Unet的改进模型Seg-GLGAN,改进模型来自2020年的论文《A CONTEXT BASED DEEP LEARNING APPROACH FO...

    医学处理分析专家
  • Mac下安装 MongoDB

    希希里之海
  • 优雅的使用UITableView

    在我们iOS开发中UITableView几乎是所有App都会使用的一个UI控件,因为业务的需要,我们常常会注册多种Cell,然后在

    会写bug的程序员

扫码关注云+社区

领取腾讯云代金券