一、简介
栈是限定仅在表尾进行插入或删除操作的一种后进先出的线性表。
基本操作：初始化栈、判断是否为空栈、入栈、出栈、获取栈顶元素、销毁栈、出栈、获取栈的大小、清空栈。
根据分配的内存空间不同而分为顺序栈和链栈。
二、顺序栈
/* 顺序栈结构。元素存放在连续的内存空间（系统数组）
栈底元素索引为 0。
*/
typedef struct Stack {
int data[MAXSIZE];
int top; // 指向栈顶的索引
} Stack;
/// 初始化栈
void initStack(Stack * stack)
{
stack->top = 0;
}
/// 空栈
bool isEmptyStack(Stack * stack)
{
return stack->top == 0;
}
/// 满栈
bool isFullStack(Stack * stack)
{
return stack->top == MAXSIZE;
}
/// 入栈
bool inputStack(Stack * stack, int data)
{
if (isFullStack(stack))
return NO;
stack->data[stack->top] = data;
stack->top++;
return YES;
}
/// 出栈
bool outputStack(Stack * stack, int * data)
{
if (isEmptyStack(stack))
return NO;
stack->top--;
*data = stack->data[stack->top];
return YES;
}
/// 打印栈的内容
void printStack(Stack * stack)
{
if (isEmptyStack(stack))
return;
int i = stack->top - 1;
while(i > -1) {
printf("%d\t", stack->data[i]);
i--;
}
printf("\r\n");
}
/// 调用
{
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int i = 0;
int data = 0;
Stack stack = { 0 };
initStack(&stack);
for (i = 0; i < sizeof(array)/sizeof(int); i++) {
inputStack(&stack, array[i]);
}
printStack(&stack);
outputStack(&stack, &data);
printf("%d\n", data);
outputStack(&stack, &data);
printf("%d\n", data);
printStack(&stack);
inputStack(&stack, 11);
inputStack(&stack, 12);
printStack(&stack);
}
10 9 8 7 6 5 4 3 2 1
10
9
8 7 6 5 4 3 2 1
12 11 8 7 6 5 4 3 2 1
三、链栈
链栈
/* 链栈结构。元素存放在非连续内存空间（动态分配的堆上）
栈顶指向链表的头结点，这样能够向下增加、删除结点。如果栈顶指向链表末尾，那么无法找到上一个结点
*/
typedef struct Stack {
int data;
struct Stack * next;
} Stack;
/// 初始化栈
void initStack(Stack * stack)
{
stack->next = NULL;
}
/// 空栈
bool isEmptyStack(Stack * stack)
{
return stack->next == NULL;
}
/// 入栈
void inputStack(Stack * stack, int data)
{
Stack * newNode = (Stack *)malloc(sizeof(Stack)); // 创建新的结点
newNode->data = data; // 赋值
newNode->next = stack->next; // next 指向之前的"第一个内容结点"
stack->next = newNode;
}
/// 出栈
bool outputStack(Stack * stack, int * data)
{
if (isEmptyStack(stack))
return NO;
Stack * node = stack->next;
if (data != NULL)
*data = node->data;
stack->next = node->next; // 去掉当前的"第一个内容结点"
return YES;
}
/// 获得栈顶内容
int topData(Stack * stack)
{
if (isEmptyStack(stack))
return -1;
Stack * node = stack->next;
return node->data;
}
/// 打印栈的内容
void printStack(Stack * stack)
{
if (isEmptyStack(stack))
return;
Stack * node = stack->next;
while(node) {
printf("%d\t", node->data);
node = node->next;
}
printf("\r\n");
}
/// 调用
{
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int i = 0;
int data = 0;
Stack stack = { 0 };
initStack(&stack);
for (i = 0; i < sizeof(array)/sizeof(int); i++) {
inputStack(&stack, array[i]);
}
printStack(&stack);
outputStack(&stack, &data);
printf("%d\n", data);
outputStack(&stack, &data);
printf("%d\n", data);
printStack(&stack);
inputStack(&stack, 11);
inputStack(&stack, 12);
printStack(&stack);
}
12 11 10 9 8 7 6 5 4 3 2 1
12
11
10 9 8 7 6 5 4 3 2 1
12 11 10 9 8 7 6 5 4 3 2 1
四、字符匹配
/// 获得栈顶内容
char topData(Stack * stack)
{
if (isEmptyStack(stack))
return '\0'; // 空字符
Stack * node = stack->next;
return node->data;
}
/// 左侧符号
bool isLeft(char c)
{
return (c == '<') || (c == '[') || (c == '(') || (c == '{');
}
/// 右侧符号
bool isRight(char c)
{
return (c == '>') || (c == ']') || (c == ')') || (c == '}');
}
/// 引号
BOOL isQuot(char c)
{
return (c == '\'') || (c == '\"');
}
bool isMatch(char left, char right)
{
return (left == '<' && right == '>')
|| (left == '[' && right == ']')
|| (left == '(' && right == ')')
|| (left == '{' && right == '}')
|| (left == '\'' && right == '\'')
|| (left == '\"' && right == '\"');
}
/// 解析字符串
bool parse(char * string)
{
Stack stack = { 0 };
initStack(&stack);
int i = 0;
bool result = true;
string = (string == NULL) ? "" : string;
while(result && (string[i] != '\0'))
{
char c = string[i];
// 左符号
if(isLeft(c)) {
inputStack(&stack, c); // 入栈
}
// 右符号
else if(isRight(c)) {
// 栈未空 && 与栈顶元素匹配
if(!isEmptyStack(&stack) && isMatch(topData(&stack), c)){
outputStack(&stack, NULL); // 出栈
}
else {
result = false;
}
}
// 引号、双引号
else if(isQuot(c)) {
// 栈为空 || 当前符号与栈顶元素不匹配
if(isEmptyStack(&stack) || !isMatch(topData(&stack), c))
{
inputStack(&stack, c); // 入栈
}
// 当前元素与栈顶元素匹配
else if(isMatch(topData(&stack), c))
{
outputStack(&stack, NULL); // 出栈
}
}
i++;
}
return result && isEmptyStack(&stack);
}
/// 调用
{
char * s = "'([]){}'""";
if (parse(s)) {
NSLog(@"配对成功");
}
else {
NSLog(@"配对失败");
}
}
配对成功
五、栈实现队列
static Stack stack_in = {0}; // 添加数据的栈
static Stack stack_out = {0}; // 移除数据的栈
// 入队
void inputQueue(char c)
{
inputStack(&stack_in, c);
}
// 出队
char outputQueue()
{
// 空队列
if (isEmptyQueue()) {
printf("空队列\t");
return '\0';
}
// out 栈为空
if (isEmptyStack(&stack_out)) {
while (!isEmptyStack(&stack_in)) {
inputStack(&stack_out, topData(&stack_in));
outputStack(&stack_in, NULL);
}
}
// out 栈为空
if (isEmptyStack(&stack_out))
return '\0';
char data;
outputStack(&stack_out, &data);
return data;
}
// 空队列
bool isEmptyQueue()
{
return isEmptyStack(&stack_in) && isEmptyStack(&stack_out);
}
/// 调用
{
char array[10] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
int i = 0;
// 入队
for (; i < 4; i++) {
inputQueue(array[i]);
}
// 出队
printf("%c\n", outputQueue());
// 入队
for (; i < 10; i++) {
inputQueue(array[i]);
}
// 出队
for (int j = 0; j < 12; j++) {
printf("%c\t", outputQueue());
}
}
a
b c d e f g h i j 空队列 空队列 空队列
网友评论