26 C++ 数据结构 - 堆栈和队列的实现

数据结构基础

文章目录

• 数据结构基础
• • 基础结构定义
  • 一、堆栈
  • 二、队列

基础结构定义

程序=数据结构+算法

• 程序： 是数据结构与算法的载体，程序将数据结构和算法结合，转化为可执行的代码。
• 数据结构：组织和存储数据的方式（如数组、链表、树、图等），直接影响数据访问效率和逻辑关系。
• 算法：解决问题的步骤或规则（如排序、搜索、动态规划等），是程序实现功能的核心逻辑。

一、堆栈

// 堆栈
#include <iostream>
using namespace std;
class Stack {
public:
// 构造函数中分配内存
Stack (size_t size = 10) :
m_data (new int[size]), m_size (size),
m_top (0) {}
// 析构函数中释放内存
~Stack (void) {
if (m_data) {
delete[] m_data;
m_data = NULL;
}
m_size = 0;
m_top = 0;
}
// 压入
void push (int data) {
if (m_top >= m_size)
throw OverFlow ();
m_data[m_top++] = data;
}
// 弹出
int pop (void) {
if (! m_top)
throw UnderFlow ();
return m_data[—m_top];
}
// 空否
bool empty (void) {
return ! m_top;
}
private:
// 上溢异常
class OverFlow : public exception {
public:
const char* what (void) const throw () {
return "堆栈上溢";
}
};
// 下溢异常
class UnderFlow : public exception {
public:
const char* what (void) const throw () {
return "堆栈下溢";
}
};
int* m_data; // 数组
size_t m_size; // 容量
size_t m_top; // 栈顶
};
int main (void) {
try {
Stack stack;
for (int i = 0; i < 10; i++)
stack.push (i);
// stack.push (10); //堆栈上溢

while (! stack.empty ())
cout << stack.pop () << ' ';//9 8 7 6 5 4 3 2 1 0
// stack.pop ();//堆栈下溢
}
catch (exception& ex) {
cout << ex.what () << endl;
return –1;
}

return 0;
}

二、队列

// 队列
#include <iostream>
using namespace std;
class Queue {
public:
// 构造函数中分配内存
Queue (size_t size = 10) :
m_data (new int[size]), m_size (size),
m_rear (0), m_front (0), m_counter (0) {}
// 析构函数中释放内存
~Queue (void) {
if (m_data) {
delete[] m_data;
m_data = NULL;
}
m_size = 0;
m_rear = 0;
m_front = 0;
m_counter = 0;
}
// 压入
void push (int data) {
if (m_counter >= m_size)
throw OverFlow ();
if (m_rear >= m_size)
m_rear = 0;
m_counter++;
m_data[m_rear++] = data;
}
// 弹出
int pop (void) {
if (! m_counter)
throw UnderFlow ();
if (m_front >= m_size)
m_front = 0;
m_counter—;
return m_data[m_front++];
}
// 空否
bool empty (void) {
return ! m_counter;
}
private:
// 上溢异常
class OverFlow : public exception {
public:
const char* what (void) const throw () {
return "队列上溢";
}
};
// 下溢异常
class UnderFlow : public exception {
public:
const char* what (void) const throw () {
return "队列下溢";
}
};
int* m_data; // 数组
size_t m_size; // 容量
size_t m_rear; // 后端
size_t m_front; // 前端
size_t m_counter; // 计数
};

//验证队列，先进先出
int main (void) {
try {
Queue queue (5);
queue.push (10);
queue.push (20);
queue.push (30);
queue.push (40);
queue.push (50);
// queue.push (60); //队列上溢
cout << queue.pop () << endl; // 10
queue.push (60);
cout << queue.pop () << endl; // 20
cout << queue.pop () << endl; // 30
queue.push (70);
queue.push (80);
cout << queue.pop () << endl; // 40
cout << queue.pop () << endl; // 50
cout << queue.pop () << endl; // 60
cout << queue.pop () << endl; // 70
cout << queue.pop () << endl; // 80
// queue.pop ();//队列下溢
}
catch (exception& ex) {
cout << ex.what () << endl;
return –1;
}
return 0;
}