栈

栈是按后进先出的原则进行处理的。
栈也分为顺序存储和链式存储两种结构，分别称为顺序栈和链栈。若事先知道栈顶元素的范围，可以使用顺序栈结构，若栈中元素的数目变化范围很大，就要考虑使用链式存储结构。

//栈
//栈的顺序存储结构
//定义：
#include <stdio.h>
#define maximum 100
int top = -1;
int stack[maximum];
//初始化操作：
void CreateStack(int *stack, int len)
{
    if(len > maximum)
    {
        printf("长度超过数组的最大容量，无法创建");
        retrun ;
    }
    int value;
    for(int count = 0; count < len; count++)
    {
        scanf("%d", &value);
        stack[count] = value;
        top++;
    }
}
//入栈操作：
void Push(int *h, int value)
{
    if(top == maximum-1)
    {
        printf("栈已满\n");
        return ;
    }
    top++;
    h[top] = value;
    return ;
}
//出栈操作：
void Pop(int *h, int *e)
{
    if(top == -1)
    {
        printf("栈空\n");
        return ;
    }
    *e = h[top];
    top--;
    return ;
}
//计算栈长：
int StackLength()
{
    return top+1;
}
//取栈顶元素操作：
int GetTop(int *h)
{
    if(top == -1)
    {
        printf("Stack is Empty\n");
        return -1;
    }
    else
        return h[top];
}
//输出栈操作：
void StackDisplay(int *h)
{
    int count;
    if(top == -1)
    {
        printf("Stack is Empty\n");
        return;
    }
    for(count = top; count >= 0; count--)
        printf("%d ",h[count]);
    printf("\n");
    return ;
}
//栈的链式存储结构：
typedef struct stack{
    int data;
    struct stack *next;
}STACK;
STACK *top;
//初始化操作：
STACK *CreateStack()
{
    STACK *h;
    h = (STACK*)malloc(sizeof(STACK));
    h->next = NULL;
    top = NULL;
    return h;
}
//入栈操作：
void Push(int x)
{
    STACK *s;
    s = (STACK*)malloc(sizeof(STACK));
    s->data = x;
    if(top == NULL)
    {
        top = s;
        s->next = NULL;
    }
    else //注意s->next的指向是从栈顶向栈底的（从上往下）
    {
        s->next = top;
        top = s;
    }
    return ;
}
//出栈操作：
STACK *Pop(STACK *top, int *e)//先取出栈顶元素的值，再删除栈顶元素）
{
    STACK *p;
    if(top == NULL)
        printf("Stack is Empty\n");
    else
    {
        *e = top->data;
        p = top->next;
        free(top);
        top = p;
    }
    return top;
}//出栈操作之前需要先判断栈是否为空，然后取走栈顶元素的值，并释放结点
//取栈顶元素操作：（取栈顶元素值）
int Gettop(STACK* top)
{
    if(top == NULL)
        return NULL;
    else
        return top->data;
}
//求栈长操作：
int StackLength(STACK* top)
{
    STACK* p;
    int count = 0;
    p = top;
    while(p != NULL)
    {
        count++;
        p = p->next;
    }
    return count;
}//由于top不能移动，因此需要定义一个临时指针p 用它来遍历
//输出栈操作：
void Display(STACK* top)
{
    STACK* p;
    p = top;
    if(top == NULL)
        return;
    while(p != NULL)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return ;
}

栈的应用：

表达式求和：

为了实现运算符的优先算法，可以使用两个栈：一个存操作数operand，一个存运算符oper。依次读入字符，如果是操作数则进operand，如果是运算符，就要判断该运算符与oper中栈顶的运算符的优先级，如果低于栈顶运算符的优先级，就取出oper栈顶的操作符和两个operand栈顶操作数，计算完后将结果重新存入operand栈顶。最后再不断取出两个操作数和一个运算符然后将结果重新放入operand中。

//表达式求和：
void ExpressionComputation()
{
    STACK *oper = NULL, *operand = NULL;//栈顶指针
    char expression[50];
    int position = 0;
    char op;//保存运算符
    char operand1, operand2;//保存操作数
    int selection;//判断是运算符还是操作数
    double result;
    
    gets(expression);//读入字符表达式
    while(expression[position] != '\0' && expression[position] != '\n')
    {
        switch(expression[position])
        {
            case '+':case '-':case '*':case '/':case '%':
                selection = 1;
                break;
            default: selection = 0;
        }
        if(selection == 1)
        {
            if(oper != NULL)
                while(Priority(expression[position]) < Priority(oper->data))//表达式中的符号优先级低于栈顶元素
                {
                    operand = Pop(operand, &operand1);//取出操作数
                    operand = Pop(operand, &operand2);
                    oper = Pop(oper, &op);
                    result = ObtainResult(op, operand2, operand1);
                    operand = Push(operand, result+48);
                    if(oper == NULL)
                        break;
                }
            oper = Push(oper, expression[position]);
        }
        else
            operand = Push(operand, expression[position]);
        position++;
    }
    while(oper != NULL)
    {
        oper = Pop(oper, &op);
        operand = Pop(operand, &operand1);
        operand = Pop(operand, &operand2);
        result = ObtainResult(op, operand2, operand1);
        operand = Push(operand, result+48);
    }
    printf("%c",operand->data);
}//此程序中数字是字符形式，需要通过ASCII码转换成实际的数字，因此需要加上48

数制转换：

十进制数和其他数值的转换：
N = （N div d）+ N mod d 【N为十进制数， d为需要转换的数制的基数， div为整除， mod为求余】

//数制转换:
void Conversion(STACK *top, int N, int div)
{
    while(N)
    {
        top = Push(top, N%div);
        N = N/div;
    }
    int e, len = StackLength(top);
    for(int i=1; i<=len; i++)
    {
        top = Pop(top, &e);
        printf("%d ",e);
    }
    printf("\n");
}

括号匹配检验：

//括号匹配检验：
void BracketMatch(STACK *top, char *b)
{
    STACK *p;
    char temp;
    int i = 0;
    while(b[i] != '!')
    {
        switch(b[i])
        {
            case '{':
            case '[':
            case '(':
                top = Push(top, b[i]);
                i++;
                break;
            case '}':
                if(Getop(top) == '{')
                    top = Pop(top, &temp);
                i++;
                break;
            case ')':
                if(Getop(top) == '(')
                    top = Pop(top, &temp);
                i++;
                break;
            case ']':
                if(Getop(top) == '[')
                    top = Pop(top, &temp);
                i++;
                break;
        }
    }
}//本算法以左侧括号为基准，右括号作为匹配部分，因此令左括号入栈，右括号不入栈。

栈与递归的实现：

实例只是说明栈和递归可以这样用，算n！不用这样。。。

//用栈实现n！的具体算法：
void Push(int *h, int value)
{
    if(top == maximum-1)
    {
        printf("栈已满\n");
        return;
    }
    top++;
    h[top] = value;
    return;
}
//叠代计算
int Pile(int *h, int n)
{
    int a;
    if(n == 0)
        return 1;
    else
        Push(h,n*Pile(h, n-1));
    return h[top];
}

利用栈寻找迷宫路径：

//递归的执行过程可以利用栈结构来保存数据和返回地址
//利用栈寻找迷宫路径：
#include <stdio.h>
#define H 6
#define W 6
#define maximum 20
int map[H][W] =
{
    {1,1,1,1,1,1},
    {1,0,0,0,1,1},
    {1,0,1,0,0,1},
    {1,0,0,0,1,1},
    {1,1,0,0,0,1},
    {1,1,1,1,1,1},
};
int top = -1;
int mindirections = maximum;
struct s{
    int i;
    int j;
    int direction;
}Stack[maximum], Path[maximum];
void maze()
{
    int count = -1;
    int i, j, direction, find;
    top++;
    Stack[top].i = 1; Stack[top].j = 1;
    Stack[top].direction = -1;
    map[1][1] = -1;
    
    while(top > -1)
    {
        i = Stack[top].i; j = Stack[top].j;
        direction = Stack[top].direction;
        if(i == H-2 && j == W-2)
        {
            for(int k=0; k<=top; k++)
            {
                printf("[%d,%d]",Stack[k].i,Stack[k].j);
                if((k+1)%5==0)
                    printf("\n");
            }
            printf("\n");
            if(top+1<mindirections)
            {
                for(int k=0; k<=top; k++)
                    Path[k] = Stack[k];
                mindirections = top+1;
            }
            map[Stack[top].i][Stack[top].j] = 0;
            top--;
            i = Stack[top].i; j = Stack[top].j;
            direction = Stack[top].direction;
        }
        find = 0;
        while(direction < 4 && find == 0)
        {
            direction++;
            switch(direction)
            {
                case 0: i=Stack[top].i-1;j=Stack[top].j;break;
                case 1: i=Stack[top].i;j=Stack[top].j+1;break;
                case 2: i=Stack[top].i+1;j=Stack[top].j;break;
                case 3: i=Stack[top].i;j=Stack[top].j-1;break;
            }
            if(map[i][j] == 0) find = 1;
        }
        if(find == 1)
        {
            Stack[top].direction = direction;
            top++;
            Stack[top].i = i;
            Stack[top].j = j;
            Stack[top].direction = -1;
            map[i][j] = -1;
        }
        else
        {
            map[Stack[top].i][Stack[top].j] = 0;
            top--;
        }
    }
    printf("最短路径长度：%d\n",mindirections);
    printf("最短路径：\n");
    for(int k = 0; k < mindirections; k++)
    {
        printf("[%d,%d] ",Path[k].i,Path[k].j);
    }
    printf("\n");
}
int main()
{
    printf("迷宫所有路径：\n");
    maze();
}

#include <vector>
#include <iostream>
using namespace std;

#define MAX_SIZE  10

template <typename T> class Stack{
private:
	vector<T> sstack; 
	int size;
public:
	Stack();
	~Stack();
	void push(T const& e);
	T pop();
	T& top();
	bool isFull()const;
	bool isEmpty()const;
	int getsize()const;
	void clear();
}; 

template <typename T>
Stack<T>::Stack(){
	this->size = 0;
} 

template <typename T>
Stack<T>::~Stack(){

}

template <typename T>
void Stack<T>::push(T const& e){
	if(this->isFull())
		return;
	this->sstack.push_back(e);
	size++;
}

template <typename T>
T Stack<T>::pop(){
	if(this->isEmpty())
	{
		cout << "Wrong" << endl;
		return 0;
	}
	T ret = this->sstack[this->size-1];
	this->sstack.erase(this->sstack.begin()+this->size-1);
	size--;
	return ret;
}

template <typename T>
T& Stack<T>::top(){
	return this->sstack[this->size-1];
}

template <typename T>
bool Stack<T>::isFull()const{
	return (this->size == MAX_SIZE);
}

template <typename T>
bool Stack<T>::isEmpty()const{
	return (this->size == 0);
}

template <typename T>
int Stack<T>::getsize()const{
	return this->size;
}

template <typename T>
void Stack<T>::clear(){

}

int main(){
	Stack<int> test;
	cout << "The size: " << test.getsize() << endl;
	cout << "Is Empty?  " << test.isEmpty() << endl;
	for(int i=0; i<10; i++)
	{
		cout << "Push: " << i << endl;
		test.push(i);
	}	
	cout << "The size: " << test.getsize() << endl;
	for(int i=0; i<5; i++)
		cout << "Pop: " << test.pop() << endl;
	cout << "The size: " << test.getsize() << endl;
	cout << "Is Empty?  " << test.isEmpty() << endl;
	
	return 0;
}

#include <iostream>
using namespace std;

template <typename K>
struct Node
{
	K data;
	Node<K>* next;
};

template <typename T> class LinkedStack{
private:
	int size;
	Node<T>* StackHead;
public:
	LinkedStack();
	~LinkedStack();
	void push(T e);
	T pop();
	bool isEmpty()const;
	int getSize()const;
};


template <typename T>
LinkedStack<T>::LinkedStack(){
	this->size = 0;
	StackHead = new Node<T>; 
	StackHead->next = NULL; 
}

template <typename T>
LinkedStack<T>::~LinkedStack(){
	while(this->size > 0)
	{
		this->pop();
	}
	delete this->StackHead;
}


template <typename T>
void LinkedStack<T>::push(T e){
	Node<T>* tmpCell = new Node<T>;
	tmpCell->data = e;
	tmpCell->next = this->StackHead->next;
	this->StackHead->next = tmpCell;
	this->size++;
}

template <typename T>
T LinkedStack<T>::pop(){
	if(isEmpty())
	{
		cout << "Empty Wrong" << endl;
		return -1;
	}
	Node<T>* FirstCell;
	T TopElem;
	FirstCell = this->StackHead->next;
	TopElem = FirstCell->data;
	this->StackHead->next = FirstCell->next;
	delete FirstCell;
	this->size--;
	return TopElem;
}

template <typename T>
bool LinkedStack<T>::isEmpty()const{
	return (this->size == 0);
}

template <typename T>
int LinkedStack<T>::getSize()const{
	return this->size;
}


int main(){
	LinkedStack<int> test;
	cout << "The size: " << test.getSize() << endl;
	cout << "Is Empty?  " << test.isEmpty() << endl;
	for(int i=0; i<10; i++)
	{
		cout << "Push: " << i << endl;
		test.push(i);
	}	
	cout << "The size: " << test.getSize() << endl;
	for(int i=0; i<5; i++)
		cout << "Pop: " << test.pop() << endl;
	cout << "The size: " << test.getSize() << endl;
	cout << "Is Empty?  " << test.isEmpty() << endl;
	
	return 0;
}

#include <iostream>
using namespace std;

template <typename T> 
struct Node
{
	T data;
	Node<T>* next;
};


template <typename T> class LinkedQueue{
private:
	int size;
	Node<T>* QueueHead;
public:
	LinkedQueue();
	~LinkedQueue();
	int getSize()const;
	bool isEmpty()const;
	T getFront()const;
	T getBack()const;
	void push(T e);
	T pop();
};

template <typename T>
LinkedQueue<T>::LinkedQueue(){
	this->size = 0;
	this->QueueHead = new Node<T>;
	this->QueueHead->next = NULL;
}

template <typename T>
LinkedQueue<T>::~LinkedQueue(){
	while(this->size > 0)
	{
		this->pop();
	}
	delete this->QueueHead;
}


template <typename T>
int LinkedQueue<T>::getSize()const{
	return this->size;
}

template <typename T>
bool LinkedQueue<T>::isEmpty()const{
	return (this->size == 0);
}

template <typename T>
T LinkedQueue<T>::getFront()const{
	if(this->size == 0)
	{
		cout << "isEmpty Wrong" << endl;
		return -1;
	}
	return this->QueueHead->next->data;
}

template <typename T>
T LinkedQueue<T>::getBack()const{
	if(this->size == 0)
	{
		cout << "isEmpty Wrong" << endl;
		return -1;
	}
	Node<T>* cur = this->QueueHead;
	while(cur->next != NULL)
	{
		cur = cur->next;
	}
	return cur->data;
}


template <typename T>
void LinkedQueue<T>::push(T e){
	Node<T>* cur = this->QueueHead;
	while(cur->next != NULL)
	{
		cur = cur->next;
	}
	Node<T>* ans = new Node<T>;
	ans->data = e;
	ans->next = NULL;
	cur->next = ans;
	this->size++;
}

template <typename T>
T LinkedQueue<T>::pop(){
	if(this->size == 0)
	{
		cout << "isEmpty Wrong" << endl;
		return -1;
	}
	Node<T>* delNode = this->QueueHead->next;
	this->QueueHead->next = delNode->next;
	T retdata = delNode->data;
	delete delNode;
	this->size--;
	return retdata;
}


int main(){
	LinkedQueue<int> test;
	cout << "The size: " << test.getSize() << endl;
	cout << "Is Empty?  " << test.isEmpty() << endl;
	for(int i=0; i<10; i++)
	{
		cout << "Push: " << i << endl;
		test.push(i);
	}	
	cout << "The size: " << test.getSize() << endl;
	for(int i=0; i<5; i++)
		cout << "Pop: " << test.pop() << endl;
	cout << "The size: " << test.getSize() << endl;
	cout << "Is Empty?  " << test.isEmpty() << endl;
	cout << "Now the front: " << test.getFront() << endl;
	cout << "Now the back: " << test.getBack() << endl;
	return 0;
}