Aris

栈

2015/05/13 数据结构

栈的定义

栈是限定仅在表尾进行插入或删除操作的线性表。对栈来说，表尾端有其特殊的含义，称为栈顶(top)，相应的，表头端称为栈底(bottom)，不含元素的空表称为空栈。栈又称为后进先出(last in first out)的线性表，

栈的表示与实现

和线性表类似，栈也有两种存储表示方法。

顺序栈

顺序栈，即栈的存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。一般来说，在初始化空栈时不应限定栈的最大容量，一个较合理的做法是先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。

顺序栈的存储结构：

typedef struct{
	SElemType *base;   //在栈构造之前和销毁之后 base的值为NULL
	SElemType *top;
	int stacksize;
}SqStack;

其中stacksize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定的初始化分配量进行第一次存储分配，base可称为栈底指针，在顺序栈中，它始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在。称top为栈顶指针，其初始值指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1。因此非空栈中的栈顶指针始终在栈顶元素的下一个位置上。

顺序栈的完整代码（C语言）：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

//函数结果状态代码
#define OK           1
#define ERROR        0

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

using namespace std;

typedef int SElemType;     //定义数据类型
typedef int Status;  

//顺序栈的存储结构
typedef struct{
	SElemType *base;       //在栈构造之前和销毁之后 base的值为NULL
	SElemType *top;
	int stacksize;
}SqStack;

//初始化栈
Status InitStack(SqStack &s){
	s.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!s.base) exit(OVERFLOW);
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return OK;
}

//获取栈顶元素
Status GetTop(SqStack s,SElemType &e){
	if(s.top==s.base) return ERROR;
	e=*(s.top-1);
	return OK;
}

//压入操作
Status Push(SqStack &s,SElemType e){
	if(s.top-s.base>=s.stacksize){   //栈满 追加存储空间
		s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!s.base) exit(OVERFLOW);
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++=e;
	return OK;
}

//弹出操作
Status Pop(SqStack &s,SElemType &e){
	if(s.top==s.base) return ERROR;
	e=*--s.top;
	return OK;
}

//打印栈
void printStack(SqStack s){
	SElemType *p;
	p=s.base;
	while(p!=s.top){
		cout<<*p<<" ";
		p++;
	}
	cout<<endl;
}

int main(){
	SqStack s;
	InitStack(s);
	Push(s,1);
	Push(s,2);
	Push(s,3);
	Push(s,4);
	printStack(s);
	int e;
	for(int i=0;i<4;i++){
		Pop(s,e);
		cout<<e<<" ";
	}
	cout<<endl;
	system("pause");
}

顺序栈的完整代码（C++语言）：

#include <iostream>
using namespace std;

struct Stack{
	int maxsize;
	int *top;
	int *base;
	Stack(){
		maxsize=100;
		base=new int[maxsize];
		top=base;
	}
	void Push(int e){
		*top++=e;
	}
	int Pop(){
		if(top==base)
			return -1;
		else{
			return *--top;
		}
	}
	int getTop(){
		if(base==top)
			return -1;
		else
			return *(top-1);
	}
	bool empty(){
		return (base==top);
	}
};

int main(){
	Stack s;
	s.Push(1);
	s.Push(2);
	s.Push(3);
	cout<<s.Pop()<<endl;
	cout<<s.getTop()<<endl;
	system("pause");
}
链式栈

栈可以通过链式进行表示，由于栈的操作是线性表操作的特例，链栈的操作易于实现。

#include <iostream>
using namespace std;

struct StackNode{
	int val;
	struct StackNode *next;
	StackNode(int n):val(n){
		next=NULL;
	}
};

struct Stack{
	StackNode *top;
	StackNode *base;
	Stack(){
		base=new StackNode(0);
		top=base;
	}
	void Push(int n){
		StackNode *temp=new StackNode(n);
		temp->next=top;
		top=temp;
	}
	int Pop(){
		if(top==base) return -1;
		int n=top->val;
		StackNode *p=top;
		top=top->next;
		delete p;
		return n;
	}
	int getTop(){
		if(top==base) return -1;
		return top->val;
	}
	bool empty(){
		return (top==base);
	}
};

int main(){
	Stack s;
	s.Push(1);
	s.Push(2);
	s.Push(3);
	cout<<s.Pop()<<endl;
	cout<<s.getTop()<<endl;
	system("pause");
}

Search

    Post Directory