C语言数据结构学习：栈

C语言 数据结构学习 汇总入口：

C语言数据结构学习：[汇总]

1. 栈

1. 栈，实际上是一种特殊的线性表。
2. 这里使用的是链表栈，链表栈的博客：C语言数据结构学习：单链表

2. 栈的特点

1. 只能在一端进行存取操作，导致存取的元素元素有先进后出的特点
2. 栈是一种只能在一端进行插入和删除操作的特殊线性表。
3. 后进先出（Last In First Out，LIFO）：
   • 就像往一个桶里放东西再取东西一样，后放进去的东西会先被取出来。
4. 基本操作：
   • 入栈（push）：将一个元素压入栈顶。例如，往栈里放一本书，这本书就成为了新的栈顶元素。
   • 出栈（pop）：从栈顶取出一个元素。相当于从桌子上拿走最上面的那本书。
   • 读栈顶元素（peek）：只查看栈顶元素的值而不取出它。如同看一下最上面那本书是什么，但不拿走它。

3. 代码示例

1. 定义新的类型：Node，用于创建节点

   /* 定义新的类型Node，用于创建节点 */
   typedef struct Node {int data;struct Node* next;
   }Node;
   

2. 初始化栈

   /* 初始化栈 */
   Node* initStack() {Node* S = (Node*)malloc(sizeof(Node));S->data = 0;S->next = NULL;return S;
   }
   

3. 入栈（push）、出栈（pop）、读栈顶元素（peek）

   /* 出栈 */
   //判断栈是否为空
   int isEmpty(Node* S) {if (S->data == 0 || S->next == NULL) {return 1;}else{return 0;}
   }
   //出栈
   int pop(Node* S) {if (isEmpty(S)) {return -1;}else {Node* current = S->next;	//获取第一个元素int data = current->data;	//获取第一个元素的dataS->next = current->next;	//把栈头的next指向当前的nextfree(current);				//释放当前return data;				//返回data}
   }/* 入栈 */
   void push(Node* S, int data) {Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->next = S->next;S->next = node;S->data++;
   }/* 读栈顶元素 */
   int peek(Node* S) {if (isEmpty(S)) {return -1;}else {S->data--;return S->next->data;}
   }
   

4. 打印栈

   /* 打印栈 */
   void printStack(Node* S) {Node* current = S->next;while (current){	//当前不为空则进入printf("%d ", current->data);current = current->next;}printf("NULL\\n");
   }
   

5. 测试

   /* 测试 */
   int main(void)
   {Node* S = initStack();push(S, 1);printStack(S);push(S, 2);printStack(S);push(S, 3);printStack(S);push(S, 4);printStack(S);push(S, 5);printStack(S);pop(S);printStack(S);pop(S);printStack(S);pop(S);printStack(S);pop(S);printStack(S);return 0;
   }