【数据结构】（C语言）：栈

栈：

• 线性的集合。
• 后进先出（LIFO，last 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++;                    // 每添加一个元素，length+1
}

获取栈顶元素：

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 'n'if(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