舟山建设工程信息网站,wordpress新手建站,办公室装修案例,有限责任公司的设立条件栈
1. 基本概念
栈是一种逻辑结构#xff0c;是特殊的线性表。特殊在#xff1a; 只能在固定的一端操作
只要满足上述条件#xff0c;那么这种特殊的线性表就会呈现一种“后进先出”的逻辑#xff0c;这种逻辑就被称为栈。栈 在生活中到处可见#xff0c;比如堆叠的盘子…栈
1. 基本概念
栈是一种逻辑结构是特殊的线性表。特殊在 只能在固定的一端操作
只要满足上述条件那么这种特殊的线性表就会呈现一种“后进先出”的逻辑这种逻辑就被称为栈。栈 在生活中到处可见比如堆叠的盘子、电梯中的人们、嵌套函数的参数等等。 由于约定了只能在线性表固定的一端进行操作于是给栈这种特殊的线性表的“插入”、“删除”另起了 下面这些特定的名称 栈顶可以进行插入删除的一端 栈底栈顶的对端 入栈将节点插入栈顶之上也称为压栈函数名通常为push() 出栈将节点从栈顶剔除也称为弹栈函数名通常为pop() 取栈顶取得栈顶元素但不出栈函数名通常为top(
基于这种固定一端操作的简单约定栈获得了“后进先出”的基本特性如下图所示最后一个放入的元 素最先被拿出来
2. 存储形式
栈只是一种数据逻辑如何将数据存储于内存则是另一回事。一般而言可以采用顺序存储形成顺序 栈或采用链式存储形成链式栈。 顺序栈 顺序存储意味着开辟一块连续的内存来存储数据节点一般而言管理栈数据除了需要一块连续的 内存之外还需要记录栈的总容量、当前栈的元素个数、当前栈顶元素位置如果有多线程还需要 配互斥锁和信号量等信息为了便于管理通常将这些信息统一于在一个管理结构体之中
// 顺序栈节点
struct seqStack
{
datatype *data; // 顺序栈入口
int size; // 顺序栈总容量
int top; // 顺序栈栈顶元素下标
};链式栈
链式栈的组织形式与链表无异只不过插入删除被约束在固定的一端。为了便于操作通常也会创 建所谓管理结构体用来存储栈顶指针、栈元素个数等信息
// 链式栈节点
typedef struct node
{
datatype data;
struct node *next;
}node;
// 链式栈管理结构体
struct linkStack
{
node *top; // 链式栈栈顶指针
int size; // 链式栈当前元素个数
};3. 基本操作
不管是顺序栈链式栈栈的操作逻辑都是一样的但由于存储形式不同代码的实现是不同的。下 面分别将顺序栈和链式栈的基本核心操作罗列出来
顺序栈
sstack.h
#ifndef __SSTACK_H
#define __SSTACK_H
// 数据类型
typedef int DATA;
// 顺序栈结构体
typedef struct
{
DATA *pData; // 栈中元素的地址
int size; // 栈的总容量
int top; // 栈顶元素下标
}SeqStack;
// 初始化栈
int SStack_init(SeqStack *s, int num);
// 判断栈是否已满
int SStack_isfull(SeqStack *st);
// 判断栈是否为空
int SStack_isempty(SeqStack *st);
// 入栈/压栈
int SStack_push(SeqStack *st,DATA data);
// 出栈/弹栈
int SStack_pop(SeqStack *st,DATA *data);
// 回收栈
int SStack_free(SeqStack *st);
#endifsstack.c
#include stdlib.h
#include sstack.h
// 初始化栈
int SStack_init(SeqStack* s,int num)
{
s - pData (DATA*)calloc(sizeof(DATA),num);
if(s - pData NULL)
return -1;
s - size num ;
s - top -1;
return 0;
}
// 判断栈是否已满
int SStack_isfull(SeqStack *st)
{
return st - top 1 st - size;
}
// 判断栈是否为空
int SStack_isempty(SeqStack *st)
{
return st - top -1;
}
// 压栈/入栈
int SStack_push(SeqStack *st,DATA data)
{
if(SStack_isfull(st))
return -1;
st - top;
st - pData[st - top] data;
return 0;
}
// 出栈/弹栈
int SStack_pop(SeqStack *st,DATA *data)
{
if(SStack_isempty(st))
return -1;
*data st - pData[st - top];
st - top--;
return 0;
}
// 回收栈
int SStack_free(SeqStack *st)
{
if(st - pData)
{
free(st-pData);
st - pData NULL;
}
st - top -1;
}
sstack_main.c
#include sstack.h
#include stdio.h
int main(void)
{
SeqStack st;
SStack_init(st,10);
register int i 1;
for(; i 10; i)
SStack_push(st,i);
if(-1 SStack_push(st,1024))
fprintf(stderr,满栈,插入失败\n);
while(!SStack_isempty(st))
{
DATA data 0;
SStack_pop(st,data);
printf(%4d,data);
}
printf(\n);
SStack_free(st);
return 0;
}链式栈
inkstack.h
#ifndef __LINKSTACK_H
#define __LINKSTACK_H
// 数据类型
typedef int DATA;
// 链式栈节点
typedef struct _node
{
DATA data; // 数据
struct _node *next; // 指向下一个栈的节点
}NODE;
// 链式栈管理结构体
typedef struct
{
NODE *pHead;// 链式栈栈顶指针
int size; // 链式栈当前元素个数
int num;
}LinkStack;
// 初始化链式栈
int LStack_init(LinkStack *s, int num);
// 判断栈是否已满
int LStack_isfull(LinkStack *st);
// 判断栈是否为空
int LStack_isempty(LinkStack *st);
// 压栈/入栈
int LStack_push(LinkStack *st,DATA data);
// 弹栈/出栈
int LStack_pop(LinkStack *st,DATA *data);
// 回收栈
int LStack_free(LinkStack *st);
#endif
linkstack.c
#include linkstack.h
#include stdio.h
#include stdlib.h
// 初始化栈
int LStack_init(LinkStack *st, int num)
{
st - pHead NULL;
st - size num;
st - num 0;
return 0 ;
}
// 判断栈是否已满
int LStack_isfull(LinkStack *st)
{
return st - num st - size;
}
// 判断栈是否为空
int LStack_isempty(LinkStack *st)
{
return st - num 0;
}
// 入栈
int LStack_push(LinkStack *st,DATA data)
{
if(LStack_isfull(st))
return -1;
NODE* p (NODE*)malloc(sizeof(NODE));
if(!p)
return -1;
p - data data;
p - next st - pHead;
st - pHead p;
(st - num);
return 0;
}
// 出栈
int LStack_pop(LinkStack *st,DATA *data)
{
if(LStack_isempty(st))
return -1;
NODE* p st - pHead;
if(!p)
return -1;
*data p - data;
st - pHead p - next;
free(p);
(st - num)--;
return 0;
}
// 回收栈
int LStack_free(LinkStack *st)
{
NODE* p st - pHead, *q NULL;
while(p)
{
q p;
p p - next;
free(q);
}
st - pHead NULL;
st - num 0;
return 0;
}linkstack_main.c
#include linkstack.h
#include stdio.h
int main(void)
{
LinkStack st;
LStack_init(st,10);
register int i 1;
for(; i 10; i)
LStack_push(st,i);
if(-1 LStack_push(st,1024))
fprintf(stderr,满栈,插入失败\n);
while(!LStack_isempty(st))
{
DATA data 0;
LStack_pop(st,data);
printf(%4d,data);
}
printf(\n);
LStack_free(st);
return 0;
}
使用链式栈实现十进制转八进制键盘输入一个十进制数经过链式栈的相关算法输出八进制 数。
