本文共 2646 字,大约阅读时间需要 8 分钟。
http://blog.csdn.net/jwentao01/article/details/46765517###;
栈基本概念:
栈(stack)是限定在表尾进行插入和删除操作的线性表(或单链表)。 //只能在一段进行插入和删除,因此不存在,在中间进行插入 栈顶(top):允许插入和删除的一端。而另一端称为栈底(bottom) 空栈:不含任何数据元素的栈。 后进先出两个基本操作:
栈的插入操作(push),叫做进栈,或压栈,或入栈 删除操作(pop),叫做出栈,或弹栈 注意链栈next指针的指向,与队列不同: 如果插入一个元素,它的next指针是指向前一个已经在栈中的元素的 而队列则是,插入一个元素,其next指针是往外指,指向空。 链栈的next指针之所以这样,是方便删除操作,这一点可以在编程的过程中体会到。以下是代码:
#includeusing namespace std;typedef struct node{ int data; struct node *next;}Node;typedef struct stack{ Node *top; /**书本写法是:加一个bottom,个人感觉没什么用,反而加一个count用于表示节点数会更好*/ int count;}Link_Stack;/**创建一个空栈*/Link_Stack * Creat_stack(){ Link_Stack *p; p = new Link_Stack; /**这一步不要忘!需要给p创建空间*/ p->count = 0; p->top = NULL; return p;}/**入栈操作:push*/Link_Stack * Push_stack(Link_Stack *p,int elem){ if(NULL == p) return NULL; Node *temp; temp = new Node; temp->data = elem; temp->next = p->top; /**注意这里和队列的入队操作不同,next指向不同,为了方便出栈操作*/ p->top = temp; p->count += 1; return p;}/**出栈操作:pop*/Link_Stack * Pop_stack(Link_Stack *p){ Node *temp; temp = p->top; if(NULL == p->top) { cout << "The stack is empty." << endl; return p; } else{ p->top = p->top->next; /** temp = temp->next; 千万不能这么写,看看下一步是什么?*/ delete temp; p->count -= 1; return p; }}/**栈的遍历:输出栈*/int Show_stack(Link_Stack *p){ Node *temp; temp = p->top; if(NULL == p->top) { cout << "The stack is empty." << endl; return 0; } while(NULL != temp) { cout << temp->data << ' '; temp = temp->next; } cout << endl; return 0;}int main(){ int i = 5; int elem; Link_Stack *p; p = Creat_stack(); while(i--) { cin >> elem; Push_stack(p,elem); } cout << "空栈插入5个元素后:" << endl; Show_stack(p); cout << "删除3个元素后:" << endl; for(i = 3;i--;) { Pop_stack(p); } Show_stack(p); cout << "count:" << p->count << endl; cout << "删除2个元素后:" << endl; for(i = 2;i--;) { Pop_stack(p); } Show_stack(p); cout << "count:" << p->count << endl; Push_stack(p,6); cout << "插入元素6后:" << endl; Show_stack(p); cout << "count:" << p->count << endl; return 0;}
结果如下:
/点滴积累,我的一小步O(∩_∩)O~/