栈的两种实现

栈的两种实现

1.在线性表中，栈是一种简单但是十分重要的数据结构，栈内元素先进后出，元素出栈，入栈，以及栈内查找等。在c++程序中，程序在编译之后被分为了五大块，其中就有栈区。栈区存储着程序中的局部变量等重要的数据，但是系统内提供的栈和我们自己实现的栈有一点区别。系统栈的内存分布是，栈顶指针一直指在高地址，元素入栈之后指针的值会减小，所以内存是从高到底排列，但是对于我们自己实现的栈是相反的。这里我没有使用栈顶指针，我使用的是整形数据来指示当前栈内的元素数量，替代了栈顶指针的作用。本次实践只是简单的模拟栈的基本操作，采用数组与链表这两种线性表分别实现栈。但是对于一些其他的操作，比如说栈内查找，以及在系统栈内，系统会提供一个EBP指针，可以遍历当前寄存器来获取当前栈内所有元素，而栈顶指针ESP始终指在栈顶位置。这一点本次实验没有模拟。以下是详细代码。

/*栈的基本实现*/ #include"stdafx.h" #include #include #define MaxSize 64 using namespace std; /*基于数组实现的栈*/ class stack { private:     int data[MaxSize];     int top = -1;//栈空的时候设置为-1； public:     stack() {};//默认构造函数     int push(int data);//元素入栈     int pop();//元素出栈     bool isEmpty();//是否为空栈     void print_all();//遍历输出     void clear();//将栈置空 }; /*具体实现*/ bool stack::isEmpty() {     if (top < 0) {         cout << "栈是空栈" << endl;         return true;     }     return false; } int stack::push(int a) {     if (top > MaxSize - 1) {         cout << "the stack is full!" << endl;         return 0;     }     else {         top++;         data[top] = a;     }     return 0; } int stack::pop() {     if (top < 0) {         cout << "栈已经是空栈" << endl;         return 0;     }     else {         int k = data[top];         top--;         return k;     } } void stack::print_all() {     for (int i = 0; i < top; i++) {         cout << setw(4) << data[i];     } } void stack::clear() {     top = -1; } /*基于链表实现的栈*/ typedef struct link {     int data;//数据域     struct link*next;//指向下一节点的指针     link(int a) {         data = a;     } }link,*linknode; class link_stack{ private:     int top = -1;//栈顶标记；     linknode head = NULL;//链表头部指针     linknode tail = NULL; public:     link_stack();//默认构造函数     int push(int data);//元素入栈     int pop();//元素出栈     int clear();//将栈置空;     int isEmpty();//判断是否非空     void print_all();//遍历输出栈内所有元素 }; link_stack::link_stack() {     /*构造函数里面首先做一部分工作*/      head = new link(0);      tail = head;//链表的头指针初始化为0；尾部此时等于头部 } int link_stack::push(int data) {     linknode p = new link(data);     //此时的插入应该从头部插入     p->next = tail;//当前元素指向尾部元素     head->next = p;//头部指针指向当前元素     tail = p;//尾部元素更新为当前元素     top++;     return 0; } int link_stack::pop() {     linknode p = head->next;     if (p == NULL) {         cout << "栈已经是空栈" << endl;     }     //删除当前元素     head->next = p->next;//将head的指向指向p的下一个元素；     delete p;     top--;     if (top < 0) {         return 0;     }     return 0; } int link_stack::clear() {     //删除栈内所有的节点     linknode p = head->next;     if (p == NULL) {         cout << "当前栈为空栈" << endl;     }     else {         while (p)         {             linknode q = p;             delete q;             p = p->next;         }     }     return 0; } int link_stack::isEmpty() {     if (head->next == NULL) {         cout << "该栈是一个空栈" << endl;         return 1;     }     return 0;//非空栈 } void link_stack::print_all() {     linknode p=head->next;     if (top<0) {         cout << "该栈内没有任何元素" << endl;     }     int t = top;     while (t!=-1) {         cout << setw(4) << p->data;         p = p->next;         t--;     } } int main() {     cout << "*********************************" << endl;     cout << "基于数组实现的栈" << endl;     stack s;     for (int i = 0; i < 10 && i < MaxSize; i++) {         s.push(i);     }     s.print_all();     s.pop();     s.print_all();     s.clear();     cout << "**************************************" << endl;     cout << "基于链表实现的栈" <

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。