当前位置：首页 > news >正文

【c++学习】数据结构中的栈

news 2025/6/30 15:13:51

c++栈

栈
- 代码
- - 用线性表实现栈
  - 用链表实现栈

栈

栈：先进后出
只对栈顶元素进行操作，包括新元素入栈、栈顶元素出栈和查看栈顶元素（只支持对栈顶的增、删、查）。

代码

下述代码实现了栈及其接口
包括对栈顶的增、删、查以及查看栈的大小

用线性表实现栈

#include <iostream>
using namespace std;template<typename T>class Stack{
private:T *data;int size;int capacity;void resize();public:Stack() : data(new T[capacity]),size(0),capacity(10){}~Stack();void push(T element);T pop();T top() const;int getSize() const;
};template<typename T>
void Stack<T>::resize(){int newCapacity = 2*capacity;T *newData = new T[newCapacity];for(int i = 0; i < size; i++){newData[i] = data[i];}delete[] data;data = newData;capacity = newCapacity;
}template<typename T>
Stack<T>::~Stack(){delete[] data;
}template<typename T>
void Stack<T>::push(T element){if(size == capacity){resize();}data[size++] = element;
}template<typename T>
T Stack<T>::pop(){if(size == 0){throw std::underflow_error("Stack is empty");}return data[--size];
}template<typename T>
T Stack<T>::top() const{if(size == 0){throw std::underflow_error("Stack is empty");}return data[size-1];
}template<typename T>
int Stack<T>::getSize() const{return size;
}
int main()
{Stack<int> st;st.push(1);st.push(2);st.push(3);cout << st.getSize() << endl;cout << st.top() << endl;st.pop();cout << st.getSize() << endl;cout << st.top() << endl;	return 0;
}

用链表实现栈

#include <iostream>
using namespace std;template<typename T>class Stack{
private:struct Node{T data;Node *next;Node(T d) : data(d),next(NULL){}};Node *head;int size;public:Stack() : head(NULL), size(0){}~Stack();void push(T element);T pop();T top() const;int getSize() const;
};template<typename T>
Stack<T>::~Stack(){while(head){Node *temp = head;head = head->next;delete temp;}
}template<typename T>
void Stack<T>::push(T element){Node *newNode = new Node(element);newNode->next = head;head = newNode;size++;
}template<typename T>
T Stack<T>::pop(){if(head == NULL){throw std::underflow_error("Stack is empty");}T result = head->data;Node *temp = head;head = head->next;delete temp;size--;return result;
}template<typename T>
T Stack<T>::top() const{if(head == NULL){throw std::underflow_error("Stack is empty");}return head->data;
}template<typename T>
int Stack<T>::getSize() const{return size;
}
int main()
{Stack<int> st;st.push(1);st.push(2);st.push(3);cout << st.getSize() << endl;cout << st.top() << endl;st.pop();cout << st.getSize() << endl;cout << st.top() << endl;	}