数据结构-栈

栈和队列

#include <stack>
#include <queue>
#include <stdio.h>
using namespace std;
int main()
{
    // 栈，先进后出
    stack<int> s;
    for (int i = 0; i < 10; i++)
        s.push(i);
    while (!s.empty())
    {
        int data = s.top();
        printf("%d ", data); //9 8 7 6 5 4 3 2 1 0
        s.pop();
    }
    printf("\n");

    // 队列，先进先出
    queue<int> q;
    for (int i = 0; i < 10; i++)
        q.push(i);
    while (!q.empty())
    {
        int data = q.front();
        printf("%d ", data); //0 1 2 3 4 5 6 7 8 9
        q.pop();
    }

    return 0;
}

进制转换

// 栈Stack
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

// 进制转换问题
void Convert(char *buffer, int value, int base)
{
    const char *DATA = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    // create a stack, name it S, the data that stores in it is char
    stack<char> S;

    while (value != 0)
    {
        int d = value % base;
        char D = d >= 10 ? 'A' + d - 10 : '0' + d; //大于10进制就用字母
        // D = DATA[d];
        S.push(D); //D进栈
        value /= base;
    }
    if (S.empty()) //如果是空栈
        S.push('0');

    while (!S.empty()) //不空
    {
        *buffer++ = S.top(); //返回栈顶元素，存入buffer[]
        S.pop();             //移除栈顶元素
    }
    *buffer = '\0';
}

int main()
{
    char buffer[1024];
    int value, base;

    cout << "请输入一个数value和需要转换成的进制base。例：16 2" << endl;
    cin >> value >> base;

    // 在buffer中填写value的base进制表示串
    Convert(buffer, value, base);

    cout << buffer << endl;
    return 0;
}

车厢调度

// 车厢调度问题
// 用顺序表模拟栈，描述站台结构
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

const int MAXBUFFERLEN = 100;

struct Stack
{
    int buffer[MAXBUFFERLEN];
    int top; // top指向下一节车厢进入站台的位置
};
//初始化
int InitStack(Stack &S)
{
    S.top = 0;
    return 0;
}
int push(Stack &S, int data) //主要函数
{
    if (S.top >= MAXBUFFERLEN)
        return -1;

    S.buffer[S.top] = data; //初始化中 S.top=0
    S.top++;

    return 0;
}

int pop(Stack &S)
{
    S.top--;
    return 0;
}

int empty(const Stack S) //不用&s，因为不修改s
{
    return S.top <= 0; //判断是否为空，返回真假10
}

int top(const Stack S) //主要函数,
{
    return S.buffer[S.top - 1];
}

int main()
{
    int command, n = 1, m;
    struct Stack S;
    InitStack(S);

    //先进后出
    cout << "请输入进出栈命令: 0表示车厢进站；1表示车厢出站" << endl;
    while (cin >> command)
    {
        if (command == 0)
        {
            if (push(S, n) != 0)
                cout << "站台已满！" << endl;
            else
            {
                cout << "车厢 " << n << " 运货进入站台。" << endl;
                n++;
            }
        }
        else if (command == 1)
        {
            if (empty(S))
                cout << "站台上没有车厢！" << endl;
            else
            {
                m = top(S);
                pop(S);
                cout << "车厢 " << m << " 运货出站。" << endl;
            }
        }
    }
    return 0;
}

栈

#include <stdio.h>
#include <stdlib.h>
typedef char DataType;
#define StackSize 100
typedef struct
{
    DataType stack[StackSize];
    int top;
} SeqStack;

void InitStack(SeqStack *S)
/*将栈初始化为空栈只需要把栈顶指针top置为0*/
{
    S->top = 0; /*把栈顶指针置为0*/
}
int StackEmpty(SeqStack S)
/*判断栈是否为空，栈为空返回1，否则返回0*/
{
    if (S.top == 0) /*判断栈顶指针top是否为0*/
        return 1;   /*当栈为空时，返回1；否则返回0*/
    else
        return 0;
}
int GetTop(SeqStack S, DataType *e)
/*取栈顶元素。将栈顶元素值返回给e，并返回1表示成功；否则返回0表示失败。*/
{
    if (S.top <= 0) /*在取栈顶元素之前，判断栈是否为空*/
    {
        printf("栈已经空!\n");
        return 0;
    }
    *e = S.stack[S.top - 1]; /*在取栈顶元素*/
    return 1;
}
int PushStack(SeqStack *S, DataType e)
/*将元素e进栈，元素进栈成功返回1，否则返回0.*/
{
    if (S->top >= StackSize) /*在元素进栈前，判断是否栈已经满*/
    {
        printf("栈已满，不能进栈！\n");
        return 0;
    }
    S->stack[S->top] = e; /*元素e进栈*/
    S->top++;             /*修改栈顶指针*/
    return 1;
}
int PopStack(SeqStack *S, DataType *e)
/*出栈操作。将栈顶元素出栈，并将其赋值给e。出栈成功返回1，否则返回0*/
{
    if (S->top <= 0) /*元素出栈之前，判断栈是否为空*/
    {
        printf("栈已经没有元素，不能出栈!\n");
        return 0;
    }
    S->top--;              /*先修改栈顶指针，即出栈*/
    *e = S->stack[S->top]; /*将出栈元素赋值给e*/
    return 1;
}
int StackLength(SeqStack S)
/*求栈的长度，即栈中元素个数，栈顶指针的值就等于栈中元素的个数*/
{
    return S.top;
}

int main()
{
    DataType a[] = {'a', 'b', 'c', 'd', 'e'};
    DataType e;

    SeqStack S;
    InitStack(&S);

    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
        if (PushStack(&S, a[i]) == 0)
        {
            printf("栈已满，不能进栈！");
            return 0;
        }

    printf("出栈的元素是：");
    if (PopStack(&S, &e) == 1)
        printf("%4c", e);
    if (PopStack(&S, &e) == 1)
        printf("%4c", e);

    printf("\n当前栈顶的元素是：");
    if (GetTop(S, &e) == 0)
    {
        printf("栈已空！");
        return 0;
    }
    else
        printf("%4c\n", e);

    if (PushStack(&S, 'f') == 0)
    {
        printf("栈已满，不能进栈！");
        return 0;
    }
    if (PushStack(&S, 'g') == 0)
    {
        printf("栈已满，不能进栈！");
        return 0;
    }

    printf("当前栈中的元素个数是：%d\n", StackLength(S));
    printf("元素出栈的序列是：");
    while (!StackEmpty(S))
    {
        PopStack(&S, &e);
        printf("%4c", e);
    }
    return 0;
}

带头结点的链栈

#include <stdio.h>      
#include <string.h>    /*包含字符串长度函数*/
#include <malloc.h>    /*包含内存分配函数*/
typedef char DataType; /*类型定义为字符类型*/

typedef struct node
{
    DataType data;
    struct node *next;
} LStackNode, *LinkStack;

void InitStack(LinkStack *top)
/*将链栈初始化为空。动态生成头结点，并将头结点的指针域置为空。*/
{
    *top = (LinkStack)malloc(sizeof(LStackNode));
    (*top)->next = NULL; /*将链栈的头结点指针域置为空*/
}
int StackEmpty(LinkStack top)
/*判断链栈是否为空，就是通过判断头结点的指针域是否为空*/
{
    if (top->next == NULL) /*判断链栈头结点的指针域是否为空*/
        return 1;          /*当链栈为空时，返回1；否则返回0*/
    else
        return 0;
}
int PushStack(LinkStack top, DataType e)
/*进栈操作就是要在链表的第一个结点前插入一个新结点，进栈成功返回1*/
{
    /*定义指向第i个元素的前驱结点指针pre，指针p指向新生成的结点*/
    LStackNode *p = (LStackNode *)malloc(sizeof(LStackNode));
    p->data = e;
    p->next = top->next; /*将结点插入到栈顶*/
    top->next = p;
    return 1;
}
int PopStack(LinkStack top, DataType *e)
/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/
{
    LStackNode *p = top->next;
    if (StackEmpty(top)) /*判断堆栈是否为空*/
    {
        printf("栈已空");
        return 0;
    }
    top->next = p->next; /*将栈顶结点与链表断开，即出栈*/
    *e = p->data;        /*将出栈元素赋值给e*/
    free(p);             /*释放p指向的结点*/
    return 1;
}
int StackLength(LinkStack top)
{
    LStackNode *p = top;
    int count = 0;
    while (p->next != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}
void DestroyStack(LinkStack top)
{
    LStackNode *p = top;
    while (!p)
    {
        LStackNode *q = p;
        p = p->next;
        free(q);
    }
}
int GetTop(LinkStack top, DataType *e)
{
    LStackNode *p = top->next;
    if (!p) /*判断链栈是否为空*/
    {
        printf("栈已空");
        return 0;
    }
    *e = p->data; /*将出栈元素赋值给e*/
    return 1;
}

共享栈

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
/* 两栈共享空间结构 */
typedef struct
{
    int data[MAXSIZE];
    int top1; /* 栈1栈顶指针 */
    int top2; /* 栈2栈顶指针 */
} SqDoubleStack;

/*  构造一个空栈S */
int InitStack(SqDoubleStack *S)
{
    S->top1 = -1;
    S->top2 = MAXSIZE;
    return OK;
}
/* 插入元素e为新的栈顶元素 */
int Push(SqDoubleStack *S, int e, int stackNumber)
{
    if (S->top1 + 1 == S->top2) /* 栈已满，不能再push新元素了 */
        return ERROR;

    if (stackNumber == 1)       /* 栈1有元素进栈 */
        S->data[++S->top1] = e; /* 若是栈1则先top1+1后给数组元素赋值。 */
    else if (stackNumber == 2)  /* 栈2有元素进栈 */
        S->data[--S->top2] = e; /* 若是栈2则先top2-1后给数组元素赋值。 */
    return OK;
}
int StackTraverse(SqDoubleStack S)
{
    for (int i = 0; i < S.top1; i++)
        printf("%d ", S.data[i]);

    for (int i = S.top2; i < MAXSIZE; i++)
        printf("%d ", S.data[i]);

    printf("\n");
    return OK;
}
/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
int StackEmpty(SqDoubleStack S)
{
    if (S.top1 == -1 && S.top2 == MAXSIZE)
        return TRUE;
    else
        return FALSE;
}
/* 返回S的元素个数，即栈的长度 */
int StackLength(SqDoubleStack S)
{
    return (S.top1 + 1) + (MAXSIZE - 1 - S.top2);
}
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
int Pop(SqDoubleStack *S, int *e, int stackNumber)
{
    if (stackNumber == 1)
    {
        if (S->top1 == -1)
            return ERROR; /* 说明栈1已经是空栈，溢出 */

        *e = S->data[S->top1]; /* 将栈1的栈顶元素出栈 */
        S->top1--;
    }
    else if (stackNumber == 2)
    {
        if (S->top2 == MAXSIZE)
            return ERROR; /* 说明栈2已经是空栈，溢出 */

        *e = S->data[S->top2]; /* 将栈2的栈顶元素出栈 */
        S->top2++;
    }
    return OK;
}
int main()
{
    int j, e;
    SqDoubleStack s;

    if (InitStack(&s) == OK)
    {
        for (j = 1; j <= 5; j++)
            Push(&s, j, 1);
        for (j = MAXSIZE; j >= MAXSIZE - 2; j--)
            Push(&s, j, 2);
    }

    printf("栈中元素依次为：");
    StackTraverse(s);

    printf("当前栈中元素有：%d \n", StackLength(s));

    Pop(&s, &e, 2);
    printf("弹出的栈顶元素 e=%d\n", e);
    printf("栈空否：%d(1:空 0:否)\n", StackEmpty(s));

    for (j = 6; j <= MAXSIZE - 2; j++)
        Push(&s, j, 1);
    printf("栈中元素依次为：");
    StackTraverse(s);

    printf("栈满否：%d(1:否 0:满)\n", Push(&s, 100, 1));

    InitStack(&s);
    printf("清空栈后，栈空否：%d(1:空 0:否)\n", StackEmpty(s));

    return 0;
}

共享栈

typedef struct
{
    DataType stack[StackSize];
    int top[2];
} SSeqStack;

void InitStack(SSeqStack *S)
/*共享栈的初始化操作*/
{
    S->top[0] = 0;
    S->top[1] = StackSize - 1;
}
int PushStack(SSeqStack *S, DataType e, int flag)
/*共享栈进栈操作。进栈成功返回1，否则返回0*/
{
    if (S->top[0] == S->top[1]) /*在进栈操作之前，判断共享栈是否为空*/
        return 0;
    switch (flag)
    {
    case 0:                      /*当flag为0，表示元素要进左端的栈*/
        S->stack[S->top[0]] = e; /*元素进栈*/
        S->top[0]++;             /*修改栈顶指针*/
        break;
    case 1:                      /*当flag为1，表示元素要进右端的栈*/
        S->stack[S->top[1]] = e; /*元素进栈*/
        S->top[1]--;             /*修改栈顶指针*/
        break;
    default:
        return 0;
    }
    return 1;
}
int PopStack(SSeqStack *S, DataType *e, int flag)
{
    switch (flag) /*在出栈操作之前，判断是哪个栈要进行出栈操作*/
    {
    case 0:
        if (S->top[0] == 0) /*左端的栈为空，则返回0，表示出栈操作失败*/
            return 0;
        S->top[0]--;              /*修改栈顶指针*/
        *e = S->stack[S->top[0]]; /*将出栈的元素赋值给e*/
        break;
    case 1:
        if (S->top[1] == StackSize - 1) /*右端的栈为空，则返回0，表示出栈操作失败*/
            return 0;
        S->top[1]++;              /*修改栈顶指针*/
        *e = S->stack[S->top[1]]; /*将出栈的元素赋值给e*/
        break;
    default:
        return 0;
    }
    return 1;
}
int GetTop(SSeqStack S, DataType *e, int flag)
/*取栈顶元素。将栈顶元素值返回给e，并返回1表示成功；否则返回0表示失败。*/
{
	switch (flag)
	{
	case 0:
		if (S.top[0] == 0)
			return 0;
		*e = S.stack[S.top[0] - 1];
		break;
	case 1:
		if (S.top[1] == StackSize - 1)
			return 0;
		*e = S.stack[S.top[1] + 1];
		break;
	default:
		return 0;
	}
	return 1;
}
int StackEmpty(SSeqStack S, int flag)
{
	switch (flag)
	{
	case 0:
		if (S.top[0] == 0)
			return 1;
		break;
	case 1:
		if (S.top[1] == StackSize - 1)
			return 1;
		break;
	default:
		return 0;
	}
	return 0;
}