所谓栈，就是先进后出规则的实现，这种数据结构在DFS等算法体现的较为明显，因为课程要求不得不进行各种数据结构实现代码整理，就发出来与大家分享。下面有两种实现方法一个是基于数组实现的，另一个是基于链表实现的。
基于数组实现
源码
main.cpp
//main.cpp : 定义控制台应用程序的入口点。
#include <iostream>
using namespace std;
#include "UTILITY.h"
#include "stack.h"
//typedef double Stack_entry;
int main()
{
int n;
float item;
Stack numbers;
cout << " Type in an integer n followed by n floating point numbers.\n"
<< " The numbers will be printed in reverse order." << endl;
cin >> n;//输入字符数目
for (int i = 0; i < n; i++) {
cin >> item;
if (numbers.push(item) == overflow)
cout << "\nThe stack is full." << endl;
}
cout << "\n\n";
while (!numbers.empty()) {
numbers.top(item);
numbers.pop();
cout << item << " ";
}
cout << endl;
return 0;
}STACK.h
const int maxstack = 10; // small value for testing
typedef float Stack_entry; // The program will use stacks with float entries.
enum Error_code {
success, fail, range_error, underflow, overflow, fatal,
not_present, duplicate_error, entry_inserted, entry_found,
internal_error
};
class Stack {
public:
Stack();
bool empty() const;
Error_code pop();
Error_code top(Stack_entry& item) const;
Error_code push(const Stack_entry& item);
private:
int count;
Stack_entry entry[maxstack];
};
Stack::Stack()
/*
Pre: None.
Post: The stack is initialized to be empty.
*/
{
count = 0;
}
Error_code Stack::push(const Stack_entry& item)
/*
Pre: None.
Post: If the Stack is not full, item is added to the top
of the Stack. If the Stack is full,
an Error_code of overflow is returned and
the Stack is left unchanged.
*/
{
Error_code outcome = success;
if (count >= maxstack)
outcome = overflow;
else
entry[count++] = item;
return outcome;
}
Error_code Stack::top(Stack_entry& item) const
/*
Pre: None.
Post: If the Stack is not empty, the top of
the Stack is returned in item. If the Stack
is empty an Error_code of underflow is returned.
*/
{
Error_code outcome = success;
if (count == 0)
outcome = underflow;
else
item = entry[count - 1];
return outcome;
}
bool Stack::empty() const
/*
Pre: None.
Post:
If the Stack is empty, true is returned.
Otherwise false is returned.
*/
{
bool outcome = true;
if (count > 0) outcome = false;
return outcome;
}
Error_code Stack::pop()
/*
Pre: None.
Post: If the Stack is not empty, the top of
the Stack is removed. If the Stack
is empty, an Error_code of underflow is returned.
*/
{
Error_code outcome = success;
if (count == 0)
outcome = underflow;
else --count;
return outcome;
}基于链表实现
源码
main.cpp
#include<iostream>
#include"Stack.h"
using namespace std;
int main()
{
Stack s;
s.push('a');
s.push('b');
char c;
s.top(c);
cout << c;
return 0;
}Stack.h
#pragma once
#include"Node.h"
#pragma once
enum Error_code {
success, fail, range_error, underflow,
overflow, fatal, not_present, duplicate_error,
entry_inserted, entry_found, internal_error
};
class Stack {
public:
// Standard Stack methods
Stack() { top_node = nullptr; };
bool empty() const;
Error_code push(const Stack_entry& item);
Error_code pop();
Error_code top(Stack_entry& item) const;
// Safety features for linked structures
~Stack();
Stack(const Stack& original);
void operator =(const Stack& original);
protected:
Node* top_node;
};
Error_code Stack::push(const Stack_entry& item)
/* Post: Stack_entry item is added to the top of the Stack; returnssuccess or returns
a code of overflow if dynamic memory is exhausted. */ {
Node* new_top = new Node(item, top_node);//倒着来
if (new_top == NULL)
return overflow;
new_top->next=top_node;
top_node = new_top;
return success;
}
Error_code Stack::pop()
/* Post: The top of the Stack is removed. If the Stack is empty the method returns
underflow; otherwise it returns success. */ {
Node* old_top = top_node;
if (top_node == NULL)//空栈
return underflow;
top_node = old_top->next;
delete old_top;//防止内存泄漏
return success;
}
void Stack::operator = (const Stack& original) //深拷贝 Overload assignment
/*
Post: The Stack is reset as a copy of Stack original.
*/
{
while (!empty()) // Clean out old Stack entries
pop();
Node* new_top, * new_copy, * original_node = original.top_node;
if (original_node == NULL)
new_top = NULL;
else { // Duplicate the linked nodes
new_copy = new_top = new Node(original_node->entry);
while (original_node->next != NULL) {//正插（因为只能从栈顶开始，负负为正）
original_node = original_node->next;
new_copy->next = new Node(original_node->entry);
new_copy = new_copy->next;
}
}
top_node = new_top; // and replace them with new entries.
}
Stack::~Stack() // Destructor
/*
Post: The Stack is cleared.
*/
{
while (!empty())
pop();
}
bool Stack::empty() const
{
return top_node == NULL;
}
Stack::Stack(const Stack& original) //深拷贝 copy constructor
/*
Post: The Stack is initialized as a copy of Stack original.
*/
{
Node* new_copy, * original_node = original.top_node;
if (original_node == NULL)
top_node = NULL;
else { // Duplicate the linked nodes.
top_node = new_copy = new Node(original_node->entry);
while (original_node->next != NULL) {
original_node = original_node->next;
new_copy->next = new Node(original_node->entry);
new_copy = new_copy->next;
}
}
}
Error_code Stack::top(Stack_entry& item) const {
if (!top_node)
return underflow;
else
item = top_node->entry;
return success;
}Node.h
#pragma once
#include <cstddef>
typedef char Stack_entry;
typedef Stack_entry Node_entry;
class Node {
public:
Node_entry entry;
Node* next;
Node();
Node(Node_entry item, Node* add_on = NULL);
};
Node::Node()
{
next = NULL;
}
Node::Node(Node_entry item, Node* add_on)
{
entry = item;
next = add_on;
}