栈.md

栈

• 定义
  • "先进后出"的存储结构
• 分类
  • 静态栈
  • 动态栈
• 算法操作
  • 出栈
  • 入栈/压栈
• 应用
  • 函数调用
  • 中断
  • 表达式求值
  • 内存分配
  • 缓冲处理
  • 迷宫

---

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

// --------------------------
typedef struct Node{
    int data;
    struct Node * pNext;
}NODE, *PNODE;

typedef struct Stack{
    PNODE pTop;
    PNODE pBottom;  // pBottom中无有效数据, pBottom->pNext = NULL;
}STACK, *PSTACK;
// --------------------------

void init(PSTACK s);
void push(PSTACK s, int num);
void traverse(PSTACK s);
int pop(PSTACK s);
void delete(PSTACK s);
bool isEmpty(PSTACK s);

int main(void)
{
    STACK s;
    
    init(&s);
    push(&s, 1);
    push(&s,2);
    push(&s, 3);
    push(&s, 4);
    traverse(&s);
    
    printf("%d.\n",pop(&s));
    printf("%d.\n",pop(&s));
    printf("%d.\n",pop(&s));
    printf("%d.\n",pop(&s));
    printf("%d.\n",pop(&s));
    traverse(&s);
    
    delete(&s);
    traverse(&s);
}

//void init(PSTACK s){
//    PNODE guard = (PNODE)malloc(sizeof(NODE));    // 无需额外定义哨兵
//    if(guard == NULL)
//        exit(-1);
//    s->pBottom = guard;
//    s->pTop = guard;
//    guard->pNext = NULL;
//    guard = NULL;
//}

void init(PSTACK s){
    s->pBottom = (PNODE)malloc(sizeof(NODE));
    if(s->pBottom == NULL)
        exit(-1);
    s->pTop = s->pBottom;
    s->pBottom->pNext = NULL;
}

void push(PSTACK s, int num)
{
    PNODE node = (PNODE)malloc(sizeof(NODE));
    if(node == NULL)
        exit(-1);
    node->data = num;
    node->pNext = s->pTop;
    s->pTop = node;
}

int pop(PSTACK s)
{
    if(isEmpty(s))
    {
        return INT_MIN;
    }
    int num = s->pTop->data;
    PNODE node = s->pTop;
    s->pTop = s->pTop->pNext;
    free(node);
    node = NULL;
    return num;
}

void traverse(PSTACK s)
{
//    if(isEmpty(s))    // 测试用
//    {
//        printf("Stack Empty.\n");
//        return;
//    }
    PNODE t = s->pTop;
    while(s->pBottom != t)
    {
        printf("%d ", t->data);
        t = t->pNext;
    }
    printf("\n");
}

void delete(PSTACK s)
{
    while(s->pBottom != s->pTop)
    {
        pop(s);
    }
    
    if(isEmpty(s)){
        free(s->pBottom);
        s->pBottom = NULL;
    }
    
}

bool isEmpty(PSTACK s)
{
    return s->pTop == s->pBottom;
}

---

#include <iostream>

template <class T>
class Node{
public:
    T data;
    Node<T> * pNext;
};

template <class T>
class Stack{
public:
    Stack();
    ~ Stack();
    void push(T val);
    bool pop();
    bool isEmpty();
    void clear();
    void show();
private:
    Node<T> * pTop;
    Node<T> * pBottom;
};

template <class T>
Stack<T>::Stack(){
    pBottom = nullptr;
    pTop = nullptr;
    pBottom = new Node<T>();
    pTop = pBottom;
    pBottom->pNext = nullptr;
}

template <class T>
Stack<T>::~Stack(){
    if(pBottom != nullptr)
        delete pBottom;
}
template <class T>
void Stack<T>::push(T val)
{
    Node<T>* p = new Node<T>();
    p->data = val;
    p->pNext = pTop;
    pTop = p;
}
template <class T>
bool Stack<T>::isEmpty()
{
    return pTop == pBottom;
}
template <class T>
bool Stack<T>::pop()
{
    if(isEmpty())
        return false;
    Node<T>* p = pTop;
    pTop = pTop->pNext;
    delete p;
    p = nullptr;
    return true;
}
template <class T>
void Stack<T>::clear()
{
    if(isEmpty())
        return;
    while(!isEmpty())
    {
        pop();
    }
}

template <class T>
void Stack<T>::show(){
    std::cout << "----STACK----: ";
    Node<T>* p = pTop;
    while(p != pBottom)
    {
        std::cout << p->data << " ";
        p = p->pNext;
    }
    std::cout << std::endl;
}
int main(void)
{
    Stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.show();
    
    for(int i = 0; i < 3; ++i)
    {
        if(s.pop())
            std::cout << "SUCCESS" << std::endl;
        else
            std::cout << "FAIL" << std::endl;
    }
    s.show();
    
    
    
    
    return 0;
}