栈的简单操作¶

栈（Stack）是一种按照后进先出（LIFO，Last In First Out）原则组织数据的线性数据结构。栈只允许在一端（称为栈顶）进行插入和删除操作，不允许在另一端（称为栈底）进行操作。

栈可以用链表、数组、hash进行实现，下来以有效的括号 https://leetcode.cn/problems/valid-parentheses/为例，进行一下示例。

一、使用数组实现¶

数组实现栈操作，其实就是在数组的最后去插入和删除数据。

入栈的话，就是在数组最后插入一个数据，出栈就是删除数组最后一个数据。

CGoC优化C语言数组实现栈处理Go语言切片实现栈对象

C
bool CheckBracketMatching(char sL, char *stack,  unsigned int *top)
{
    unsigned int index = *top;
    // 没有入栈，或者与栈顶不是一对，返回false
    if ((index == 0) || (stack[index - 1] != sL)) {
        return false;
    }

    // 出栈
    stack[index] = '\0';
    index--;
    *top = index;
    return true;
}

bool isValidByArray(char* s) {
    unsigned int n = 0;
    unsigned int i = 0;
    unsigned int top = 0;
    char *stack = NULL;

    n = strlen(s);
    // 必须是偶数，如果是奇数，肯定是不满足条件的
    if ((n % 2) != 0) {
        return false;
    }

    // 使用数组，表示栈数据存储，申请内存
    stack = (char*)malloc(n);
    if (stack == NULL) {
        return false;
    }
    memset(stack, 0, n);

    // 遍历字符串，记录top，当左侧括号出现时，入栈，top++
    for (i = 0; i < n; i++) {
        // 如果在过一半的时候，top还没有开始出栈，则肯定不匹配
        if (top > n/2) {
            free(stack);
            return false;
        }
        // 找到一个左侧括号，直接入栈
        if ((s[i] == '(')  || (s[i] == '{') || (s[i] == '[')) { // 找到左侧括号
            stack[top] = s[i];
            top++;
            continue;
        }

        // 如果是右侧括号，当与栈顶是一对的时候，进行出栈，否则直接返回false
        if ((s[i] == ')') && (CheckBracketMatching('(', stack, &top) == false)) {
            free(stack);
            return false;
        }

        if ((s[i] == '}') && (CheckBracketMatching('{', stack, &top) == false)) {
            free(stack);
            return false;
        }

        if ((s[i] == ']') && (CheckBracketMatching('[', stack, &top) == false)) {
            free(stack);
            return false;
        }
    }
    
    // 如果括号是匹配的，则top是一定为0
    free(stack);
    return top == 0;
}

bool isValid(char* s) {
    return isValidByArray(s);
}

Go
// 使用切片，完成出栈和入栈
func isValid(s string) bool {
    strlen := len(s)
    if strlen % 2 == 1 {
        return false
    }
    pairs := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    var stack []byte
    for i := 0; i < strlen; i++ {
        // 如果在过一半的时候，top还没有开始出栈，则肯定不匹配
        if (len(stack) > strlen/2) {
            return false;
        }

        // 题目指定只有 '('，')'，'{'，'}'，'['，']'几个字符串，有匹配到右侧括号
        if pairs[s[i]] > 0 {
            // 右侧括号，如果字符串有效，则左侧括号必然已经在栈中，并且是在栈顶
            if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
                return false
            }
            // 满足条件，出栈
            stack = stack[:len(stack)-1]
        } else {
            // 不是右侧括号，入栈
            stack = append(stack, s[i])
        }
    }

    // 如果括号是匹配的，最终结果，栈一定是空的
    return len(stack) == 0
}

C
bool CheckBracketMatching(char sL, char *stack,  unsigned int *top)
{
    unsigned int index = *top;
    // 没有入栈，或者与栈顶不是一对，返回false
    if ((index == 0) || (stack[index - 1] != sL)) {
        return false;
    }

    // 出栈
    stack[index] = '\0';
    index--;
    *top = index;
    return true;
}

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValidByArrayWithParis(char* s) {
    unsigned int n = 0;
    unsigned int i = 0;
    unsigned int top = 0;
    char *stack = NULL;

    n = strlen(s);
    // 必须是偶数，如果是奇数，肯定是不满足条件的
    if ((n % 2) != 0) {
        return false;
    }

    // 使用数组，表示栈数据存储，申请内存
    stack = (char*)malloc(n);
    if (stack == NULL) {
        return false;
    }
    memset(stack,0,n);

    // 遍历字符串，记录top，当左侧括号出现时，入栈，top++
    for (i = 0; i < n; i++) {
        // 超过一半的时候，就需要开始出栈了，否则必然不匹配
        if (top > n/2) {
            free(stack);
            return false;
        }
        char ch = pairs(s[i]);
        // 找到一个左侧括号，直接入栈
        if (ch != 0) { // 找到左侧括号
            stack[top] = s[i];
            top++;
        } else {
            if (CheckBracketMatching(ch, stack, &top) == false) {
                free(stack);
                return false;
            }
        }
    }

    // 如果括号是匹配的，则top是一定为0
    free(stack);
    return top == 0;
}

bool isValid(char* s) {
    return isValidByArrayWithParis(s);
}

C
#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>  

#define MAX_SIZE 100  // 定义栈的最大容量  

typedef struct {  
    int data[MAX_SIZE];  
    int top;  // 栈顶指针  
} Stack;  

// 初始化栈  
void initStack(Stack *s) {  
    s->top = -1;  
}  

// 判断栈是否为空  
bool isEmpty(Stack *s) {  
    return s->top == -1;  
}  

// 判断栈是否已满  
bool isFull(Stack *s) {  
    return s->top == MAX_SIZE - 1;  
}  

// 入栈操作  
bool push(Stack *s, int value) {  
    if (isFull(s)) {  
        printf("Stack is full\n");  
        return false;  
    }  
    s->top++;  
    s->data[s->top] = value;  
    return true;  
}  

// 出栈操作  
bool pop(Stack *s, int *value) {  
    if (isEmpty(s)) {  
        printf("Stack is empty\n");  
        return false;  
    }  
    *value = s->data[s->top];  
    s->top--;  
    return true;  
}  

// 查看栈顶元素  
bool peek(Stack *s, int *value) {  
    if (isEmpty(s)) {  
        printf("Stack is empty\n");  
        return false;  
    }  
    *value = s->data[s->top];  
    return true;  
}  

int main() {  
    Stack s;  
    initStack(&s);  

    // 入栈操作  
    push(&s, 1);  
    push(&s, 2);  
    push(&s, 3);  

    // 查看栈顶元素  
    int topValue;  
    peek(&s, &topValue);  
    printf("Top element: %d\n", topValue);  

    // 出栈操作  
    int poppedValue;  
    pop(&s, &poppedValue);  
    printf("Popped element: %d\n", poppedValue);  

    return 0;  
}

Go
package main  

import (  
    "errors"  
    "fmt"  
)  

// Stack represents a stack that holds elements of type int.  
type Stack struct {  
    elements []int  
}  

// NewStack creates and returns a new Stack.  
func NewStack() *Stack {  
    return &Stack{elements: []int{}}  
}  

// Push adds an element to the top of the stack.  
func (s *Stack) Push(element int) {  
    s.elements = append(s.elements, element)  
}  

// Pop removes and returns the element at the top of the stack.  
// If the stack is empty, it returns an error.  
func (s *Stack) Pop() (int, error) {  
    if s.IsEmpty() {  
        return 0, errors.New("stack is empty")  
    }  
    index := len(s.elements) - 1  
    element := s.elements[index]  
    s.elements = s.elements[:index]  
    return element, nil  
}  

// Peek returns the element at the top of the stack without removing it.  
// If the stack is empty, it returns an error.  
func (s *Stack) Peek() (int, error) {  
    if s.IsEmpty() {  
        return 0, errors.New("stack is empty")  
    }  
    return s.elements[len(s.elements)-1], nil  
}  

// IsEmpty checks if the stack is empty.  
func (s *Stack) IsEmpty() bool {  
    return len(s.elements) == 0  
}  

func main() {  
    stack := NewStack()  

    // Push elements onto the stack  
    stack.Push(1)  
    stack.Push(2)  
    stack.Push(3)  

    // Peek the top element  
    top, err := stack.Peek()  
    if err != nil {  
        fmt.Println(err)  
    } else {  
        fmt.Println("Top element:", top)  
    }  

    // Pop elements from the stack  
    for !stack.IsEmpty() {  
        element, err := stack.Pop()  
        if err != nil {  
            fmt.Println(err)  
        } else {  
            fmt.Println("Popped element:", element)  
        }  
    }  

    // Verify that the stack is empty  
    if stack.IsEmpty() {  
        fmt.Println("Stack is empty")  
    }  
}

二、使用链表实现¶

如果使用单链表实现，那么入栈就是在链表头部插入节点，出栈就是在链表头部删除节点。

如果是使用双向链表实现，那么入栈和出栈在head和tail没啥区别，都可以的。

另外，也可以单独实现一个栈的对象，进行push、pop操作。

C语言C语言链表实现栈处理Go语言链表实现栈对象

C
#include <stdio.h>
#include <stdlib.h>
#include "stdbool.h"

// 定义链表节点结构体
typedef struct Node {
    char data;
    struct Node* next;
} Node;

// 定义栈结构体
typedef struct Stack {
    Node* top;
} Stack;

// 初始化栈
Stack* StackCreate() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = NULL;
    return stack;
}

// 判断栈是否为空
bool StackIsEmpty(Stack* stack) {
    return stack->top == NULL;
}

// 入栈操作
void StackPush(Stack* stack, char value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}

// 出栈操作
char StackPop(Stack* stack) {
    if (StackIsEmpty(stack)) {
        return -1;
    }
    Node* temp = stack->top;
    char value = temp->data;
    stack->top = temp->next;
    free(temp);
    return value;
}

// 查看栈顶元素
char StackPeek(Stack* stack) {
    if (StackIsEmpty(stack)) {
        return -1;
    }
    return stack->top->data;
}

// 销毁栈，释放所有节点内存
void StackDestroy(Stack* stack) {
    Node* temp;
    while (!StackIsEmpty(stack)) {
        temp = stack->top;
        stack->top = stack->top->next;
        free(temp);
    }
    free(stack);
}

char charPairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValidBracket(char* s) {
    unsigned int n = 0;
    unsigned int i = 0;
    unsigned int top = 0;
    Stack *stack = NULL;

    n = strlen(s);
    // 必须是偶数，如果是奇数，肯定是不满足条件的
    if ((n % 2) != 0) {
        return false;
    }

    stack = StackCreate();
    // 遍历字符串，记录top，当左侧括号出现时，入栈，top++
    for (i = 0; i < n; i++) {
        // 超过一半的时候，就需要开始出栈了，否则必然不匹配
        if (top > n/2) {
            StackDestroy(stack);
            return false;
        }
        char ch = charPairs(s[i]);
        // 找到一个左侧括号，直接入栈
        if (ch == 0) { // 找到左侧括号
            StackPush(stack, s[i]);
        } else {
            if (StackIsEmpty(stack) || (StackPeek(stack) != ch)) {
                StackDestroy(stack);
                return false;
            }
            StackPop(stack);
        }
    }

    // 如果括号是匹配的，栈一定是空的
    if (StackIsEmpty(stack)) {
        return true;
    }
    StackDestroy(stack);
    return false;
}

C
#include <stdio.h>  
#include <stdlib.h>  

// 定义链表节点结构体  
typedef struct Node {  
    int data;  
    struct Node* next;  
} Node;  

// 定义栈结构体  
typedef struct Stack {  
    Node* top;  
} Stack;  

// 初始化栈  
Stack* createStack() {  
    Stack* stack = (Stack*)malloc(sizeof(Stack));  
    stack->top = NULL;  
    return stack;  
}  

// 判断栈是否为空  
int isEmpty(Stack* stack) {  
    return stack->top == NULL;  
}  

// 入栈操作  
void push(Stack* stack, int value) {  
    Node* newNode = (Node*)malloc(sizeof(Node));  
    newNode->data = value;  
    newNode->next = stack->top;  
    stack->top = newNode;  
}  

// 出栈操作  
int pop(Stack* stack) {  
    if (isEmpty(stack)) {  
        printf("Error: Stack is empty.\n");  
        exit(1);  
    }  
    Node* temp = stack->top;  
    int value = temp->data;  
    stack->top = temp->next;  
    free(temp);  
    return value;  
}  

// 查看栈顶元素  
int peek(Stack* stack) {  
    if (isEmpty(stack)) {  
        printf("Error: Stack is empty.\n");  
        exit(1);  
    }  
    return stack->top->data;  
}  

// 销毁栈，释放所有节点内存  
void destroyStack(Stack* stack) {  
    Node* temp;  
    while (!isEmpty(stack)) {  
        temp = stack->top;  
        stack->top = stack->top->next;  
        free(temp);  
    }  
    free(stack);  
}  

// 主函数  
int main() {  
    Stack* stack = createStack();  

    // 入栈操作  
    push(stack, 1);  
    push(stack, 2);  
    push(stack, 3);  

    // 查看栈顶元素  
    printf("Top element: %d\n", peek(stack));  

    // 出栈操作  
    printf("Popped element: %d\n", pop(stack));  
    printf("Popped element: %d\n", pop(stack));  

    // 再次查看栈顶元素  
    printf("Top element: %d\n", peek(stack));  

    // 销毁栈  
    destroyStack(stack);  

    return 0;  
}

Go
package main  

import (  
    "errors"  
    "fmt"  
)  

// Node represents a node in the linked list.  
type Node struct {  
    value int  
    next  *Node  
}  

// Stack represents a stack that holds elements of type int.  
type Stack struct {  
    top *Node  
}  

// NewStack creates and returns a new Stack.  
func NewStack() *Stack {  
    return &Stack{}  
}  

// Push adds an element to the top of the stack.  
func (s *Stack) Push(value int) {  
    newNode := &Node{value: value}  
    if s.top != nil {  
        newNode.next = s.top  
    }  
    s.top = newNode  
}  

// Pop removes and returns the element at the top of the stack.  
// If the stack is empty, it returns an error.  
func (s *Stack) Pop() (int, error) {  
    if s.IsEmpty() {  
        return 0, errors.New("stack is empty")  
    }  
    value := s.top.value  
    s.top = s.top.next  
    return value, nil  
}  

// Peek returns the element at the top of the stack without removing it.  
// If the stack is empty, it returns an error.  
func (s *Stack) Peek() (int, error) {  
    if s.IsEmpty() {  
        return 0, errors.New("stack is empty")  
    }  
    return s.top.value, nil  
}  

// IsEmpty checks if the stack is empty.  
func (s *Stack) IsEmpty() bool {  
    return s.top == nil  
}  

func main() {  
    stack := NewStack()  

    // Push elements onto the stack  
    stack.Push(1)  
    stack.Push(2)  
    stack.Push(3)  

    // Peek the top element  
    top, err := stack.Peek()  
    if err != nil {  
        fmt.Println(err)  
    } else {  
        fmt.Println("Top element:", top)  
    }  

    // Pop elements from the stack  
    for !stack.IsEmpty() {  
        element, err := stack.Pop()  
        if err != nil {  
            fmt.Println(err)  
        } else {  
            fmt.Println("Popped element:", element)  
        }  
    }  

    // Verify that the stack is empty  
    if stack.IsEmpty() {  
        fmt.Println("Stack is empty")  
    }  
}