Simple knapsack, queue and stack with deque

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)))