栈

栈只能从一端存取,另一端是封闭的
在栈中,不论是存还是取,都必须遵循"先进后出"的原则

==>栈是一种只能从表的一端存取数据,且遵循"先进后出"原则的线性存储结构

进栈和出栈

进栈:将数据存储到栈里面去

出栈:将数据从栈中间取出来

栈的实现方法

栈:有点"特殊"的线性存储结构

顺序表==>顺序栈 (顺序存储结构)
链表==>链栈 (链式存储结构)

顺序栈

#include <stdio.h> 
// ** 元素进栈 
// 参数: 存储结构,栈顶指针,数据 
// 返回值: 栈顶指针 
int pushElem(int* arr, int top, int val) 
{ arr[++top] = val; return top; 
}
// ** 元素出栈 
// 参数: 存储结构,栈顶指针 
// 返回值: 栈顶指针 
int popElem(int* arr, int top) 
{ // 先判断 if (top <= -1) { printf("空栈!\n"); return -1; }printf("元素%d出栈\n",arr[top]); top--; // 原来的数据还在 return top; 
}

int main() 
{ // 数组 int a[100]; // top指针(下标) int top = -1; // 入栈 top = pushElem(a, top, 1); top = pushElem(a, top, 2); top = pushElem(a, top, 3); top = pushElem(a, top, 4);top = pushElem(a, top, 5); // 出栈 top = popElem(a, top); top = popElem(a, top); top = popElem(a, top); top = popElem(a, top); top = popElem(a, top); return 0; 
}

链栈

一般会将链表的头部作为栈顶,尾部作为栈底

#include <stdio.h> 
#include <stdlib.h> 
// 节点 
typedef struct Node 
{ int data; struct Node* pnext; 
}Node; 
// **添加元素 
// 参数: 头指针,数据 
// 返回值: 头指针 
Node* push(Node* stack, int a) 
{ // 1 申请内存 Node* NewNode = (Node*)malloc(sizeof(Node)); // 2 初始化节点的数据域 NewNode->data = a; // 3 把新的节点作为新的头节点 NewNode->pnext = stack; // 4 头指针指向新的头节点 stack = NewNode; // 5 返回头指针 return stack; 
}
// **删除元素 
// 参数: 头指针 
// 返回值: 头指针 
Node* pop(Node* stack) 
{ // 判断是否为空 if (stack) { // 临时指针保存栈顶(头指针) Node* p = stack; // 头指针后移 stack = stack->pnext; // 打印一下数据printf("弹出原来栈顶元素:%d ", p->data); // 再次判断一下是否到了栈底 if (stack) { printf("现在栈顶元素:%d\n", stack->data); }else { printf("栈已经空了!\n"); }// 释放节点 free(p); p->pnext = NULL; }else { printf("是一个空栈!\n"); }return stack; 
}

int main() 
{ Node* stack = NULL; // 入栈 stack = push(stack, 1); stack = push(stack, 2); stack = push(stack, 3); stack = push(stack, 4); stack = push(stack, 5); // 出栈 stack = pop(stack); stack = pop(stack); stack = pop(stack); stack = pop(stack); stack = pop(stack); return 0; 
}

队列

队列的两端都"开口",要求:只能从一端进入队列,从另一端出队列

队头和队尾

队头: 数据出队列的一端

队尾: 数据进入队列的一端

队列的实现方法

顺序表==>顺序队列
链表==>链队列

顺序队列

#include <stdio.h> 
// **入队 
// 参数: 存储结构,队尾,数据 
// 返回值: 队尾 
int enQueue(int* a, int rear, int data) 
{ // rear: 即将添加数据的位置 a[rear] = data; rear++; return rear; 
}
// **出队 
// 参数: 存储结构,队头,队尾 
// 返回值: 无 
void deQueue(int* a, int front, int rear) 
{ // 如果 front == rear,表示队列为空 while (front != rear) { printf("出队元素:%d\n", a[front]); front++;} 
}

int main() 
{ // 数组 int a[100]; // 队头和队尾 int front, rear; // 当队列中没有元素的时候,队头和队尾是同一个地方 front = rear = 0; // 入队 rear = enQueue(a, rear, 1); rear = enQueue(a, rear, 2); rear = enQueue(a, rear, 3); rear = enQueue(a, rear, 4); rear = enQueue(a, rear, 5); // 出队 deQueue(a, front, rear); return 0; 
}

缺点明显，应当改善

栈队列

#include <stdio.h> 
#include <stdlib.h> 
// 节点 
typedef struct QNode 
{ int data; struct QNode* next; 
}QNode; 

// 创建队列(头节点) 
QNode* initQueue()
{ // 创建头节点 QNode* queue = (QNode*)malloc(sizeof(QNode)); // 给值 queue->data = 0; // 这句可以不写 queue->next = NULL; return queue; 
}

// 入队 
QNode* enQueue(QNode* rear, int data) 
{ // 1 做一个新的节点 QNode* NewNode = (QNode*)malloc(sizeof(QNode)); NewNode->data = data; NewNode->next = NULL; // 2 使用尾插法添加 rear->next = NewNode; rear = NewNode; return rear; 
}
// 出队 
QNode* deQueue(QNode* top, QNode* rear) 
{ if (top->next == NULL) { printf("队列为空!\n"); return rear; }// 创建临时指针 QNode* p = top->next; // 显示数据 printf("%d ", p->data); // 断头,换头 p->next可能为NULL top->next = p->next; // 判断(是否即将只剩下一个节点) if (rear == p) { rear = top; }// 释放 free(p); return rear; 
}

int main() 
{ QNode* queue, *top, *rear; queue = top = rear = initQueue(); // 入队 rear = enQueue(rear, 1); rear = enQueue(rear, 2); rear = enQueue(rear, 3); rear = enQueue(rear, 4);rear = enQueue(rear, 5); // 出队 rear = deQueue(top, rear); rear = deQueue(top, rear); rear = deQueue(top, rear); rear = deQueue(top, rear); rear = deQueue(top, rear); rear = deQueue(top, rear); return 0; 
}