本文最后更新于101 天前,其中的信息可能已经过时,如有错误请发送邮件到big_fw@foxmail.com
顺序表实现
#include<iostream>
/*
顺序表实现,私有成员变量:大小size,容量capacity
里面的元素element,因为是顺序表实现,不需要单独实现栈顶指针head
公有成员函数:入栈,出栈,找到栈中某个元素,构造,析构
*/
using namespace std;
template<typename T>
class Stack{
private:
int size;
int capacity;
T* element;
public:
void push(T num);
void pop();
T top();
int getsize();
void printAllElement();
Stack<T>(int capacity) : size(0),capacity(capacity) {
element = new T[capacity];
}
Stack<T>() : size(0),capacity(10){
element = new T[10];
}
~Stack(){
delete[] element;
size = 0;
capacity = 0;
element = nullptr;
}
};
//入栈,先判断栈满没满,满了就扩容,没满将元素插到最后一个
template<typename T>
void Stack<T>::push(T num){
if(size == capacity){
T* new_element = new T[capacity*2];
capacity = capacity * 2;
for(int i = 0;i < size;i++){
new_element[i] = move(element[i]);
}
delete[] element;
element = new_element;
new_element = nullptr;
}
element[size] = num;
size += 1;
}
//出栈
//栈里是否还有能出栈的元素,若有,将最后插入的元素删除,size--;
template<typename T>
void Stack<T>::pop(){
if(size<1){
throw underflow_error("Stack is empty");
}else{
size--;
}
}
//获取栈顶元素
template<typename T>
T Stack<T>::top(){
return element[size-1];
}
//获取栈的大小
template<typename T>
int Stack<T>::getsize(){
return size;
}
template<typename T>
void Stack<T>::printAllElement(){
for(int i = 0;i<size;i++){
cout << element[i] << " ";
}
cout << endl;
}
void test(){
Stack<int> stack(3);
stack.push(0);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(5);
stack.pop();
stack.pop();
cout << "------------------------" << endl;
cout << stack.top() << endl;
cout << stack.getsize() << endl;
stack.printAllElement();
cout << "----------------------------" << endl;
Stack<char> stack1(5);
stack1.push('a');
stack1.push('b');
stack1.push('c');
stack1.push('d');
stack1.push('e');
cout << "------------------------" << endl;
cout << stack1.top() << endl;
cout << stack1.getsize() << endl;
stack1.printAllElement();
}
链表实现
#include<iostream>
using namespace std;
template<typename T>
struct Node{
Node<T>* next;
T data;
Node(T value) : next(nullptr),data(value){}
};
template<typename T>
class Stack{
private:
Node<T>* head;
int size;
public:
Stack() : head(nullptr),size(0){}
~Stack(){
Node<T>* cur = head;
while(cur != nullptr){
Node<T>* temp = cur;
cur = cur->next;
delete temp;
}
}
void push(T value);
void pop();
T top();
int getsize();
void printAllElement();
};
template<typename T>
void Stack<T>::push(T value){
Node<T>* new_node = new Node(value);
new_node->next = head;
head = new_node;
size++;
}
template<typename T>
void Stack<T>::pop(){
if(size <= 0){
throw underflow_error("Stack is empty");
}
Node<T>* temp = head;
head = head->next;
delete temp;
size--;
}
template<typename T>
void Stack<T>::printAllElement(){
if(size <= 0){
cout << "Stack is empty" << endl;
}
Node<T>* cur = head;
for(int i=0;i<size;++i){
cout << cur->data << " ";
cur = cur->next;
}
cout << endl;
}
void test1(){
Stack<char> s;
s.push('a');
s.push('p');
s.push('p');
s.push('0');
s.pop();
s.printAllElement();
}