Implement a fixed capacity stack

Constant volume string stack

Consider implementing a Fixed capacity The stack , This stack can only store character string .

Realization function

fix_string_stack.h

#ifndef FIX_STRING_STACK
#define FIX_STRING_STACK

#include <vector>
#include <string>

using std::vector;
using std::string;

class FixStringStack {
    
public:
    FixStringStack(size_t n);
    void Push(const string &str);
    string Pop();
    bool IsEmpty() const;
    size_t Size() const;

private:
    vector<string> vStr;
    size_t N;
};

#endif

fix_string_stack.cpp

#include "fix_string_stack.h"

FixStringStack::FixStringStack(size_t n) : vStr(n), N(0) {
    }

void FixStringStack::Push(const string &str)
{
    
    vStr[N++] = str;
}

string FixStringStack::Pop()
{
    
    return vStr[--N];
}

bool FixStringStack::IsEmpty() const
{
    
    return N == 0;
}

size_t FixStringStack::Size() const
{
    
    return N;
}

Write tests

fix_string_stack_test.h

#ifndef FIX_STRING_TEST_H
#define FIX_STRING_TEST_H

void FixStringStackTest();

#endif

fix_string_stack_test.cpp

#include "fix_string_stack.h"
#include <iostream>
#include <string>

void FixStringStackTest()
{
    
    FixStringStack st(100);
    std::string str;

    while (std::cin >> str) {
    
        if (str != string("-")) {
    
            st.Push(str);
        } else if (!st.IsEmpty()) {
    
            std::cout << st.Pop() << std::endl;
        }
    }

    std::cout << st.Size() << std::endl;
}

function

main.cpp

#include "fix_string_stack_test.h"

int main()
{
    
    FixStringStackTest();

    return 0;
}

Running results ：

Fixed volume stack advantage Every time Push and Pop Required for operation Time is independent of the length of the stack .

FixStringStack The disadvantages are also obvious ：
(1) Can only store string object .
(2) Before use, you must Estimate the maximum capacity of the stack , It may cause Memory waste .
(3)Push Time detection Is the stack full .

Let's ignore vector The ability to dynamically allocate memory , Think of it as an ordinary array .

Constant volume stack

For the above shortcomings , Use the following method to optimize , And try to ensure that its advantages are still .
(1) Generic Programming .
(2) Time dynamic Allocate memory .

Realization

fix_stack.h

#ifndef FIX_STACK
#define FIX_STACK

#include <cstddef>

template <typename Item>
class FixStack {
    
public:
    FixStack(size_t cap);
    ~FixStack();

    void Push(const Item &item);
    Item Pop();
    bool IsEmpty() const;
    size_t Size() const;

private:
    void ReSize(size_t max);

    size_t cap_;
    size_t sz_;
    Item *data_;
};

template <typename Item>
FixStack<Item>::FixStack(size_t cap) : cap_(cap), sz_(0)
{
    
    data_ = new Item[cap_];
}

template <typename Item>
FixStack<Item>::~FixStack()
{
    
    delete[] data_;
    data_ = nullptr;
}

template <typename Item>
void FixStack<Item>::ReSize(size_t max)
{
    
    Item *newData = new Item[max];
    for (size_t i = 0; i < sz_; ++i) {
    
        newData[i] = data_[i];
    }

    data_ = newData;
    cap_ = max;
}

template <typename Item>
void FixStack<Item>::Push(const Item &item)
{
    
    if (sz_ == cap_) {
    
        ReSize( 2 * cap_);
    }
    data_[sz_++] = item;
}

template <typename Item>
Item FixStack<Item>::Pop()
{
    
    return data_[--sz_];
}

template <typename Item>
bool FixStack<Item>::IsEmpty() const
{
    
    return sz_ == 0;
}

template <typename Item>
size_t FixStack<Item>::Size() const
{
    
    return sz_;
}

#endif

C++ in Templates The definition and implementation of classes must be written in The same In the document .
Dynamically allocate memory over time ：Push when , If the memory for saving data is full , Just Reallocate current capacity 2 Times more memory , And copy the existing data into the new memory .
Destructor ： When the stack object dies , Free the heap memory it requested , Avoid memory leaks .

test

fix_stack_test.h

#ifndef FIX_STACK_TEST
#define FIX_STACK_TEST

void FixStackTest();

#endif

fix_stack_test.cpp

#include "fix_stack.h"
#include <string>
#include <iostream>

void FixStackTest()
{
    
    FixStack<std::string> st(1);
    std::string str;

    while (std::cin >> str) {
    
        if (str != std::string("-")) {
    
            st.Push(str);
        } else if (!st.IsEmpty()) {
    
            std::cout << st.Pop() << std::endl;
        }
    }

    std::cout << st.Size() << std::endl;
}

function

main.cpp

#include "fix_stack_test.h"

int main()
{
    
    FixStackTest();

    return 0;
}

Running results ：