1.栈
1.栈的定义:栈作为一种限定性的线性表,是将线性表的插入和删除运算限制为仅在表的一端进行,通常将表中允许进行插入.删除操作的一端称为栈顶,因此栈顶的当前位置是动态变化的,它是由一个称为栈顶指针的位置指示器指示,同时标的另一端称为栈底,当栈中没有元素时称为空栈,栈的插入操作被形象的称为进栈或入栈. ADT stack 数据元素:可以是任意类型的数据,但必须属于同一个数据对象. 结论关系:栈中的数据元素之间是线性关系; 基本操作:
- InitStack(S)
操作前提:S为未初始化的栈; 操作结果:将S初始化为空栈.
- ClearStack(S)
操作前提:栈S已经存在; 操作结果:将栈S置为空栈;
- IsEmpty(S)
操作前提:栈S已经存在; 操作结果:判栈是否为空,若栈空返回 TRUE,否则返回FALSE;
- Push(S,x)
操作前提:栈S已经存在; 操作结果:在S的栈顶插入元素,若栈未满,将x插入栈顶位置,返回TRUE,若栈已满,返回FALSE.
- Pop(S,x)
操作前提:栈S已经存在; 操作结果:删除栈S的顶部元素,并用x带回该值,返回TRUE,若栈为空,返回 FALSE.
- GetTop(S,x)
操作前提:栈S已经存在. 操作结果:取栈顶部的元素赋给x所指的单元,与Pop(S,x)不同的是GetTop(S,x)不改变栈顶的位置. 2.顺序栈:顺序栈存储结构实现的栈,即用一组地址连续的存储单元依次存放自栈底到栈顶的元素.同时由于栈操作的特殊性,还必须附设一个位置指针Top(栈顶指针)来动态的指示栈顶元素在顺序栈中位置.通常以top=-1表示空栈, 看个例子:
#include <stdio.h>
#define Stack_size 50
#define FALSE 0
#define TRUE 1
typedef int StackElementType;
typedef struct
{
StackElementType elem[Stack_size]; // 用来存放栈中元素的一维数组
int top; //用来存放栈顶元素的下标,top=-1表示空栈
}SeqStack;
//初始化一个空栈
void InitStack(SeqStack *S)
{
S->top=-1;
}
//清空栈
void ClearStack(SeqStack *S)
{
S->top=-1;
}
int IsEmpty(SeqStack *S)
{
if(S->top==-1)
{
return TRUE;
}
return FALSE;
}
int IsFull(SeqStack *S)
{
if(S->top==Stack_size-1)
{
return TRUE;
}
return FALSE;
}
int Push(SeqStack *S,StackElementType x)
{
if(!IsFull(S)) //判断栈是否满
{
S->top++;
S->elem[S->top]=x;
return TRUE;
}
return FALSE;
}
int Pop(SeqStack *S,StackElementType *x)
{
if(!IsEmpty(S)) //栈是否为空
{
*x=S->elem[S->top];
S->top--;
//printf("%d",*x);
return TRUE;
}
return FALSE;
}
int GetTop(SeqStack *S,StackElementType *x) //得到栈顶元素,但top不动
{
if(!IsEmpty)
{
*x=S->elem[S->top];
return TRUE;
}
return FALSE;
}
int main()
{
int i,x;
SeqStack S;
InitStack(&S);
for(i=0;i<10;i++)
{
printf("请输入入栈元素:");
scanf("%d",&x);
Push(&S,x);
}
printf("出栈:\n");
while(!IsEmpty(&S))
{
Pop(&S,&x);
printf("%3d",x);
}
printf("\n");
return 0;
}
结果:
yang@liu:~/shujujiegou2$ ./a.out 请输入入栈元素:1 请输入入栈元素:2 请输入入栈元素:3 请输入入栈元素:4 请输入入栈元素:5 请输入入栈元素:6 请输入入栈元素:7 请输入入栈元素:8 请输入入栈元素:9 请输入入栈元素:10 出栈: 10 9 8 7 6 5 4 3 2 1
3.在顺序栈的共享技术中最长用的是两个栈的共享技术即双端栈,主要利用栈的栈底位置不变,而栈顶位置动态变化,首先申请一个共享数组S[Stack_Size];将两个栈的栈底分别放在一维数组的两端,分别是Stack_Size,-1;由于两个栈顶动态变化,形成互补,使得每个栈的可用空间与实际使用的需求有关:看个例子:
#include <stdio.h>
#define Stack_Size 50
typedef int StackElementType;
typedef struct
{
StackElementType elem[Stack_Size];
int top[2];
}SeqStack;
void InitStack(SeqStack *S)
{
S->top[0]=-1;
S->top[1]=Stack_Size;
}
int IsEmpty_top0(SeqStack *S)
{
if(S->top[0]==-1)
{
return 1;
}
else
{
return 0;
}
}
int IsEmpty_top1(SeqStack *S)
{
if(S->top[1]==Stack_Size)
{
return 1;
}
else
{
return 0;
}
}
int IsFull(SeqStack *S)
{
if(S->top[0]+1==S->top[1])
{
return 1;
}
else
{
return 0;
}
}
void ClearStack(SeqStack *S)
{
S->top[0]=-1;
S->top[1]=Stack_Size;
}
int Push(SeqStack *S,StackElementType x,int i)
{
if(!IsFull(S))
{
switch(i)
{
case 0:
S->top[0]++;
S->elem[S->top[0]]=x;
break;
case 1:
S->top[1]--;
S->elem[S->top[1]]=x;
break;
default:
break;
}
}
}
int Pop(SeqStack *S,StackElementType *x,int i)
{
switch(i)
{
case 0:
if(!IsEmpty_top0(S))
{
*x=S->elem[S->top[0]];
S->top[0]--;
return 1;
}
else
{
return 0;
}
break;
case 1:
if(!IsEmpty_top1(S))
{
*x=S->elem[S->top[1]];
S->top[1]++;
return 1;
}
else
{
return 0;
}
break;
default:
break;
}
}
int main()
{
SeqStack *S;
int i,x;
InitStack(S);
for(i=0;i<10;i++)
{
printf("请输入入栈元素:");
scanf("%d",&x);
Push(S,x,0);
}
for(i=0;i<10;i++)
{
printf("请输入入栈元素:");
scanf("%d",&x);
Push(S,x,1);
}
printf("出栈0:\n");
while(!IsEmpty_top0(S))
{
Pop(S,&x,0);
printf("%3d",x);
}
printf("\n");
while(!IsEmpty_top1(S))
{
Pop(S,&x,1);
printf("%3d",x);
}
printf("\n");
return 0;
}
结果:
yang@liu:~/shujujiegou2$ ./a.out 请输入入栈元素:1 请输入入栈元素:2 请输入入栈元素:3 请输入入栈元素:4 请输入入栈元素:5 请输入入栈元素:6 请输入入栈元素:7 请输入入栈元素:8 请输入入栈元素:9 请输入入栈元素:10 请输入入栈元素:10 请输入入栈元素:9 请输入入栈元素:8 请输入入栈元素:7 请输入入栈元素:6 请输入入栈元素:5 请输入入栈元素:4 请输入入栈元素:3 请输入入栈元素:2 请输入入栈元素:1 出栈0: 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10
3.链栈:链栈即采用链表做为存储结构,在这里采用带头节点的链表实现链栈,由于栈的删除和插入都在表头进行,所以,头节点的指针就是栈顶.看个例子:
#include <stdio.h>
#include <stdlib.h>
#define LinkStackLen sizeof(struct node)
typedef int StackElementType;
typedef struct node
{
StackElementType data;
struct node *next;
}LinkStackNode;
typedef LinkStackNode * LinkStack;
int InitStack(LinkStack top)
{
top->next=NULL;
return 1;
}
int IsEmpty(LinkStack top)
{
if(top->next==NULL)
{
return 1;
}
return 0;
}
int Push(LinkStack top,StackElementType x)
{
LinkStackNode *temp;
temp=(LinkStackNode *)malloc(LinkStackLen);
if(temp==NULL)
{
return 0;
}
temp->data=x;
temp->next=top->next;
top->next=temp;
return 1;
}
int Pop(LinkStack top,StackElementType *x)
{
LinkStackNode *temp;
if(!IsEmpty(top))
{
temp=top->next;
*x=temp->data;
top->next=temp->next;
free(temp);
return 1;
}
return 0;
}
void GetTop(LinkStack top,StackElementType *x)
{
*x=top->next->data;
}
int main()
{
int i;
LinkStackNode *top;
top=(LinkStackNode *)malloc(LinkStackLen);
InitStack(top);
for(i=0;i<10;i++)
{
Push(top,i);
}
while(!IsEmpty(top))
{
Pop(top,&i);
printf("%d",i);
}
printf("\n");
return 0;
}
4,多栈运算:将多个链栈的栈顶指针放在一个一维指针数组里统一管理,从而实现同时管理多个栈.来看个例子:
#include <stdio.h>
#include <stdlib.h>
#define Count 10
typedef int StackElementType;
typedef struct node
{
StackElementType data;
struct node *next;
}LinkStackNode;
typedef LinkStackNode* LinkStack;
LinkStack top[Count];
void InitStack(int i)
{
top[i]->next=NULL;
}
int IsEmpty(int i)
{
if(top[i]->next==NULL)
{
return 1;
}
return 0;
}
int Push(LinkStack top[],int i,StackElementType x)
{
LinkStackNode *temp;
temp=(LinkStackNode *)malloc(sizeof(LinkStackNode));
if(temp==NULL)
{
return 0;
}
temp->data=x;
temp->next=top[i]->next;
top[i]->next=temp;
return 1;
}
int Pop(LinkStack top[],int i,StackElementType *x)
{
LinkStackNode *temp;
if(!IsEmpty(i))
{
temp=top[i]->next;
*x=temp->data;
top[i]->next=temp->next;
free(temp);
return 1;
}
return 0;
}
int main()
{
int i,j;
//LinkStack top[Count];
for(i=0;i<10;i++)
{
top[i]=(LinkStackNode *)malloc(sizeof(LinkStackNode));
InitStack(i);
}
for(i=0;i<10;i++)
{
printf("top[%d]入栈:\n",i);
for(j=0;j<10;j++)
{
Push(top,i,j);
}
}
for(i=0;i<10;i++)
{
printf("top[%d]出栈:\n",i);
while(!IsEmpty(i))
{
Pop(top,i,&j);
printf("%3d",j);
}
printf("\n");
}
printf("\n");
return 0;
}
结果:
yang@liu:~/shujujiegou2$ ./a.out top[0]入栈: top[1]入栈: top[2]入栈: top[3]入栈: top[4]入栈: top[5]入栈: top[6]入栈: top[7]入栈: top[8]入栈: top[9]入栈: top[0]出栈: 9 8 7 6 5 4 3 2 1 0 top[1]出栈: 9 8 7 6 5 4 3 2 1 0 top[2]出栈: 9 8 7 6 5 4 3 2 1 0 top[3]出栈: 9 8 7 6 5 4 3 2 1 0 top[4]出栈: 9 8 7 6 5 4 3 2 1 0 top[5]出栈: 9 8 7 6 5 4 3 2 1 0 top[6]出栈: 9 8 7 6 5 4 3 2 1 0 top[7]出栈: 9 8 7 6 5 4 3 2 1 0 top[8]出栈: 9 8 7 6 5 4 3 2 1 0 top[9]出栈: 9 8 7 6 5 4 3 2 1 0