东山县城乡规划建设局网站,个人网站图片,做网站是什么课,福州云建站栈#xff1a;
线性的集合。后进先出#xff08;LIFO#xff0c;last in first out#xff09;。两个指针#xff1a;指向栈顶和栈底。栈顶指向最后进入且第一个出去的元素。栈底指向第一个进入且最后一个出去的元素。两个操作#xff1a;入栈#xff08;往栈尾添加元素…栈
线性的集合。后进先出LIFOlast in first out。两个指针指向栈顶和栈底。栈顶指向最后进入且第一个出去的元素。栈底指向第一个进入且最后一个出去的元素。两个操作入栈往栈尾添加元素出栈从栈尾取出元素。可以使用链表实现也可以使用数组实现。本文使用双链表举例。 入栈往栈顶栈尾部添加元素。
头指针指向第一个元素。尾指针指向最后的元素。 出栈从栈顶栈尾部删除元素。
头指针指向第一个元素。尾指针指向最后的元素。 C语言实现双链表
创建节点结构体数据类型并创建具体节点实例的函数
// 节点结构体数据类型
typedef struct Node
{int value; // 存储数据为整数struct Node *next; // 指向下一个数据的指针struct Node *prev; // 指向上一个数据的指针
} LinkNode; // 别名LinkNode
// 创建具体节点实例的函数
LinkNode * createNode(int data)
{LinkNode *node (LinkNode *)malloc(sizeof(LinkNode)); // 分配内存空间if(node NULL){perror(Memory allocation failed);exit(-1);}node-value data;node-prev NULL;node-next NULL;return node;
} 本文将头指针、尾指针和栈长度作为全局变量
LinkNode *header NULL; // 头指针,指向第一个节点,初始化为NULL
LinkNode *tail NULL; // 尾指针,指向最后节点,初始化为NULL
int length 0; // 统计栈有多少元素,初始化为0 入栈
// 入栈往栈顶即尾部添加数据
void push(int data)
{LinkNode *node createNode(data);if(length 0) // 空栈头指针和尾指针都指向新节点{header node;tail node;length;return ;}tail-next node; // 原最后节点的下一个为新节点node-prev tail; // 新节点的上一个为原最后节点tail node; // 尾指针指向新节点即新节点为最后节点 length; // 每添加一个元素length1
} 获取栈顶元素
int gettop(void)
{// 栈不为空则栈顶元素为尾指针指向的最后节点的值if(length ! 0) return tail-value;
} 出栈
int pop(void)
{if(length ! 0){// 获取最后节点的值int top tail-value;// 通过最后节点的prev找到倒数第二个节点,其next指向NULL,则原倒数第二个节点为新的最后节点tail-prev-next NULL;// 每删除一个节点,length-1length--;// 返回原最后节点的值return top;}
} 遍历栈
void travel(void)
{if(length 0) return ;LinkNode *cur header; // 从链表头部开始遍历直到最后printf(stack elements:);while(cur ! NULL){printf(%d \t, cur-value);cur cur-next;}printf(\n);
} 完整代码stack.c
#include stdio.h
#include stdlib.h
#include ctype.h/* structrue */
typedef struct Node // node structure
{int value;struct Node *next;struct Node *prev;
} LinkNode;/* global variables */
LinkNode *header NULL; // the header pointer
LinkNode *tail NULL; // the tailer pointer
int length 0; // the number of the stack elements/* function prototype */
void push(int data); // add element to the end of the stack
int pop(void); // delete element from the end of the stack
int gettop(void); // show element at the end of the stack
void travel(void); // show element one by one/* main function */
int main(void)
{// cycle input a number until q or non-numeric, add the number to the stackwhile(1) // 循环输入数字,并入栈,输入q退出输入循环{int data 0, c;printf(if quit,input q. Input a number: );c getchar(); // 获取输入的一个字符if(tolower(c) q) break; // 若输入q,则退出输入循环if(c 0 || c 9) break; // 输入的不是数字,则退出输入循环while(c ! \n) // 若整数为多位数,通过一位一位计算最终获得多位整数{data * 10;data c - 48; // ASCII码表中0对应码值48c getchar();}push(data); // 入栈printf(length is %d \n, length); // 输出栈元素个数travel(); // 遍历栈}// when stack not empty,cycle look and delete the top element until input nif(length 0) exit(-1);char k;printf(if you want to look and delete the top element? (y/n) );scanf( %c, k); // 获取输入的内容while(tolower(k) y length ! 0) // 循环输入是否查看并删除栈顶元素{printf(top element is %d \n, gettop()); // 输出栈顶元素pop(); // 出栈printf(length is %d \n, length); // 输出栈元素个数travel(); // 遍历栈printf(if you want to look and delete the top element? (y/n) );scanf( %c, k); // 获取下一个输入的内容}
}/* subfunction */
LinkNode * createNode(int data) // create a node
{LinkNode *node (LinkNode *)malloc(sizeof(LinkNode));if(node NULL){perror(Memory allocation failed);exit(-1);}node-value data;node-prev NULL;node-next NULL;return node;
}void push(int data) // add element to the end of the stack
{LinkNode *node createNode(data);if(length 0){header node;tail node;length;return ;}tail-next node;node-prev tail;tail node;length;
}int pop(void) // delete element from the end of the stack
{if(length ! 0){int top tail-value;tail-prev-next NULL;length--;return top;}
}int gettop(void) // show element at the end of the stack
{if(length ! 0) return tail-value;
}void travel(void) // show element one by one
{if(length 0) return ;LinkNode *cur header;printf(stack elements:);while(cur ! NULL){printf(%d \t, cur-value);cur cur-next;}printf(\n);
} 编译链接 gcc -o stack stack.c 执行可执行文件 ./stack
