1、栈的定义
栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈),允许进行操作的一端称为“栈顶”,另一固定端称为“栈底”,当栈中没有元素时称为“空栈”。特点:后进先出(LIFO)。
2、栈的基本运算
创建空栈:CreateStack (len)
清空栈 :ClearStack (S)
判断是否栈空:EmptyStack (S)
判断是否栈满:FullStack (S)
元素进栈:PushStack (S, x)
元素出栈:PopStack (S)
取栈顶元素:GetTop (S)
3、顺序栈
它是顺序表的一种,具有顺序表同样的存储结构,由数组定义,配合用数组下标表示的栈顶指针top(相对指针)完成各种操作。
typedef int data_t ; /*定义栈中数据元素的数据类型*/
typedef struct
{
data_t *data ; /*用指针指向栈的存储空间*/
int maxlen; /*当前栈的最大元素个数*/
int top ; /*指示栈顶位置(数组下标)的变量*/
} seqstack_t; /*顺序栈类型定义*/a、创建栈:
seqstack_t *CreateStack (int len)
{
seqstack_t *ss;
ss = (seqstack_t *)malloc(sizeof(seqstack_t));
ss->data = (data_t *)malloc(sizeof(data_t) * len);
ss->top = -1;
ss->maxlen = len;
return ss;
}b、清空栈:
ClearStack (seqstack_t *s)
{
s-> top = -1 ;
}c、判断栈是否空 :
int EmptyStack (seqstack_t *s)
{
return (s->top == -1 ? 1 : 0);
}d、进栈 :
void PushStack (seqstack_t *s , data_t x)
{ if (s->top = = N - 1){
printf ( “overflow !\n”) ;
return ;
}
else {
s->top ++ ;
s->data[s->top] = x ;
}
return ;
}
e、出栈 :
datatype PopStack(seqstack_t *s)
{
s->top--;
return (s->data[s->top+1]);
}
f、取栈顶元素:
datatype GetTop(seqstack_t *s)
{
return (s->data[s->top]);
}4、链式栈
插入操作和删除操作均在链表头部进行,链表尾部就是栈底,栈顶指针就是头指针。
typedef int data_t ; /*定义栈中数据元素数据类型*/
typedef struct node_t
{
data_t data ; /*数据域*/
struct node_t *next ; /*链接指针域*/
} linkstack_t ; /*链栈类型定义*/a、创建空栈 :
linkstack_t *CreateLinkstack()
{
linkstack_t *top;
top = (linkstack_t *)malloc(sizeof(linkstack_t));
top->next = NULL;
return top;
}
b、判断是否空栈 :
int EmptyStack (linkstack_t *top)
{
return (top->next == NULL ? 1 : 0);
}
c、入栈 :
void PushStack(linkstack_t *top, data_t x)
{
linkstack_t *p ; /*定义辅助指针*/
p = (linkstack_t *)malloc ( sizeof (linkstack_t) ) ; /*指向新结点*/
p->data = x ; /*将数据存入新结点的数据域中*/
p->next = top->next;
top->next = p; /*新结点插入原栈顶之前*/
return;
}
相关文章
- 03-23数据结构——栈
- 03-23数据结构之栈
- 03-23链栈
- 03-23加减乘除四则运算(链栈的应用)
- 03-23c++练习10——两个栈实现一个队列
- 03-23数据结构(6):栈的链式存储结构及其基本运算的实现
- 03-23[数据结构]--链栈的实现
- 03-23链栈
- 03-23C语言数据结构链栈(创建、入栈、出栈、取栈顶元素、遍历链栈中的元素)
- 03-23python – 为什么要实现两个如此相似的数据结构,如List和Tuple