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

英雄爱吃土豆片

发布于 2020-10-29 11:00:26

4310

发布于 2020-10-29 11:00:26

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

栈的顺序存储结构与操作题目编号:457

请你定义一个顺序栈，可以对顺序栈进行“将某个元素入栈”、“弹出栈顶元素”、“取栈顶元素（不删除）”、“判断栈是否为空”、“清空栈”等操作。键盘输入一些命令，可以执行上述操作。本题中，顺序栈元素为字符，顺序栈的最大长度为10。输入描述

各个命令以及相关数据的输入格式如下：将某个元素入栈：P，接下来一行是要入栈的元素

弹出栈顶元素：D

取栈顶元素（不删除）：G 清空栈：T 判断栈是否为空操作：Y 当输入的命令为E时，程序结束

输出描述

当输入的命令为Y时，输出栈是否为空，如果栈为空输出Yes，栈不空输出No。

当输入命令G时，输出取出的栈顶元素

当输入命令D时，输出弹出的栈顶元素

注意：如果没有满足的元素，输出None，所有的元素均占一行

输入样例

P 1 P 2 D G Y T D Y P 3 P 4 G E

输出样例

2 1 No None Yes 4

解题思路： 水。

通关代码：

#include <iostream>

#define MaxSize 10

using namespace std;

class Stack {
	public:
		Stack();
		
	public:
		void Push(char ch);
		char Pop();
		char getTop();
		void Clear();
		bool isEmpty();
		
	private:
		char arr_[MaxSize];
		int top_;
};

Stack::Stack() {
	top_ = 0;
}

void Stack::Push(char ch) {
	if (top_ == MaxSize) throw "上溢";
	
	arr_[++top_] = ch;
}

char Stack::Pop() {
	if (top_ == 0) throw "None";
	
	char ch = arr_[top_];
	
	top_--;
	
	return ch;
}

char Stack::getTop() {
	return arr_[top_];
}

void Stack::Clear() {
	top_ = 0;
}

bool Stack::isEmpty() {
	return top_ ? false : true;
}

int main() {
	Stack s;	
	char val, key;

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

				case 'T':
					s.Clear();
					break;

				case 'G':
					cout << s.getTop() << endl;
					break;

				case 'D':
					cout << s.Pop() << endl;
					break;
					
				case 'Y':
					cout << (s.isEmpty() ? "Yes" : "No") << endl;
			}
		} catch (const char* str) {
			cout << str << endl;
		}
	}
	
	return 0;
}

栈的链式存储结构与操作题目编号:458

题目要求： 同上。

解题思路： 水。

通关代码：

#include <iostream>

using namespace std;

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

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

	public:
		void Push(char val);
		char Pop();
		void Clear();
		char getTop();
		bool isEmpty();

	private:
		Node* top_;
		int length_;
};

Stack::Stack() {
	top_ = NULL;
	length_ = 0;
}

Stack::~Stack() {
	Node* afterTop = NULL;
	
	for (Node* p = top_; p != NULL; p = afterTop) {
		afterTop = p->_next;
		delete p;
	}
}

void Stack::Push(char val) {
	Node* node = new Node(val);
	
	node->_next = top_;
	top_ = node;
	
	length_++;
}

char Stack::Pop() {
	if (length_ == 0) throw "None";
	
	Node* deletedNode = top_;
	char val = deletedNode->_val;
	
	top_ = top_->_next;
	
	delete deletedNode;
	
	length_--;
	
	return val;
}

void Stack::Clear() {
	Node* afterTop = NULL;
	
	for (Node* p = top_; p != NULL; p = afterTop) {
		afterTop = p->_next;
		delete p;
	}	
	
	length_ = 0;
	
	top_ = NULL;
}

char Stack::getTop() {
	if (length_ == 0) throw "None";
	
	return top_->_val;
}

bool Stack::isEmpty() {
	return length_ ? false : true;
}

int main() {
	Stack s;	
	char val, key;

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

				case 'T':
					s.Clear();
					break;

				case 'G':
					cout << s.getTop() << endl;
					break;

				case 'D':
					cout << s.Pop() << endl;
					break;
					
				case 'Y':
					cout << (s.isEmpty() ? "Yes" : "No") << endl;
			}
		} catch (const char* str) {
			cout << str << endl;
		}
	}

	return 0;
}

毕。

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

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

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

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

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

登录后参与评论

0 条评论

热度