数据结构之栈

栈

栈：具有数据先入后出，先出后入的特性。
从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。
栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

用数组实现顺序栈

C代码结构体实现

#include<stdio.h>

#define maxsize 100

typedef struct{
    int data[maxsize];
    int topindex;
}SeqStack;

void push(SeqStack &stack, int value)
{
    if(stack.topindex == maxsize){
        printf("stack is full \n");
    }else{
        stack.data[stack.topindex] = value;
        stack.topindex++;
    }
}

void pop(SeqStack &stack)
{
    if(stack.topindex == 0){
        printf("stack is empty\n");
    }else{
        printf("pop %d\n", stack.data[--stack.topindex]);
    }
}

int isEmpty(SeqStack &stack)
{
    if(stack.topindex == 0){
        printf("stack is empty\n");
        return 1;
    }else{
        printf("stack is not empty \n");
        return 0;
    }
}

int main()
{
    SeqStack stack;
    stack.topindex = 0;
    
    push(stack, 5);
    push(stack, 4);
    push(stack, 3);
    pop(stack);
    pop(stack);
    isEmpty(stack);
    pop(stack);
    isEmpty(stack);
    pop(stack);
        
    
    return 0;
}

运行结果

pop 3
pop 4
stack is not empty
pop 5
stack is empty
stack is empty

c++类对象实现栈

#include<iostream>
using std::cout;
using std::cin;
using std::endl;

class Stack{
    private:
        int *data_;
        int max_size_;
        int top_;
        
        void initStack(){
            data_ = new int(max_size_);
            top_ = -1;
        }
    
    public:
        Stack(){
            max_size_ = 10;
            initStack();
        }
        
        Stack(int max_size){
            max_size_ = max_size;
            initStack();
        }
        
        ~Stack(){
            delete data_;
        }
        
        int isEmpty(){
            return (top_ == -1) ? 1:0;
        }
        
        int isFull(){
            return (top_ >= max_size_) ? 1:0;
        }
        
        int push(int x){
            if(isFull()) return 0;
            else data_[++top_] = x;
            
            return 1;
        }
        
        int pop(int &x){
            if(isEmpty()) return 0;
            else x = data_[top_--];
            
            return x;
        }
        
        void clear(){
            top_ = -1;
        }
};

int main()
{
    Stack stack(12);
    stack.push(123);
    stack.push(123);
    stack.push(456);
    int a;
    while(stack.pop(a)) {
        cout<<a<<endl;
    }
    return 0;
}

支持动态扩容的栈

当栈是由数组构建时，栈的内存有一定的限制。当栈内存满时，我们需要对栈进行动态扩容，这里只需要依赖一个可以动态扩容的数组即可，一个动态扩容的数组是当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据统统拷贝过去。这样就实现了一个支持动态扩容的数组。因此动态扩容的栈就是当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中。

栈的应用

函数调用
表达式求值：使用两个栈，一个存储操作数，一个存储符合
括号匹配：栈来存储未匹配的左括号，扫描到右括号时，左括号出栈并匹配。
实现浏览器的前进和后退