首页 笔记 数据结构

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

c++ 语言，链栈实现

实验内容：

  1. 编程实现栈的如下功能：
    （1）建立一个长度为 n 的顺序栈，元素类型可自行定义，并输出栈中各元素值。
    （2）将数据元素 e 入栈，并输出入栈后的顺序栈中各元素值。
    （3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。
  2. 编程实现队列的如下功能：
    （1）建立一个长度为 n 的循环队列，元素类型可自行定义，并输出队列中各元素值。
    （2）将数据元素 e 入队，并输出入队后的队列中各元素值。
    （3）将循环队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。
  3. 编程实现链式栈的如下功能
    建立长度为 n 的链式栈，元素类型可自行定义，实现栈的初始化、进栈、出栈等典型操作。

整体上，一是实现顺序栈和链栈的基本操作：入栈操作（Push）、出栈操作（Pop）、取栈顶元素（Top）、判断栈空（IsEmpty）、判断栈满（IsFull）、获取栈中元素个数（Size）、展示栈中所有元素（PrintStack）、清空栈中所有元素（Clear）。二是实现队列的基本操作：入队操作（Push）、出队操作（Pop）、取队首元素（Front）、判断队空（IsEmpty）、判断队满（IsFull）、获取队中元素个数（Size）、展示队中所有元素（PrintQueue）、清空队中所有元素（Clear）。依旧是封装一个模板类。初始化和销毁操作在构造函数和析取函数中实现。

(目录)

# 顺序栈

# 顺序栈操作类定义

// 顺序栈定义
template <class T> class myStack1 {
private:
 int MaxSize;  // 堆栈容量
 T* Data;   // 数据
 int top;  // 记录栈顶元素 为栈顶元素下标后一个下标，为空时 top 为 0
public:
 myStack1(int maxsize = 100);  // 构造函数 分配空间
 ~myStack1();       // 析构函数 回收空间
 void PrintStack();     // 展示顺序栈中所有元素
 void Push(T data); // 入栈操作，top 值加一，存储元素 item 在栈顶
 T Pop();   // 出栈操作，将元素弹出返回，Top 值减一
 T Top();   // 取栈顶元素，不弹出
 int Size();   // 获取堆栈元素数量
 bool IsEmpty();  // 判断栈空与否
 bool IsFull();  // 判断栈满与否
};

# 主要操作

# (1) 构造函数和析构函数

template <class T>
myStack1<T>::myStack1(int maxsize) : MaxSize(maxsize), top(0) {
 Data = new T[maxsize];
};
template <class T> myStack1<T>::~myStack1() {
 if (Data)
  delete[] Data;
}

# (2) 判断栈空栈满

// 判断栈空与否
template <class T> bool myStack1<T>::IsEmpty() {
 return top == 0;
}
// 判断栈满与否
template <class T> bool myStack1<T>::IsFull() {
 return top == MaxSize;
}

# (3) 入栈操作

存储元素 data 在栈顶，Top 值加一

template <class T> void myStack1<T>::Push(T data) {
 if (IsFull()) {
  cout << "error:Failed to Push,The Stack is Full!" << endl;
 } else {
  Data[top++] = data;
 }
}

# (4) 取栈顶元素

取栈顶元素，不弹出

template <class T> T myStack1<T>::Top() {
 if (IsEmpty()) {
  cout << "error:The Top isn't existed, The Stack is Empty!" << endl;
  return error;  // ERROR 为 T 类型中的特殊值
 } else {
  return Data[top - 1];
 }
}

# (5) 获取堆栈元素数量

template <class T> int myStack1<T>::Size() {
 return top;
}

# (6) 出栈操作

弹出栈顶元素，Top 值减一

template <class T> T myStack1<T>::Pop() {
 if (IsEmpty()) {
  cout << "error:Failed to Pop, The Stack is Empty!" << endl;
  return error;  // ERROR 为 T 类型中的特殊值
 } else {
  T temp = Data[--top];
  return temp;
 }
}

# (7) 展示顺序栈中所有元素

template <class T> void myStack1<T>::PrintStack() {
 if (IsEmpty())
  cout << "This Stack is empty!" << endl;
 for (int i = 0; i < top; ++i) {
  cout << "The " << i + 1 << "th Data is:";
  cout << Data[i] << endl;
 }
 cout << "The Stack has " << top << " elements in total." << endl;
}

# 完整代码

// 顺序栈
#include <bits/stdc++.h>
#define error -1
using namespace std;
// 顺序栈定义
template <class T> class myStack1 {
private:
 int MaxSize;  // 堆栈容量
 T* Data;   // 数据
 int top;  // 记录栈顶元素 为栈顶元素下标后一个下标，为空时 top 为 0
public:
 myStack1(int maxsize = 100);  // 构造函数 分配空间
 ~myStack1();       // 析构函数 回收空间
 void PrintStack();     // 展示顺序栈中所有元素
 void Push(T data); // 入栈操作，top 值加一，存储元素 item 在栈顶
 T Pop();   // 出栈操作，将元素弹出返回，Top 值减一
 T Top();   // 取栈顶元素，不弹出
 int Size();   // 获取堆栈元素数量
 bool IsEmpty();  // 判断栈空与否
 bool IsFull();  // 判断栈满与否
};
// 顺序栈操作类实现
// 构造函数 分配空间
template <class T>
myStack1<T>::myStack1(int maxsize) : MaxSize(maxsize), top(0) {
 Data = new T[maxsize];
};
// 析构函数 释放空间
template <class T> myStack1<T>::~myStack1() {
 if (Data)
  delete[] Data;
}
//(1) 判断栈空与否
template <class T> bool myStack1<T>::IsEmpty() {
 return top == 0;
}
//(2) 判断栈满与否
template <class T> bool myStack1<T>::IsFull() {
 return top == MaxSize;
}
//(3) 入栈操作
// 存储元素 data 在栈顶，Top 值加一
template <class T> void myStack1<T>::Push(T data) {
 if (IsFull()) {
  cout << "error:Failed to Push,The Stack is Full!" << endl;
 }
 else {
  Data[top++] = data;
 }
}
//(4) 取栈顶元素，不弹出
template <class T> T myStack1<T>::Top() {
 if (IsEmpty()) {
  cout << "error:The Top isn't existed, The Stack is Empty!" << endl;
  return error;  // ERROR 为 T 类型中的特殊值
 }
 else {
  return Data[top - 1];
 }
}
//(5) 获取堆栈元素数量
template <class T> int myStack1<T>::Size() {
 return top;
}
//(6) 出栈操作
// 弹出栈顶元素，Top 值减一
template <class T> T myStack1<T>::Pop() {
 if (IsEmpty()) {
  cout << "error:Failed to Pop, The Stack is Empty!" << endl;
  return error;  // ERROR 为 T 类型中的特殊值
 }
 else {
  T temp = Data[--top];
  return temp;
 }
}
//(7) 展示顺序栈中所有元素
template <class T> void myStack1<T>::PrintStack() {
 if (IsEmpty())
  cout << "This Stack is empty!" << endl;
 for (int i = 0; i < top; ++i) {
  cout << "The " << i + 1 << "th Data is:";
  cout << Data[i] << endl;
 }
 cout << "The Stack has " << top << " elements in total." << endl;
}
// 主函数中调用的函数 (测试用)
template <class T> void Stack_Push(myStack1<T>& S) {
 T data;
 cout << "请输入要入栈的元素:";
 cin >> data;
 S.Push(data);
 cout << "------------- After Push, Stack S ---------------" << endl;
 S.PrintStack();
}
template <class T> void Stack_Pop(myStack1<T>& S) {
 T data = S.Pop();
 if (data != error) {
  cout << "出栈元素为:";
  cout << data << endl;
 }
 cout << "------------- After Pop, Stack S ---------------" << endl;
 S.PrintStack();
}
template <class T> void Stack_Top(myStack1<T>& S) {
 T data = S.Top();
 if (data != error) {
  cout << "栈顶元素为:";
  cout << data << endl;
 }
}
template <class T> void Stack_Size(myStack1<T>& S) {
 cout << "该堆栈中元素个数为:" << S.Size() << endl;
}
template <class T> void Stack_PrintStack(myStack1<T>& S) {
 cout << "---------------------- Stack S --------------------" << endl;
 S.PrintStack();
}
int main() {
 int n;
 cout << "输入n,建立长度为n的顺序栈:";
 cin >> n;
 myStack1<int> S(n);
 cout << "输入n个元素:" << endl;
 for (int i = 0; i < n; ++i) {
  int data;
  cin >> data;
  S.Push(data);
 }
 cout << "1 入栈操作" << endl;
 cout << "2 出栈操作" << endl;
 cout << "3 取栈顶元素" << endl;
 cout << "4 取堆栈元素个数" << endl;
 cout << "5 输出顺序栈中所有元素" << endl;
 cout << "6 结束" << endl;
 while (1) {
  int choice;
  cout << "菜单选择:";
  cin >> choice;
  getchar();
  switch (choice) {
   case 1: Stack_Push(S); break;
   case 2: Stack_Pop(S); break;
   case 3: Stack_Top(S); break;
   case 4: Stack_Size(S); break;
   case 5: Stack_PrintStack(S); break;
   case 6: break;
   default: cout << "输入错误，请重新输入";
  }
  if (choice == 6)
   exit(0);
  cout << "按回车键继续…" << endl;
  getchar();
 };
 return 0;
}
# 链栈
# 链栈结点定义
template <class T> class SNode {
private:
 SNode* next;  // 指针
 T Data;    // 数据
public:
 friend class Stack<T>;
 SNode() { next = nullptr; }  // 空结点
 SNode(T data) {     // 有数据的结点
  Data = data;
  next = nullptr;
 }
 void showdata() { cout << Data << endl; }  // 展示该结点数据
};
# 链栈操作类定义
template <class T> class Stack {
private:
 int maxsize;  // 堆栈容量
 SNode<T>* head;  // 头指针 带空头结点，所以栈顶元素一直为 head->next
public:
 Stack(int size = 100); // 构造函数 分配空间，空头结点
 ~Stack();    // 析构函数 回收空间
 void PrintStack();  // 展示栈中所有元素
 void Clear();   // 清空栈中所有元素
 void Push(T data);  // 入栈操作 存储元素 data 在栈顶
 T Pop();   // 出栈操作 弹出栈顶元素并将其在栈中删除
 T Top();   // 取栈顶元素，不弹出
 int Size();   // 获取堆栈元素数量
 bool IsEmpty();  // 判断栈空与否
 bool IsFull();  // 判断栈满与否
};
# 主要操作
# (1) 构造函数和析构函数
// 构造函数 分配空间，空头结点
template <class T> Stack<T>::Stack(int size) : maxsize(size) {
 head = new SNode<T>;
 head->next = nullptr;
};
// 析构函数 释放空间
template <class T> Stack<T>::~Stack() {
 while (head->next) {
  Pop();
 }
 if (head)
  delete head;
}
# (2) 判断栈空栈满
template <class T> bool Stack<T>::IsEmpty() {
 if (head->next) return false;
 else return true;
}
template <class T> bool Stack<T>::IsFull() {
 if (Size() < maxsize) return false;
 else return true;
}
# (3) 入栈操作
存储元素 data 在栈顶
template <class T> void Stack<T>::Push(T data) {
 if (IsFull()) {
  cout << "error:Failed to Push,The Stack is Full!" << endl;
 } else {
  SNode<T>* p = new SNode<T>;
  p->Data = data;
  p->next = head->next;
  head->next = p;
 }
}
# (4) 取栈顶元素
template <class T> T Stack<T>::Top() {
 if (IsEmpty()) {
  cout << "error:The Top isn't existed, The Stack is Empty!" << endl;
  return error;
 } else {
  T temp = head->next->Data;
  return temp;
 }
}
# (5) 获取堆栈元素数量
template <class T> int Stack<T>::Size() {
 int cnt = 0;
 SNode<T>* p = head;
 while (p->next) {
  cnt++;
  p = p->next;
 }
 return cnt;
}
# (6) 出栈操作
弹出栈顶元素并将其在栈中删除
template <class T> T Stack<T>::Pop() {
 if (IsEmpty()) {
  cout << "error:Failed to Pop, The Stack is Empty!" << endl;
  return error;
 } else {
  SNode<T>* temp = head->next;
  T TopData = temp->Data;
  head->next = temp->next;
  delete temp;
  return TopData;
 }
}
# (7) 展示栈中所有元素
弹出栈顶元素并将其在栈中删除
template <class T> T Stack<T>::Pop() {
 if (IsEmpty()) {
  cout << "error:Failed to Pop, The Stack is Empty!" << endl;
  return error;
 } else {
  SNode<T>* temp = head->next;
  T TopData = temp->Data;
  head->next = temp->next;
  delete temp;
  return TopData;
 }
}
# (8) 清空栈中所有元素
//(8) 清空栈中所有元素
template <class T> void Stack<T>::Clear() {
 while (head->next) {
  Pop();
 }
}
# 完整代码
// 链栈
#include <bits/stdc++.h>
#define error -1
using namespace std;
template <class T> class Stack;
// 链栈结点定义
template <class T> class SNode {
private:
 SNode* next;  // 指针
 T Data;    // 数据
public:
 friend class Stack<T>;
 SNode() { next = nullptr; }  // 空结点
 SNode(T data) {     // 有数据的结点
  Data = data;
  next = nullptr;
 }
 void showdata() { cout << Data << endl; }  // 展示该结点数据
};
// 链栈操作类定义
template <class T> class Stack {
private:
 int maxsize;  // 堆栈容量
 SNode<T>* head;  // 头指针 带空头结点，所以栈顶元素一直为 head->next
public:
 Stack(int size = 100); // 构造函数 分配空间，空头结点
 ~Stack();    // 析构函数 回收空间
 void PrintStack();  // 展示栈中所有元素
 void Clear();   // 清空栈中所有元素
 void Push(T data);  // 入栈操作 存储元素 data 在栈顶
 T Pop();   // 出栈操作 弹出栈顶元素并将其在栈中删除
 T Top();   // 取栈顶元素，不弹出
 int Size();   // 获取堆栈元素数量
 bool IsEmpty();  // 判断栈空与否
 bool IsFull();  // 判断栈满与否
};
// 链栈操作类实现
// 构造函数 分配空间，空头结点
template <class T> Stack<T>::Stack(int size) : maxsize(size) {
 head = new SNode<T>;
 head->next = nullptr;
};
// 析构函数 释放空间
template <class T> Stack<T>::~Stack() {
 while (head->next) {
  Pop();
 }
 if (head)
  delete head;
}
//(1) 判断栈空与否
template <class T> bool Stack<T>::IsEmpty() {
 if (head->next)
  return false;
 else
  return true;
}
//(2) 判断栈满与否
template <class T> bool Stack<T>::IsFull() {
 if (Size() < maxsize)
  return false;
 else
  return true;
}
//(3) 入栈操作
// 存储元素 data 在栈顶
template <class T> void Stack<T>::Push(T data) {
 if (IsFull()) {
  cout << "error:Failed to Push,The Stack is Full!" << endl;
 }
 else {
  SNode<T>* p = new SNode<T>;
  p->Data = data;
  p->next = head->next;
  head->next = p;
 }
}
//(4) 取栈顶元素，不弹出
template <class T> T Stack<T>::Top() {
 if (IsEmpty()) {
  cout << "error:The Top isn't existed, The Stack is Empty!" << endl;
  return error;
 }
 else {
  T temp = head->next->Data;
  return temp;
 }
}
//(5) 获取堆栈元素数量
template <class T> int Stack<T>::Size() {
 int cnt = 0;
 SNode<T>* p = head;
 while (p->next) {
  cnt++;
  p = p->next;
 }
 return cnt;
}
//(6) 出栈操作
// 弹出栈顶元素并将其在栈中删除
template <class T> T Stack<T>::Pop() {
 if (IsEmpty()) {
  cout << "error:Failed to Pop, The Stack is Empty!" << endl;
  return error;
 }
 else {
  SNode<T>* temp = head->next;
  T TopData = temp->Data;
  head->next = temp->next;
  delete temp;
  return TopData;
 }
}
//(7) 展示栈中所有元素
template <class T> void Stack<T>::PrintStack() {
 if (IsEmpty())
  cout << "This Stack is empty!" << endl;
 SNode<T>* p = head;
 int cnt = 0;
 while (p->next) {
  ++cnt;
  p = p->next;
  cout << "The " << cnt << "th Data is:";
  cout << p->Data << endl;
 }
 cout << "The Stack has " << Size() << " elements in total." << endl;
}
//(8) 清空栈中所有元素
template <class T> void Stack<T>::Clear() {
 while (head->next) {
  Pop();
 }
}
// 主函数中调用的函数 (测试用)
template <class T> void Stack_Push(Stack<T>& S) {
 T data;
 cout << "请输入要入栈的元素:";
 cin >> data;
 getchar();
 S.Push(data);
 cout << "------------- After Push, Stack S ---------------" << endl;
 S.PrintStack();
}
template <class T> void Stack_Pop(Stack<T>& S) {
 T data = S.Pop();
 if (data != error) {
  cout << "出栈元素为:";
  cout << data << endl;
 }
 cout << "------------- After Pop, Stack S ---------------" << endl;
 S.PrintStack();
}
template <class T> void Stack_Top(Stack<T>& S) {
 T data = S.Top();
 if (data != error) {
  cout << "栈顶元素为:";
  cout << data << endl;
 }
}
template <class T> void Stack_Size(Stack<T>& S) {
 cout << "该堆栈中元素个数为:" << S.Size() << endl;
}
template <class T> void Stack_PrintStack(Stack<T>& S) {
 cout << "---------------------- Stack S --------------------" << endl;
 S.PrintStack();
}
template <class T> void Stack_ClearStack(Stack<T>& S) {
 S.Clear();
 cout << "成功清空！" << endl;
}
int main() {
 int n;
 cout << "输入n,建立长度为n的链栈:";
 cin >> n;
 Stack<int> S(n);
 cout << "输入n个元素:" << endl;
 for (int i = 0; i < n; ++i) {
  int data;
  cin >> data;
  S.Push(data);
 }
 cout << "1 入栈操作" << endl;
 cout << "2 出栈操作" << endl;
 cout << "3 取栈顶元素" << endl;
 cout << "4 取堆栈元素个数" << endl;
 cout << "5 输出栈中所有元素" << endl;
 cout << "6 清空栈中所有元素" << endl;
 cout << "7 结束" << endl;
 while (1) {
  int choice;
  cout << "菜单选择:";
  cin >> choice;
  getchar();
  switch (choice) {
   case 1: Stack_Push(S); break;
   case 2: Stack_Pop(S); break;
   case 3: Stack_Top(S); break;
   case 4: Stack_Size(S); break;
   case 5: Stack_PrintStack(S); break;
   case 6: Stack_ClearStack(S); break;
   case 7: break;
   default: cout << "输入错误，请重新输入";
  }
  if (choice == 7)
   exit(0);
  cout << "按回车键继续…" << endl;
  getchar();
 };
 return 0;
}