当前位置:网站首页>Simple knapsack, queue and stack with deque
Simple knapsack, queue and stack with deque
2022-07-05 05:35:00 【Raise items】
List of articles
Algorithm
When solving a problem , it is to be noted that : understand and Definition problem , Control the problem Complexity , Put it decompose For sub problems that are easier to solve .
The steps to solve the problem Called algorithm .
In the field of Computer Science , We use it Algorithm This word describes a kind of Co., LTD. 、 determine 、 It works And suitable for A computer program To solve the problem .
Computing and storage resources of computers are limited , So it can only solve some mathematical theoretical problems .
To define an algorithm , We can use Natural language Describe the process of solving a problem , Or use a Program Design language to realize this process .
To calculate two nonnegative integers p
and q
Of greatest common divisor For example .
Natural language description
if q
yes 0
, Then the greatest common divisor is p
;
otherwise , take p
Divide q
Get the remainder r
,p
and q
The greatest common divisor of is q
and r
Maximum common divisor of .
C++ Realization
int gcd(int p, int q)
{
if (q == 0) {
return p;
}
return gcd(q, p % q);
}
Compared to natural language , The program is more about the algorithm accurate and Completely Description of .
meanwhile , data structure It is the by-product or result of the algorithm , Therefore, to understand the algorithm, we must learn the data structure .
data structure
Here are three data structures : knapsack 、 queue and Stack .
Generic and iteration (template<typename Item>
Iterable<Item>
) It can ensure that three data structures can be stored Any type The elements of , And the element is in a form that can be Traverse Preserved in the form of .
In this case , Use STL
Medium deque
Storage elements . knapsack 、 Both queues and stacks are right deque
Encapsulation .
knapsack
Knapsack is a data structure that collects elements , Deleting elements... Is not supported .bag.h
#include <deque>
template <typename Item>
class Bag {
public:
Bag(); // Create an empty backpack
void Add(const Item &item); // Additive elements
bool IsEmpty(); // Whether the backpack is empty
int Size(); // The number of elements in the backpack
private:
std::deque<Item> dq_;
};
template <typename Item>
Bag<Item>::Bag() {
}
template<typename Item>
void Bag<Item>::Add(const Item &item)
{
dq_.push_back(item);
}
template <typename Item>
bool Bag<Item>::IsEmpty()
{
return dq_.empty();
}
template <typename Item>
int Bag<Item>::Size()
{
return dq_.size();
}
queue
Queue is based on fifo The set type of the strategy .queue.h
#include <deque>
template <typename Item>
class Queue {
public:
Queue(); // Create an empty queue
void EnQueue(const Item &item); // Additive elements
Item Dequeue(); // Delete the first added element
bool IsEmpty(); // Whether the queue is empty
int Size(); // The number of elements in the queue
private:
std::deque<Item> dq_;
};
template <typename Item>
Queue<Item>::Queue() {
}
template <typename Item>
void Queue<Item>::EnQueue(const Item &item)
{
dq_.push_back(item);
}
template <typename Item>
Item Queue<Item>::Dequeue()
{
auto item = dq_.front();
dq_.pop_front();
return item;
}
template <typename Item>
bool Queue<Item>::IsEmpty()
{
return dq_.empty();
}
template <typename Item>
int Queue<Item>::Size()
{
return dq_.size();
}
Stack
The stack is based on Last in, first out The set type of the strategy .stack.h
#include <deque>
template <typename Item>
class Stack {
public:
Stack(); // Create an empty stack
void Push(const Item &item); // Additive elements
Item Pop(); // Delete recently added elements
bool IsEmpty(); // Is the stack empty
int Size(); // The number of elements in the stack
private:
std::deque<Item> dq_;
};
template <typename Item>
Stack<Item>::Stack() {
}
template <typename Item>
void Stack<Item>::Push(const Item &item)
{
dq_.push_back(item);
}
template <typename Item>
Item Stack<Item>::Pop()
{
auto item = dq_.back();
dq_.pop_back();
return item;
}
template <typename Item>
bool Stack<Item>::IsEmpty()
{
return dq_.empty();
}
template <typename Item>
int Stack<Item>::Size()
{
return dq_.size();
}
A classic application of stack is computation Arithmetic expressions Value . for example :(1 + ((2 + 3) * (4 * 5)))
边栏推荐
- A misunderstanding about the console window
- Binary search basis
- To be continued] [UE4 notes] L4 object editing
- ALU逻辑运算单元
- Light a light with stm32
- Zheng Qing 21 ACM is fun. (3) part of the problem solution and summary
- Control Unit 控制部件
- 使用Electron开发桌面应用
- 搭建完数据库和网站后.打开app测试时候显示服务器正在维护.
- [jailhouse article] performance measurements for hypervisors on embedded ARM processors
猜你喜欢
CF1637E Best Pair
[speed pointer] 142 circular linked list II
Yolov5 ajouter un mécanisme d'attention
Using HashMap to realize simple cache
Chapter 6 data flow modeling - after class exercises
Talking about JVM (frequent interview)
全排列的代码 (递归写法)
In this indifferent world, light crying
[article de jailhouse] jailhouse hypervisor
Sword finger offer 05 Replace spaces
随机推荐
Double pointer Foundation
Using HashMap to realize simple cache
CF1634 F. Fibonacci Additions
【Jailhouse 文章】Jailhouse Hypervisor
ssh免密登录设置及使用脚本进行ssh登录并执行指令
游戏商城毕业设计
Analysis of backdoor vulnerability in remote code execution penetration test / / phpstudy of national game title of national secondary vocational network security B module
剑指 Offer 05. 替换空格
Summary of Haut OJ 2021 freshman week
每日一题-无重复字符的最长子串
How can the Solon framework easily obtain the response time of each request?
[to be continued] [UE4 notes] L3 import resources and project migration
sync. Interpretation of mutex source code
Haut OJ 1316: sister choice buys candy III
个人开发的渗透测试工具Satania v1.2更新
Haut OJ 1218: maximum continuous sub segment sum
【ES实战】ES上的native realm安全方式使用
YOLOv5-Shufflenetv2
lxml. etree. XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
剑指 Offer 53 - II. 0~n-1中缺失的数字