栈和队列

栈： 使用数组实现，就要用类来表示，类可以保存携带数据。。

// My_stack.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>

using namespace std;


class mystack
{
public:
    mystack(){top=0;}
    bool full();
    bool isEmpty();
    void push(int i);
    int pop();
    friend void print(mystack &);
    friend ostream& operator<<(ostream& os,mystack& ms);
private:
    int a[10];
    int top;
};
ostream& operator<<(ostream& os,mystack& ms)
{
    os<<ms.a;
    return os;
}
void print(mystack & ms)
{
    for (int i=0;i<10;i++)
    {
        cout<<ms.a[i]<<" ";
    }
    cout<<endl;
}
bool mystack::full()
{
    if (top==10)
        return true;
    else return false;
}
bool mystack::isEmpty()
{
    if (top==0)return true;
    else return false;
}

void mystack::push(int i)
{
    if (full())
        cout<<"stack overflow!"<<endl;
    else
    {
        top=top+1;
        a[top]=i;
    }
}

int mystack::pop()
{
    if (isEmpty())
    {
        cout<<"stack underflow!"<<endl;
        return -1;
    }
    else
    {
        top--;
        return a[top+1];
    }    
}

int _tmain(int argc, _TCHAR* argv[])
{
    mystack ms;
    cout<<ms.isEmpty()<<endl;

    for (int i=0;i<10;i++)
    {
        ms.push(2*i);
        cout<<"push "<<i<<endl;
    }
    cout<<ms.full()<<endl;
    print(ms);
    cout<<ms.pop()<<endl;
    system("pause");
    return 0;
}

 用链表实现stack。算法导论10.2-2

// stack.cpp : 定义控制台应用程序的入口点。
//用链表实现栈

#include "stdafx.h"
#include <iostream>

using namespace std;

typedef struct _Node
{
    int data;
    _Node* next;
}node;
/*
typedef struct _Stack
{
    node* head=(node*)malloc(sizeof(node));
    head->next=head;
}stack;
*/

node* createNode(int data)
{
    node* nnode=(node*)malloc(sizeof(node));
    nnode->data=data;
    nnode->next=NULL;
    return nnode;
}
/*
node* createStack(int data)
{
    node* head=(node*)malloc(sizeof(node));
    head->data=data;
    head->next=head;
    return head;
}*/
node* appendNode(node* head,int key)
{
    node* new_node=createNode(key);
    node* p=head,*q;
    while (p!=NULL)
    {
        q=p;
        p=p->next;
    }
    q->next=new_node;
    return head;

    /*
    node* p=head,*q;
    if (p==NULL)
    {
        cout<<"stack is empty"<<endl;
        return NULL;
    }
    else 
    {
        
        node* new_node=createNode(key);
        while (p!=NULL)
        {
            q=p;
            p=p->next;
        }
        q->next=new_node;
    }
    return head;
    */
}

node* stack_push(node* head,int key)
{
    node* p=head,*q;
    q=p->next;
    node* new_node=createNode(key);
    new_node->next=q;
    p->next=new_node;
    return head;
}

node* stack_pop(node* head)
{
    node* p=head,*q;
    q=p->next;
    if (p==NULL)
    {
        cout<<"哎呦!"<<endl;
        return NULL;
    }
    else
    {
        p->next=q->next;
        free(q);
    }
    return head;
}

int top(node* head)
{
    node* p=head;
    if (p->next==NULL)
    {
        cout<<"there is no elements in stack!"<<endl;
        return NULL;
    }
    else
    {
        return p->next->data;
    }
}

void print(node* head)
{
    node* p=head;
    while (p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
        /*
        if(p!=NULL)
            p=p->next;
            cout<<p->data<<" ";
            之前这样写程序奔溃了，找半天，==
        */
    }
    cout<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
    node* head=createNode(0);//头结点置为0
    for (int i=1;i<10;i++)
    {
        head=appendNode(head,i);
    }
    print(head);
    stack_push(head,10);
    cout<<top(head)<<endl;;
    stack_push(head,11);
    stack_push(head,12);
    print(head);
    for (int i=1;i<=12;i++)
    {
        stack_pop(head);
        print(head);
    }
    free(head);
    system("pause");
    return 0;
}

 队列：使用链表实现.算导10.2-3

// My_queue.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

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

typedef struct myQueue
{
    node* front;
    node* rear;
}myQueue;

myQueue* createQueue()
{
    myQueue* q=(myQueue*)malloc(sizeof(node));//头结点
    q->front=NULL;
    q->rear=NULL;
    return q;
}

myQueue* enqueue(myQueue* q,int data)
{
    Node* new_Node=(Node*)malloc(sizeof(Node));
    new_Node->data=data;
    new_Node->next=NULL;
    if (q->rear==NULL)
    {//队列为空，队首队尾都指向new_node
        q->front=q->rear=new_Node;
    }
    else
    {//不空，将新节点连接到最后一个节点q->rear之后
        q->rear->next=new_Node;
        q->rear=new_Node;
    }
    return q;
}

myQueue* dequeue(myQueue* q)
{
    Node* dq=NULL;
    dq=q->front;
    if (dq==NULL)cout<<"empty!"<<endl;
    else
    {
        q->front=q->front->next;
        if (q->front==NULL)
            q->rear=NULL;//一个节点的情况
        free(dq);
    }
    return q;
}

int GetLength(myQueue* q)
{
    Node* gq=NULL;
    gq=q->front;
    int i=0;
    while (gq!=q->rear)
    {
        i++;
        gq=gq->next;
    }
    i++;
    return i;
}
void print(myQueue* q)
{
    Node* pq=NULL;
    pq=q->front;
    if(pq==NULL)
    {
        cout<<"empty!"<<endl;
        return;
    }
    while (pq!=q->rear)
    {
        cout<<pq->data<<" ";
        pq=pq->next;
    }
    cout<<q->rear->data<<endl;
    if(pq==NULL) cout<<"queue is empty!"<<endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    myQueue *mq=createQueue();
    print(mq);
    enqueue(mq,1);
    enqueue(mq,2);
    enqueue(mq,3);
    enqueue(mq,4);
    int i=GetLength(mq);
    print(mq);
    dequeue(mq);
    print(mq);
    dequeue(mq);
    print(mq);
    dequeue(mq);
    print(mq);
    dequeue(mq);
    print(mq);
    system("pause");
    return 0;
}