数据结构（三）-- 栈、队列

#include <iostream>
#define StackSize 100	//栈长度

using namespace std;

class SeqStack {

private:
    int data[StackSize];	//线性栈表
    int top;	//纪录栈顶

public:
    SeqStack(){top=-1;};    //将项顶指针置为-1
    ~SeqStack(){}

    void Push(int x){
    	if (top==StackSize-1){
			cout<<"栈满"<<endl;
			return;
		}
		top++;
		data[top] = x;
	}

	//弹栈
    int Pop(){
    	if (top==-1){
			cout<<"栈空"<<endl;
			return;
		}
    	return data[top];
    	top--
    }	//版本1：取出栈顶元素
	//一般是用版本1，所以版本2不看了
	
    int GetTop(){
		if (top==-1){
			cout<<"栈空"<<endl;
			return;
		}
		return data[top];
	}//获取栈顶元素

    int Empty(){
	if (top==-1) 
        return 1;
	} //判断是否为空	
};

#include <iostream>

using namespace std;

const int defaultSize = 50;         //默认栈空间大小
const int stackIncreament = 20;     //栈溢出时扩展空间的增量
const int n = 2;                    //设置n=2个栈共有一个栈空间

class DualStack
{
public:
    DualStack(int sz = defaultSize);        //构造函数
    ~DualStack();                           //析构函数
public:
    bool Push(const T& x, int d) ;      //新元素x进栈
    bool Pop(T& x, int d);              //栈顶元素出栈，并将该元素的值保存至x
    bool getTop(T& x, int d) const;     //读取栈顶元素，并将该元素的值保存至x
    bool IsEmpty() const;               //判断栈是否为空
    bool IsFull() const;                //判断栈是否为满
    int getSize() const;                //计算栈中元素个数
    void MakeEmpty();                   //清空栈的内容
    void overflowProcess();             //栈的溢出处理
    
private:
	int *vec;			//存放栈中元素
    int top[n-1];     //栈顶指针
    int maxSize;    //栈最大可容纳元素个数
};

//构造函数
DualStack::DualStack(int sz)
{
    if (sz >= 0)
    {
    	maxSize = sz;           
    	top[0] = -1;
    	top[1] = maxSize;
			vec = new int[maxSize];
    }
}                       

//析构函数
DualStack::~DualStack()
{
    delete[] vec;
    vec = NULL;
}   

//新元素x进栈
bool DualStack::Push(const int x, int d)
{
    if (true == IsFull())
        return false;
    if (0 == d)
        top[0]++;
    else
        top[1]--;
    vec[top[d]] = x;
    return true;
}

//栈顶元素出栈，并将该元素的值保存至x
bool DualStack::Pop(int x, int d)
{
    if (true == IsEmpty())
        return false;
    x = vec[top[d]];
    if (0 == d)
        top[0]--;
    else
        top[1]++;
    return true;
}

//读取栈顶元素，并将该元素的值保存至x
bool DualStack::getTop(int x, int d) const
{
    if (true == IsEmpty())
        return false;
    x = vec[top[d]];
    return true;
}

//判断栈是否为空
bool DualStack::IsEmpty() const
{
    return ((-1 == top[0]) && (maxSize == top[1])) ? true : false;
}

//判断栈是否为满
bool DualStack::IsFull() const
{
    return (top[0] + 1 == top[1]) ? true : false;
}

//计算栈中元素个数
int DualStack::getSize() const
{
    return (top[0] + 1) + (maxSize - top[1]);
}

//清空栈的内容
void DualStack::MakeEmpty()
{
    delete[] vec;
    top[0] = -1;
    top[1] = maxSize;
    vec = new int[maxSize];
    //如果用vector容器的话，就直接清空了
    //但是为了普遍性，还是把STL收起来了
}

//栈的溢出处理
void DualStack::overflowProcess()
{
    int newSize = maxSize + stackIncreament;
    int *neweVector = new int[newSize];
    for (int i = 0; i <= top[0]; i++)
    {
        neweVector[i] = vec[i];
    }
    for (int i = maxSize - 1; i >= top[1]; i--)
    {
        neweVector[i + stackIncreament] = vec[i];
    }
    delete[] vec;
    vec= neweVector;
    maxSize = newSize;
    top[1] += stackIncreament;
}

在实现数据"入栈"操作时，需要将数据从链表的头部插入；
在实现数据"出栈"操作时，需要删除链表头部的首元节点；

//链表中的节点结构
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;

//stack为当前的链栈，a表示入栈元素

lineStack* push(lineStack * stack,int a){
    //创建存储新元素的节点
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    //新节点与头节点建立逻辑关系
    line->next=stack;
    //更新头指针的指向
    stack=line;
    return stack;
}

//栈顶元素出链栈的实现函数
lineStack * pop(lineStack * stack){
    if (stack) {
        //声明一个新指针指向栈顶节点
        lineStack * p=stack;
        //更新头指针
        stack=stack->next;
        printf("出栈元素：%d ",p->data);
        if (stack) {
            printf("新栈顶元素：%d\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}

a是起始柱，c是目标柱，b起到中转作用

void main()
{
	int n = 64;	//可以泛化
	
	Stack a = init_stack();
	Stack b = init_stack();
	Stack c = init_stack();
	while(n-->0){// 初始化栈a，代表最左边柱子和盘子
		 push_stack(a,i); 
	}
	hanoi(n,a,b,c); 
}

void hanoi(int n,Stack a,Stack b,Stack c)
{
	if(n == 1) // 盘子数为1
		pop_push(a,c);
	else
	{
		hanoi(n-1,a,c,b); // 将栈a的n-1个盘子顺序移到栈b
		pop_push(a,c); // 将栈a的第n个盘子移到栈c
		hanoi(n-1,b,c,a); // 将栈b的n-1个盘子顺序移到栈c
	}
}

输入：中缀表达式串

输出：后缀表达式串

PROCESS BEGIN:

   1.从左往右扫描中缀表达式串s，对于每一个操作数或操作符，执行以下操作;

                2.IF (扫描到的s[i]是操作数DATA)

　　　　　    将s[i]添加到输出队列中;

               3.IF (扫描到的s[i]是开括号'(')

                        将s[i]压栈;

               4.WHILE (扫描到的s[i]是操作符OP)

                       IF (栈为空 或 栈顶为'(' 或 扫描到的操作符优先级比栈顶操作符高)

                             将s[i]压栈;

                             BREAK;

                       ELSE

                             出栈至输出队列中

               5.IF (扫描到的s[i]是闭括号')')

                       栈中运算符逐个出栈并输出，直到遇到开括号'(';

                       开括号'('出栈并丢弃;

               6.返回第1.步

　　       7.WHILE (扫描结束而栈中还有操作符)

                        操作符出栈并加到输出队列中

PROCESS END

#ifndef _STACK_H_
#define _STACK_H_

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

#define SIZE 10

typedef struct node
{
    int data;
    struct node *next;
}Node;

typedef struct stack
{
    Node *top;
}Stack;

void Init(Stack *s);

int Empty(Stack *s);

void Push(Stack *s, int data);

void Pop(Stack *s);

int GetTop(Stack *s);

#endif 

#include "stack.h"


void Init(Stack *s)
{
    if (NULL == s)
        return;

    s->top = NULL;
}

int Empty(Stack *s)
{
    if (NULL == s)
        return 0;

    if (NULL == s->top)
        return 1;

    return 0;
}

void Push(Stack *s,int data)
{
    if (NULL == s)
        return;

    Node *node = (Node *)malloc(sizeof(Node)/sizeof(char));
    if (NULL == node)
        return;

    node->data = data;
    node->next = s->top;
    s->top = node;
}

void Pop(Stack *s)
{
    if (NULL == s)
        return;

    if (Empty(s) == 1)
        return;

    Node *tmp = s->top;
    s->top = tmp->next;
    free(tmp);
}

int GetTop(Stack *s)
{
    if (NULL == s)
        return;

    if (Empty(s) == 1)
    {
        printf ("无栈顶元素\n");
        exit(-1); 
    }

    return s->top->data;
}

#include <stdio.h>
#include "stack.h"
#include <string.h>

int Ope_judge(Stack *s_ope,int ope)
{
    if(Empty(s_ope))
        return 1;

    int top = GetTop(s_ope);

    switch(top)
    {
        case '+':
        case '-':
            if(ope == '*' || ope == '/' || ope == '(')
                return 1;
            break;
        case '*':
        case '/':
            if( ope == '(')
                return 1;
            break;
        case '(':
            if(ope == ')')
            {
                Pop(s_ope);
            }
            return 1;
        default :
            break;
    }

    return 0;
}

void Calc(Stack *s_ope,Stack *s_num)
{
    int num1 = GetTop(s_num);
    Pop(s_num);

    int num2 = GetTop(s_num);
    Pop(s_num);

    int ope = GetTop(s_ope);
    Pop(s_ope);

    int res;
    switch(ope)
    {
        case '+':
            res = num2 + num1;
            break;
        case '-':
            res = num2 - num1;
            break;
        case '*':
            res = num2 * num1;
            break;
        case '/':
            res = num2 / num1;
            break;
        default:
            break;
    }
    Push(s_num,res);
}


void Ope_deal(Stack *s_ope,Stack *s_num,int ope)
{
    if(Ope_judge(s_ope,ope) == 1)
    {
        Push(s_ope,ope);
    }
    else
    {
        while(Ope_judge(s_ope,ope) == 0)
        {
            Calc(s_ope,s_num);
        }

        if(ope != ')')
            Push(s_ope,ope);
    }

}

int main()
{
    char buf[100];
    fgets(buf,100,stdin);
    buf[strlen(buf)-1] = '\0';

    Stack s_num;
    Stack s_ope;

    Init (&s_num);
    Init (&s_ope);

    char *p = buf;
    while(*p)
    {
        if(*p >= '0' && *p <= '9')
        {
            int num = 0;
            while(*p >= '0' && *p <= '9')
            {
                num = num *10 + *p - '0';
                p++;
            }

            Push(&s_num , num);
            continue;
        }
        Ope_deal(&s_ope,&s_num,*p);
        p++;
    }

        while(!Empty(&s_ope))
        {
            Calc(&s_ope,&s_num);
        }

        int res = GetTop(&s_num);

        printf ("计算结果为：%d\n", res);


    return 0;
}

//两个栈实现队列
class stack_to_queue {
private:
	stack *s1, *s2;
	int flag;
public:
	stack_to_queue() {
		flag = 0;
		s1 = new stack();
		s2 = new stack();
	}

	void push(int value) {
		s1->push(value);
	}

	int pop() {
		if (s2->isempty()) {
			if(!s1->isempty()){
				while (!s1->isempty()) {
					s2->push(s1->pop());
				}
				int res = s2->pop();
				return res;
			}
			else
				return NULL;
		}
		else {
			int res = s2->pop();
			return res;
		}
	}

	int get_top() {
		if (!s2->isempty()) {
			return s2->get_top();
		}
		else {
			if (!s1->isempty()) {
				while (!s1->isempty()) {
					s2->push(s1->pop());
				}
				return s2->get_top();
			}
			else
				return NULL;
		}
	}
};

//两个队列实现栈
class queue_to_stack {
private:
	queue* q1, * q2;
	int flag;
public:
	queue_to_stack() {
		flag = 0;	
		q1 = new queue();
		q2 = new queue();
	}

	void push(int value) {
		if (flag) {
			q1->push(value);
		}
		else {
			q2->push(value);
		}
		
	}

	int pop() {
		if (q1->isempty() && q2->isempty())
			return NULL;
		else {
			if (flag) {
				flag--;
				while (!q1->only_one()) {
					q2->push(q1->pop());
				}
				return q1->pop();
			}
			else {
				flag++;
				while (!q2->only_one()) {
					q1->push(q2->pop());
				}
				return q2->pop();
			}
		}
	}

	int get_top() {
		//跟上面改动不多，不写了
	}
};